A Set Theory Proof

feliks0 · #1 $Old$ October 31st, 2009, 07:30 AM

Hello,

This is my first time posting a question on this forum and I am a newbie in the field of discrete mathematics.
I uploaded question number 9a which I've been trying to solve for the last 3 days without much success, as well as my attempt at solving it.

Any suggestions would be welcome!

Plato · #2 $Old$ October 31st, 2009, 07:57 AM

You want to prove that $(A\cup C)\cap(B\cup C')\subseteq (A\cup B).$
I would do it by contradiction.
Suppose that $t\in (A\cup C)\cap(B\cup C')~\&~t \notin(A\cup B)$ .
Then that means that $t\notin A~\&~t\notin B$ .

From which we get $t\in (A\cup C)~\&~t\notin A$ so $t\in C$ .

Also we get $t\in (B\cup C')~\&~t\notin B$ so $t\in C'$ .

Do you see the contradiction?

feliks0 · #3 $Old$ October 31st, 2009, 09:50 AM

First of all, let me thank you for your kind help.

If I got your idea right, then since t cannot be both an element of C and an element of the complement of C, we deduce that the opposite is correct concerning the first line. That is, the left side is a subset of the right side.

I was trying to get to having the same expressions on both sides of the equation by using the consistency principle, since that is what is expected from me. Elegant solutions never hurt anyone though.

Thank you once more!

Plato · #4 $Old$ October 31st, 2009, 10:23 AM

Quote:

Originally Posted by feliks0 $View Post$

I was trying to get to having the same expressions on both sides of the equation by using the consistency principle, since that is what is expected from me.

First this is not an equation. Moreover, it turnout to be rather messy to expand the LHS.
I am not sure that is really the best way to proceed. I did not see a way to do it easily.
There is a simple demonstration using Venn diagrams.
To use the ‘pick-a-point’ proof may be the best alterative to what I posted.
Actually I came to the posted proof as a result of starting out that way.

Failure · #5 $Old$ October 31st, 2009, 10:56 AM

Quote:

Originally Posted by Plato $View Post$

First this is not an equation. Moreover, it turnout to be rather messy to expand the LHS.

Expanding the LHS doesn't look so bad. What about the following
$\begin{array}{lcl}(A\cup C)\cap (B\cup C')&=&A\cap (B\cup C')\cup C\cap (B\cup C')\\ &=& A\cap (B\cup C')\cup C\cap B\cup C\cap C' \end{array}$
(Assuming the convention that $\cap$ binds more strongly than $\cup$ , of course.)
Now we have decomposed the original LHS into a union of three sets, the first is a subset of A (since intersecting A with any other set gives a subset of A), the second is a subset of B (again, because this is an intersection of B with another set) and the third is the empty set. Hence the whole union is contained in the union of A and B.
More formally, this is last step uses the following general rule: If $X\subseteq Z$ and $Y\subseteq Z$ then $X\cup Y \subseteq Z$ . Which is just another way of saying that $\cup$ is a "least upper bound" operator in the boolean lattice of subsets of a given universal set: if Z is an upper bound for both X and Y then it is also an upper bound for $X\cup Y$ .
Similarly, intersection of sets is a "greatest lower bound" operator in that boolean lattice.

oldguynewstudent · #6 $Old$ November 1st, 2009, 07:55 AM

Quote:

Originally Posted by Failure $View Post$

Expanding the LHS doesn't look so bad. What about the following
$\begin{array}{lcl}(A\cup C)\cap (B\cup C')&=&A\cap (B\cup C')\cup C\cap (B\cup C')\\&=& A\cap (B\cup C')\cup C\cap B\cup C\cap C'\end{array}$
(Assuming the convention that $\cap$ binds more strongly than $\cup$ , of course.)
Now we have decomposed the original LHS into a union of three sets, the first is a subset of A (since intersecting A with any other set gives a subset of A), the second is a subset of B (again, because this is an intersection of B with another set) and the third is the empty set. Hence the whole union is contained in the union of A and B.
More formally, this is last step uses the following general rule: If $X\subseteq Z$ and $Y\subseteq Z$ then $X\cup Y \subseteq Z$ . Which is just another way of saying that $\cup$ is a "least upper bound" operator in the boolean lattice of subsets of a given universal set: if Z is an upper bound for both X and Y then it is also an upper bound for $X\cup Y$ .
Similarly, intersection of sets is a "greatest lower bound" operator in that boolean lattice.

I have gotten so much help from this website and the wonderful people here. I can follow Failure's elegant proof. What my professor was looking for from my class was more of a continuation and definition oriented proof.

$A\cap (B\cup C')\cup C\cap B\cup C\cap C'$

= $A \cap B \cup (C' \cup C) \cap B \cup \emptyset$

= $A \cap B \cup \mho \cap B$

= $A \cap B \cup B$ = $A \cap B$

= { x | x $\epsilon$ (A AND B) }

= { x | x $\epsilon$ A AND x $\epsilon$ B }

$\forall$ x, x $\epsilon$ A OR x $\epsilon$ B which is the definition of a subset.

Failure's proof is much more elegant not to mention shorter. However if you're just beginning with the definitions etc. this may be more what your professor is looking for. I also hope I got it right!

Failure · #7 $Old$ November 1st, 2009, 11:13 AM

Quote:

Originally Posted by oldguynewstudent $View Post$

I have gotten so much help from this website and the wonderful people here. I can follow Failure's elegant proof. What my professor was looking for from my class was more of a continuation and definition oriented proof.

$A\cap (B\cup C')\cup C\cap B\cup C\cap C'$

= $A \cap B \cup (C' \cup C) \cap B \cup \emptyset$

I don't see how you get this from the preceding line, I must admit.

Quote:

= $A \cap B \cup \mho \cap B$

= $A \cap B \cup B {\color{red}\overset{?}{=}} A \cap B$

One thing I believe to know for sure: $(A\cap B)\cup B = B$ so something is amiss here.

Quote:

= { x | x $\epsilon$ (A AND B) }

= { x | x $\epsilon$ A AND x $\epsilon$ B }

$\forall$ x, x $\epsilon$ A OR x $\epsilon$ B which is the definition of a subset.

Failure's proof is much more elegant not to mention shorter. However if you're just beginning with the definitions etc. this may be more what your professor is looking for. I also hope I got it right!

oldguynewstudent · #8 $Old$ November 1st, 2009, 03:53 PM

Quote:

Originally Posted by Failure $View Post$

I don't see how you get this from the preceding line, I must admit.

One thing I believe to know for sure: $(A\cap B)\cup B = B$ so something is amiss here.

I am still learning this and prone to mistakes. Perhaps I misinterpreted C', which I took to be the complement of C.

In that case, C $\cap$ C' would be the null set by the complement law.

Then by the associative propery, (B $\cup$ C') $\cup$ C = B $\cup$ (C' $\cup$ C).

Of course B $\cup$ null = B

And it looks like I made a mistake in the last line. I had mistakenly taken B $\cup$ B first instead of using the absorbtion law.

Thank you again for your expert help! And please continue to critique. It is the best way to learn.