# Logical Proof

1. Feb 3, 2008

### ajsingh

1. The problem statement, all variables and given/known data

To prove $$A \subseteq C and B \subseteq C$$ implies $$(A \cup B)\subseteq C$$

2. The attempt at a solution

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

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

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

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

$$\Rightarrow (A \cup B) \subseteq C$$

Does that seem to flow logically?

Thanks

2. Feb 4, 2008

### Nevetsman

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!

Steve

3. Feb 4, 2008

### HallsofIvy

Staff Emeritus
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 $x\in A\cup B$.

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