$\begingroup$This is a problem from Discrete Mathematics and its Applications:
- Explain why $A \times B \times C$ and $(A \times B) \times C$ are not the same.
I understand the process behind the Cartesian product of two sets:
Let $A$ and $B$ be sets. The Cartesian Product of $A$ and $B$, denoted by $A \times B$, is the set of all ordered pairs $(a,b)$, where $a \in A$ and $b \in B$. Hence,
$$A \times B = \{(a,b)\mid a \in A \land b \in B\}.$$
You are forming a set of all the possible ordered pairs where one element is a member of the first set and the other element is a member of the other set.
How would you start this proof or explanation? To me these should be the same because it involves the same operation (Cartesian product). Usually when there are three expressions that are applied the same operation, you just go left to right, say 4 * 5 * 6. I don't understand how you would explain A x B x C is not equal to (A x B) x C. To me, using my last example, that's like explaining 4 * 5 * 6 is not equal to (4 * 5) *6.
$\endgroup$2 Answers
$\begingroup$You didn't give a definition for $A\times B\times C$ but it's usually defined by $$A\times B\times C=\{(a,b,c) | a\in A, b\in B, c\in C\}$$ Now $(A\times B)\times C$ is, by definition $$(A\times B)\times C = \{((a,b),c) | (a,b)\in A\times B, c\in C\} = \{((a,b),c) | a\in A,b\in B, c\in C\}$$ This shows you the difference: The elements are of the form $((a,b),c) \ne (a,b,c)$, but they are, in fact, in a 1-1 correspondence, wich may be the point of confusion.
Addendum due to comment of Asaf: An ordered pair can be written as a set: $$(a,b) = \{a,\{a,b\}\}\\ (a,b,c) = \{a,\{a,b\},\{a,b,c\}\}\\ ((a,b),c) = \{(a,b),\{(a,b),c\}\} = \Big\{\{a,\{a,b\}\},\{\{a,\{a,b\}\},c\}\Big\}$$ Wich clearly shows why $((a,b),c) \ne (a,b,c)$.
$\endgroup$16$\begingroup$Hint: What does a typical element of $(A \times B) \times C$ look like? A typical element of $A \times B \times C$?
$\endgroup$1A typical element of the former is $((a, b), c)$, which in particular is an ordered pair, and a typical element of the latter is $(a, b, c)$, which is an ordered triple. Still, as you point out, these sets are very similar, and in fact there is a canonical bijection between them, namely $$((a, b), c) \leftrightarrow (a, b, c).$$
