Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Logical Proof

  1. Feb 3, 2008 #1
    1. The problem statement, all variables and given/known data

    To prove [tex]A \subseteq C and B \subseteq C[/tex] implies [tex](A \cup B)\subseteq C[/tex]

    2. The attempt at a solution

    I just wanted to know if my reasoning seems logical. Here is my attempt:

    Assume [tex]A \subseteq C and B \subseteq C ........ (1) [/tex]
    Assume [tex]\forall x [ x\in A] and \forall x [x \in B] ........... (2) [/tex]
    Hence, from definition of [tex]\bigcup \forall x [x \in A \cup B ] ....... (3)[/tex]

    From (1) and defination of [tex]\subseteq, \forall x [ x \in A \Rightarrow x \in C and x \in B \Rightarrow x \in C ] .............. (4)[/tex]

    Hence, [tex]\forall x [x \in A \cup B \Rightarrow x \in C] .............. (5)[/tex]

    [tex]\Rightarrow (A \cup B) \subseteq C


    Does that seem to flow logically?

  2. jcsd
  3. Feb 4, 2008 #2
    Hi Ajsingh!

    I think your progression is correct except for premise 2. You say that x is an element of A, AND, x is an element of B. That can be true, but it doesn't have to be true. I recommend switching the AND to an OR. After you make that change, I don't see any fault in your logic. I also think it flows better if you switch premises 3 and 4. I know it's semantics but the progression seems better to me.

    I also want to point out that unless specified in the problem, it might be enough to simply demonstrate that this proof is true. What if you assigned C={1,2,3,4,5}, A={1,2,3}, B={3,4}

    A is a subset of C. B is a subset of C, A U B = {1,2,3,4} which also is a subset of C. Proved. I mention this, because it also shows a contradiction to your premise #2. Namely, 4 is an element of B but NOT an element of A.

    Hope this helps!

  4. Feb 4, 2008 #3


    User Avatar
    Science Advisor

    You want to prove one set is a subset of another. The standard way of doing that is to say "if x in the first set" and show "therefore x is in the second set".

    While this isn't, strictly speaking, wrong, you don't need to "assume" that- it is given.

    Now you don't want to say that! For one thing, A and B might be disjoint- there might be no such x! What you want to say is "Assume [itex] x\in A\cup B[/itex].

    You are going the wrong way. Starting from the assumption that [itex]a\in A \cup B[/itex] it follows that either [itex]x\in A[/itex] or [itex]x\in B[/itex].

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook