# Help with proof

1. Jun 29, 2008

### Feldoh

Ok so over the summer I decided to read Apostol's Calculus Vol. 1 and my only background in calculus is in a high school calculus class, so I know the extreme basics and am trying to put my knowledge on a my rigorous footing.

I think my biggest problem is definitely writing my own proofs. I just started so I'm still in the section that covers basic set theory and it asks to prove commutative and associative properties involving unions and intersections. I think I can prove the commutative law but the associative law is proving (pun intended) to be quite difficult for me. I just seem to be going around in circles just writing out the problem so I was wondering if anyone could critique this bad attempt and give me some sort of starting place.

Prove $$(A \cup B) \cup C = A (B \cup C)$$

Let $$x \in A, y \in B, z \in C$$ and let $$D = A \cup B, E B \cup C$$

This implies D = {x, y} and E = {y, z}

So $$D \cup C =$$ {x, y, z} and $$A \cup E =$$ {x, y, z}

Therefore $$D \cup C = A \cup E = (A \cup B) \cup C = A (B \cup C)$$

2. Jun 29, 2008

### d_leet

You're going about this the wrong way. You do not know ahead of time that any of A, B, or C are non-empty so you can't really let x, y, or z belong to any of those sets. Furthermore even if we can let x be in A and y be in B then that does not mean D={x,y}, A and B could have other elements, or x could be equal to y.

The basic idea in showing that two sets, let's call them P and Q are equal is to show that:
1) if x is in P, then x is in Q, and
2) if y is in Q then x is in P

Statement one proves that P is a subset of Q (why?). And statement two proves that Q is a subset of P, and two sets can only be subsets of each other if they are equal and are in fact the same set, so this is what you need to do for the case where P=(AUB)UC and Q=AU(BUC).

3. Jun 29, 2008

### Feldoh

If you can prove statement one true it proves that P is a subset of Q by the definition of a subset which is for every element x in set P it is contained in set Q, the same goes for statement two just reversed in a sense, correct? My problem, I think, is proving statement one and two true. I thought about that but the best I could come up with was to assume that $$x \in P$$ which is one of the problems in my original attempt.

I still don't think I'm getting it...

4. Jun 29, 2008

### waht

yes precisely

To show that P = Q, you must show that $P \subset Q[/tex] and [itex]Q \subset P[/tex] To show that [itex]P \subset Q[/tex] Allow [itex] x \in P$. Then show that $x \in Q$.

5. Jun 29, 2008

### d_leet

If x is in (AUB)UC what is true about x? How can we use any of this information to show that x is in AU(BUC)?

6. Jun 30, 2008

### waht

If x is in (A U B) U C then x is in (A U B) or x is in C.

just work the definitions

7. Jun 30, 2008

### Feldoh

All of this makes sense however what if A, B and C are empty then P would also be empty so how can we just assume $x \in P$?

Edit: By the way thanks for all the help so far :)

8. Jun 30, 2008

### HallsofIvy

Some textbooks make the point that you should start a set proof like this "If x is in (A U B) U C" rather than "Let x be in (A U B) U C" for precisely that reason. If A, B, C are all empty you can't say "let x be in ..." but the hypothesis of "if x is in ..." is, in that case, false, so the theorem itself is vacuously true.

Last edited by a moderator: Aug 1, 2008
9. Jun 30, 2008

### Feldoh

So...

Let P = (A U B) U C and Q = A U (B U C)

If $x \in P$ then x must belong to, at least, one set A, B, or C.

Therefore $x \in Q$ ==> $P \subseteq Q$

By the same logic we find $Q \subseteq P$

Therefore P=Q ==> (A U B) U C = A U (B U C)

Is that correct?

10. Jun 30, 2008

### matt grime

This is largely immaterial: if X is empty, then the statement if x in X then... is vacuously true so there is nothing to worry about.
Alternately one can worry about these exceptions individually, but the proof then is also trivial.

11. Jun 30, 2008

### Feldoh

Yeah, but the way I worded it in the first post was "Let x..." instead of "If x..." I can kind of see a difference in the two. "If" implies we're just considering a case where as "Let" kind of seems like one is simply saying x IS in a particular set.

12. Jul 30, 2008

### peos69

xεAU(BUC)<====>xεAVxε(BUC)<======>xεAV(xεBVxεC)<======>(xεAVxεB)VxεC<===>
xε(AUB)VxεC<======>xε(AUB)UC<====> AU(BUC)= (AUB)UC
The qestion now is how do we prove xεAV(xεBVxεC) <====>(xεAVxεB)VxεC

13. Jul 31, 2008

### peos69

Here is another proof:
Let xɛ[AU(BUC)] then this is equivalent to xɛAV xɛ(BUC) then we have to examine two cases:
1) for xɛA but xɛA ==> xɛAv xɛB <====> xɛ(AUB) ===> xɛ(AUB)v xɛC <===> xɛ[(AUB)UC]

2) for xɛ(BUC),but xɛ(BUC) <===> xɛBv xɛC AND now we examine the two subcases.
2a) for xɛB WE HAVE xɛB ==> xɛBv xɛA <===> xɛAv xɛB <==> xɛ(AUB) ===> xɛ(AUB)vxɛC <==> xɛ[(AUB)UC]
2b) for xɛC WE HAVE xɛC ==> xɛCv xɛ(AUB) ==> xɛ(AUB)v xɛC <=====> xɛ[(AUB)UC]
Hence all cases give us xɛ[(AUB)UC]
So we have proved xɛ[AU(BUC)]====> xɛ[(AUB)UC]
Now for the opposite we follow exactly the same way

14. Jul 31, 2008

### peos69

Here is one more proof

Let xɛ[AU(BUC)] this is equivalent to xɛAvxɛ(BUC) which is equivalent to
~xɛA→xɛ(BUC). ………………………………………………..1

Let ~xɛ(AUB) then by D Morgans rule we have that
~xɛA…………………………………………………………2
~xɛB………………………………………………………….3
From 1 and 2 we deduce xɛ(BUC) which is equivalent to
xɛBvxɛC↔ ~xɛB→xɛC…………………………………………….4
From 3 and 4 we deduce xɛC
Hence ~xɛ(AUB)→xɛC or xɛ(AUB)vxɛC or xɛ[(AUB)UC]
Therefor xɛ[AU(BUC]→xɛ[(AUB)UC]
For the opposite we follow exactly the same way
NOTE ~xε means x does not belong to

15. Aug 1, 2008

### peos69

Now let us present a proof by contradiction.
Let xε[AU(BUC)]
But xε[AU(BUC)] <==> xεAv xε(BUC) <==>
~ xε A==> xε(BUC)………………………………………………1
Let now ~ xε[(AUB)UC]
But ~ xε[(AUB)UC] <==> ~ xε(AUB)˄ ~ xεC====>
~ xεA…………………………………………………………………2
~ xεB………………………………………………………………….3
~ xεC………………………………………………………………….4
Now from 1 and 2 we deduce xε(BUC)……………………………..5
From 3 and 4 we have ~ xεB˄~ xεC <===>~ xε(BUC)………….6
But 5 and 6 are contradictory .
Hence xε[(AUB)UC]
So we have proved xε[AU(BUC)] ==>` xε[(AUB)UC]
For the opposite we follow the same way