Help Proving Commutative & Associative Properties of Unions & Intersections

  • Thread starter Feldoh
  • Start date
  • Tags
    Proof
In summary: 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.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).If you can prove statement one true it proves
  • #1
Feldoh
1,342
3
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 [tex](A \cup B) \cup C = A (B \cup C)[/tex]

Let [tex]x \in A, y \in B, z \in C[/tex] and let [tex]D = A \cup B, E B \cup C[/tex]

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

So [tex]D \cup C =[/tex] {x, y, z} and [tex] A \cup E =[/tex] {x, y, z}

Therefore [tex]D \cup C = A \cup E = (A \cup B) \cup C = A (B \cup C)[/tex]
 
Physics news on Phys.org
  • #2
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
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 [tex]x \in P[/tex] which is one of the problems in my original attempt.

I still don't think I'm getting it...
 
  • #4
Feldoh said:
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?

yes precisely

To show that P = Q, you must show that [itex]P \subset Q[/tex] and [itex]Q \subset P[/tex]


To show that [itex]P \subset Q[/tex]

Allow [itex] x \in P [/itex]. Then show that [itex] x \in Q [/itex].
 
  • #5
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
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
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 [itex]x \in P[/itex]?

Edit: By the way thanks for all the help so far :)
 
  • #8
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:
  • #9
So...

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

If [itex]x \in P[/itex] then x must belong to, at least, one set A, B, or C.

Therefore [itex]x \in Q[/itex] ==> [itex]P \subseteq Q[/itex]

By the same logic we find [itex]Q \subseteq P[/itex]

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

Is that correct?
 
  • #10
d_leet said:
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.

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
matt grime said:
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.

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
here is your proof:
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
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
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
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
 

1. What are the commutative and associative properties of unions and intersections?

The commutative property states that the order in which sets are joined by a union or intersection does not affect the result. For example, A ∩ B = B ∩ A. The associative property states that the grouping of sets does not affect the result. For example, (A ∪ B) ∪ C = A ∪ (B ∪ C).

2. Why are the commutative and associative properties important in set theory?

The commutative and associative properties are important because they allow us to manipulate and simplify expressions involving sets. This is particularly useful in proving mathematical theorems and solving problems in various fields of science and mathematics.

3. How do you prove the commutative property of unions and intersections?

To prove the commutative property, we must show that the order of the sets does not affect the result. This can be done by showing that A ∩ B = B ∩ A and A ∪ B = B ∪ A using the definition of intersections and unions, and the fact that the order of elements in a set does not matter.

4. How do you prove the associative property of unions and intersections?

To prove the associative property, we must show that the grouping of sets does not affect the result. This can be done by showing that (A ∩ B) ∩ C = A ∩ (B ∩ C) and (A ∪ B) ∪ C = A ∪ (B ∪ C) using the definition of intersections and unions, and the fact that the order of elements in a set does not matter.

5. Can the commutative and associative properties be applied to more than two sets?

Yes, the commutative and associative properties can be applied to any number of sets. For example, the commutative property can be extended to A ∩ B ∩ C = B ∩ C ∩ A and A ∪ B ∪ C = B ∪ C ∪ A. Similarly, the associative property can be extended to (A ∩ B) ∩ C = A ∩ (B ∩ C) = B ∩ (A ∩ C) and (A ∪ B) ∪ C = A ∪ (B ∪ C) = B ∪ (A ∪ C).

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
721
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Topology and Analysis
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
4K
  • Linear and Abstract Algebra
Replies
10
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
898
Back
Top