1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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