# Homework Help: Prove an Associative Law (set theory)

1. Jun 12, 2013

### gunslinger

1. The problem statement, all variables and given/known data
Prove that: A$\cup$(B$\cup$C) = (A$\cup$B)$\cup$C

2. Relevant equations

3. The attempt at a solution
I never had to prove anything but I'll try.
A$\cup$(B $\cup$C).
Take:
A = {1, 2, 3, 4, 5}, B = {5, 6, 7, 8, 9, 10}, C = {7, 8, 9, 10}
(B$\cup$C) = P
If A$\cup$P means A, united with the union of B and C, which is {5, ..., 10}. Their union is {1, ..., 10}
Now take (A$\cup$B) = P
P = {1, ..., 10}
P$\cup$C = {1, ..., 10}
With that I prove that the problem above is True :P But is that enough?

Last edited: Jun 12, 2013
2. Jun 12, 2013

### MarneMath

When proving a general statement, you need to avoid specific cases. Although working through a specific case may help you get the general idea on how to prove a statement, it doesn't prove the general case. When it comes to proving sets, the most common technique is to grab an arbitrary element from the set and show that since it belongs to a certain set it also belongs to this other set to and work towards your result. For example, let x be an element from the set A U (B U C), then x is an element of A or x is an element of (B U C). If x is an element of A...etc etc etc

3. Jun 12, 2013

### Staff: Mentor

No, it's not. You can't prove a general statement by the use of an example.

One way to prove this would be to start with an element x that is an element of $A \cup (B \cup C)$, and show that it is also in $(A \cup B) \cup C$. This shows that the set on the left side of the equation is a subset of the one on the right side.

Now assume that x is an element of $(A \cup B) \cup C$. If you can show that the same element also belongs to $(A \cup B) \cup C$, you will have shown that the set on the right side is a subset of the one on the left side, which establishes the equality of the two sets.

4. Jun 13, 2013

### gunslinger

If x is an element of A U (B U C). That means that x is either in A, B or C.
If x is an element of C U (A U B). That means that x is either in A, B or C.

5. Jun 13, 2013

### Staff: Mentor

When you say "either ... or" the implication is that x is in one of them, but not the other. That is not necessarily true. It could be that A and B overlap (their intersection is not empty, or that A and C overlap, or that B and C overlap, or even that all three sets overlap.

So it's conceivable that x is in both A and B, but not in C, for example.
I would write it as (A U B) U C, which is the way it's written in the problem. What I said above applies here as well.

6. Jun 13, 2013

### LCKurtz

Presumably you mean $(A\cup B)\cup C$. While what you say is true, it doesn't constitute a proof. To show two sets $M$ and $N$ are the same, you show $M\subset N$ and $N \subset M$. You are leaving out a lot of steps. So start out with supposing $x\in A\cup (B\cup C)$. That means $x\in A$ or $x \in B\cup C$, as you have stated. And if $x \in B\cup C$ then $x\in B$ or $x \in C$. Now, depending on which is the case, you have to show in any event that $x \in (A\cup B)\cup C$. You can't just declare it to be true. Give the details for each possibility. Once you have that, you are half done with the problem.

7. Jun 14, 2013

### gunslinger

So, for (A $\cup$ B) $\cup$ C. Suppose x $\in$ (A $\cup$ B) $\cup$ C. That means x $\in$ (A $\cup$ B) or x $\in$ C. From x $\in$ (A $\cup$ B) we can derive that x $\in$ A or x $\in$ B.

8. Jun 14, 2013

### HallsofIvy

I would give a little more detail. To prove "A U (B U C)= (A U B) To prove "if x is in A U (B U C) then it is s in A U (B U C)" (the statement says nothing about "C U (A U B)") we prove
1) A U (B U C)$\subseteq$ (A U B) U C and then prove
2) (A U B) U C $\subseteq$ A U (B U C)

And we prove "X $\subseteq$ Y" by starting "if x is in X" and using the properties of X and Y to conclude "then x is in Y".

If x is in A U(B U C) then (by definition of "U") x is in A or x is in B U C. Again, by definition of U, if x is in B U C then x is in B or in C. So we have three possibilities
1) if x is in A then it is in A U B and so in (A U B) U C.
2) if x is in B then it is in A U B and so in (A U B) U C.
3) if x is in C then it is immediately in (A U B) U C.

Do the same to prove "(A U B) U C $\subseteq$ A U (B U C)".

9. Jun 14, 2013

### gunslinger

Aha so firstly we prove how the left side is equal to the right and then how the right side is equal to the left?

10. Jun 14, 2013

### Fredrik

Staff Emeritus
No. First you prove that every element of the set on the left is an element of the set on the right, and then you prove that every element of the set on the right is an element of the set on the left.

There's an axiom of set theory that says that an equality X=Y holds if and only if every element of X is an element of Y, and every element of Y is an element of X. That's what you need to use.

So you should start by saying something like "Let x be an arbitrary element of $A\cup(B\cup C)$". Then you use the definition of $\cup$ to prove that $x\in (A\cup B)\cup C$. Then I suggest you leave a blank line for clarity, and start the next paragraph with "Now let x be an arbitrary element of $(A\cup B)\cup C$". The rest should be obvious.

This isn't precalculus by the way. Since set theory is usually studied after calculus, I will move this to calculus & beyond.