Associativity of Cartesian Product

Theorem

Let $A, B, C$ be non-empty sets.

Then:

$A \times \left({B \times C}\right) \ne \left({A \times B}\right) \times C$

where $A \times B$ is the cartesian product of $A$ and $B$.

Intuitive Proof

By definition:

$A \times B = \left\{{\left({a, b}\right): a \in A, b \in B}\right\}$

that is, the set of all ordered pairs $\left({a, b}\right)$ such that $a \in A$ and $b \in B$.

Now:

• Elements of $A \times \left({B \times C}\right)$ are in the form $\left({a, \left({b, c}\right)}\right)$;
• Elements of $\left({A \times B}\right)\times C$ are in the form $\left({\left({a, b}\right), c}\right)$.

So for $A \times \left({B \times C}\right) = \left({A \times B}\right)\times C$ we would need to have that $a = \left({a, b}\right)$ and $\left({b, c}\right) = c$.

This can not possibly be so, except perhaps in the most degenerate cases.

So from the strict perspective of the interpretation of the pure definitions, $A \times \left({B \times C}\right) \ne \left({A \times B}\right) \times C$.

$\blacksquare$

Formal Proof

Assign to every set $X$ the following number $n \left({X}\right) \in \N$:

$\displaystyle n(X) = \begin{cases} 0 & : X = \varnothing \\ 1 + \max_{Y\in X} \ n(Y) & : \text{ otherwise} \end{cases}$

The Axiom of Foundation implies that, for every $X$, $n(X)<\infty$.

Now let $a \in A$ be such that $\displaystyle n \left({a}\right) = \min_{b \in A} \ n \left({b}\right)$.

Suppose $\exists a' \in A, b \in B: a = \left({a', b}\right)$, that is, $a$ equals the ordered pair of $a'$ and $b'$.

Then it follows that:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle n \left({a}\right)\)	\(=\)	\(\displaystyle n \left({ \left\{ { \left\{ {a'}\right\}, \left\{ {a', b}\right\} }\right\} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of ordered pair
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 1 + \max \left({n \left({ \left\{ {a'}\right\} }\right), n \left({ \left\{ {a', b}\right\} }\right) }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of $n$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle n \left({ \left\{ {a', b}\right\} }\right)\)	\(\ge\)	\(\displaystyle n \left({ \left\{ {a'}\right\} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Maximum of Subset
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 1 + n \left({a'}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of $n$
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle n \left({a}\right)\)	\(\ge\)	\(\displaystyle 2 + n \left({a'}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

That is, $n \left({a'}\right) < n \left({a}\right)$, contradicting the assumed minimality of the latter.

Therefore, $a \notin A \times B$, and hence $A \nsubseteq A \times B$.

It follows that we cannot have $A \times \left({B \times C}\right) \ne \left({A \times B}\right) \times C$ from Equality of Cartesian Product.

$\blacksquare$

Comment

Despite this result, the cartesian product of three sets is usually just written $A \times B \times C$ and understood to be the set of all ordered triples.

That is, as the set of all elements like $\left({a, \left({b, c}\right)}\right)$.

From Cardinality of Cartesian Product, we have that:

$\left|{A \times \left({B \times C}\right)}\right| \sim \left|{\left({A \times B}\right)\times C}\right|$

and so:

$A \times \left({B \times C}\right) \sim \left({A \times B}\right)\times C$

where $\sim$ denotes set equivalence.

So it matters little whether $A \times B \times C$ is defined as being $A \times \left({B \times C}\right)$ or $\left({A \times B}\right)\times C$, and it is rare that one would even need to know.

When absolute rigour is required, the cartesian product of more than two sets can be defined using ordered $n$-tuples or, even more generally, by indexed sets.

See also

• Equality of Cartesian Products

Sources

• J.A. Green: Sets and Groups (1965)... (previous)... (next): Exercise $1.8$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 9 \beta$