Simple question on Union of sets: Proof of associativity

I need to prove $A\cup B \cup C=(A\cup B)\cup C=A\cup (B\cup C)$.

I already proved that $(A\cup B)\cup C=A\cup(B\cup C)$ by proving they are subsets of one another.

My question is now, how do I prove that they are equal to $A\cup B\cup C$? And is it necessary to include that part? I felt that it is, as the question asks to prove all 3 parts equal to each other. Please advise me. Thanks a lot!

• I think what you are supposed to prove is that $(A \cup B)\cup C = A \cup(B \cup C)$. Once you've done that, this justifies writing $A \cup B \cup C$ for this set and should be viewed as the definition of $A \cup B \cup C$. – Stefan Mesken Mar 21 '17 at 8:25
• What's with the downvotes? This is a completely reasonable question. It's based on a slight misunderstanding, but clearing up misunderstandings is what questions are for, and this question gives sufficient detail about the OP's confusion that we can figure out what the misunderstanding it and write answers that will hopefully dispel it. – Henning Makholm Mar 21 '17 at 8:32
• @Stefan Well, actually if we are talking about ZF then the Axiom of Union is defined over any collection of sets. – freakish Mar 21 '17 at 8:35
• @freakish: I don't think we're talking about ZF's axiom of union here, but about the binary union operator in a set algebra. (The union operator in ZF is unary, so it doesn't even make sense to ask whether it is associative). – Henning Makholm Mar 21 '17 at 8:36
• @HenningMakholm How can we prove something such fundamental as associativity of the union without touching the underlying axiomatic system? Union being unary in ZF doesn't change anything since you can write $\bigcup\{A, B, C\}$, $\bigcup\{\bigcup\{A, B\}, C\}$ and $\bigcup\{A, \bigcup\{B, C\}\}$. This is the proper (from the formal point of view) way to look at it. – freakish Mar 21 '17 at 8:40

You might say that there is actually no such thing as $A \cup B \cup C$, in a way. There are two possible orders of evaluation here, $(A \cup B) \cup C$ and $A \cup (B \cup C)$ which you showed to be equal. $A \cup B \cup C$ is just a notation to signify this equality and order-independence.

Together with commutativity, assuming you also proved that, so that $A \cup (B \cup C)$ is same as $(B \cup C) \cup A$, you can show that all possible ways of taking the union of three sets gives the same result. Thus we call it just $A \cup B \cup C$.

For four sets, you need to establish the equality of 24 permutations, I guess. But then you can write them all as $A \cup B \cup C \cup D$.

You can see this is getting tedious so an appeal to induction to show that this is true for all n is wise.

What you should have asked yourself before asking the question is what does $A\cup B\cup C$ mean? Which order is the operations supposed to be done? Or do you use a more clever definition for that(*)?

Actually in this case the associativity is used to give the expression $A\cup B\cup C$ a meaning: it says that we don't have to specify in which order the operations has to be done since $(A\cup B)\cup C=A\cup(B\cup C)$. As we don't have to do that we can just say that $A\cup B\cup C$ is defined as $(A\cup B)\cup C) = A\cup(B\cup C)$

(*) One could of course use more advanced machinery to define $A\cup B\cup C$ as the set consisting of elements that are in at least one of the sets $A$, $B$ or $C$. In that case one would have the case that there's something to be proven. One way to do it all is by using truth table:

$$\begin{matrix} x\in A & x\in B & x\in C & x\in (A\cup B) & x \in (A\cup B)\cup C & x \in (A\cup B\cup C) \\ \hline f & f & f & f & f & f \\ f & f & T & f & T & T \\ f & T & f & T & T & T \\ f & T & T & T & T & T \\ T & f & f & T & T & T \\ T & f & T & T & T & T \\ T & T & f & T & T & T \\ T & T & T & T & T & T \\ \end{matrix}$$

The $x\in (A\cup B)$ column is true whenever $x$ in one of $A$ and $B$ that is at least one of the first two columns is true. In similar way the next column is formed as true iff at least one of the $x\in C$ and $x\in (A\cup B)$ is true. The last is true whenever at least one of the first three is true.

That the last two columns are identical means that $x\in (A\cup B)\cup C)$ is equivalent to $x\in (A\cup B\cup C)$.

Let $a\in A \implies a \in A\cup B\cup C \ also a\in A\cup (B\cup C) \ and\ a \in (A\cup B)\cup C$. Similarly, Let $b\in B \implies b\in A\cup B\cup C \ also b\in A\cup (B\cup C) \ and\ b \in (A\cup B)\cup C$. Similarly, Let $c\in C \implies c\in A\cup B\cup C \ also c\in A\cup (B\cup C) \ and\ c \in (A\cup B)\cup C$.

So, $A\cup B\cup C = (A\cup B)\cup C = A\cup (B\cup C)$

I have just loudly championed a different answer in comments, but on further consideration, I do think there's more to it than that.

First, let us write down some definitions

1. If $A$ and $B$ are sets, then $A\cup B$ means the set whose elements are exactly every $x$ that is an element of at least one of $A$ and $B$.

2. If $A$, $B$ and $C$ are sets, then $A\cup B\cup C$ means the set whose elements are exactly every $x$ that is an element of at least one of $A$, $B$, and $C$.

Once we have given $A\cup B\cup C$ a definition it is not immediate that the set described by that definition is the same set as the one we get by doing the union in two separate steps as $(A\cup B)\cup C$. It is true that they are the same (fortunately so, because otherwise the notation $A\cup B\cup C$ would be really misleading), but it does deserve a proof of its own.

Proving this is not really more difficult than proving that $(A\cup B)\cup C = A\cup(B\cup C)$ by showing inclusions in both directions.

To show that this is not just empty pedantry, let's consider another example where it does not go as nicely:

1. If $A$ and $B$ are sets, then $A\mathop\triangle B$ means the set whose elements are exactly every $x$ that is an element of exactly one of $A$ and $B$.

2. If $A$, $B$ and $C$ are sets, then $\triangle(A,B,C)$ means the set whose elements are exactly every $x$ that is an element of exactly one of $A$, $B$, and $C$.

The binary $\triangle$ operation defined in (3) is quite nice and well-behaved (and useful enough in certain contexts that the notation $\triangle$ is somewhat standard). In particular, it is straightforward to prove that $\triangle$ is commutative and associative.

However, it is not true that $\triangle(A,B,C)$ is the same as $(A\triangle B)\triangle C$. (For a counterexample, consider $A=\{1,2\}$, $B=\{1,3\}$, $C=\{1,4\}$. Then $(A\triangle B)\triangle C=\{1,2,3,4\}$, but $\triangle(A,B,C)=\{2,3,4\}$).

So $\triangle$ is an example of an operator that seems to behave just as nice as $\cup$ does -- in particular, it is associative -- but where applying it to one argument at a time does not reproduce the straightforward generalization of the intuitive definition of the binary operator.

(What actually works is to say that $A_1\triangle A_2\triangle\cdots\triangle A_n$ is the set whose elements are exactly every $x$ that is an element of an odd number of the $A_i$s. Note that when there are just two operands, "an odd number" is the same as "exactly one", but "odd" is the description that generalizes well).