Results 1 to 8 of 8

Math Help - A Set Theory Proof

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    10

    A Set Theory Proof

    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!
    Attached Thumbnails Attached Thumbnails A Set Theory Proof-p1010178.jpg   A Set Theory Proof-p1010179.jpg   A Set Theory Proof-p1010180.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1615
    Awards
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    10
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1615
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    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')\\<br />
&=& A\cap (B\cup C')\cup C\cap B\cup C\cap C'<br />
\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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    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')\\<br />
&=& A\cap (B\cup C')\cup C\cap B\cup C\cap C'<br />
\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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    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.


    = 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.

    = { 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!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with set theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 8th 2011, 10:25 AM
  2. Set Theory: Help with a proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 11th 2010, 01:59 PM
  3. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  4. Set theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 22nd 2009, 04:13 AM
  5. Set theory proof help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 12th 2008, 02:33 PM

Search Tags


/mathhelpforum @mathhelpforum