Associativity of cartesian product and nested ordered n-tuples

for 3 sets $A,B,C$ is $A\times B \times C = A\times (B\times C) = (A\times B)\times C$ OR to be more specific, is the ordered pair $((a,b),c)=$ ordered triplet $(a,b,c)=$ ordered pair $(a,(b,c))$?

Wikipedia states-

in another article on Wikipedia (and many other e-books and pdfs on the web)-

I think the root of confusion is the nested ordered pairs-

is the ordered pair $((a,b),c)=$ ordered triplet $(a,b,c)=$ ordered pair $(a,(b,c))$?

Please help

Solution 1:

The ordered pairs $\big\langle\langle a,b\rangle,c\big\rangle$ and $\big\langle a,\langle b,c\rangle\big\rangle$ are not equal. Formally, an ordered pair $\langle x,y\rangle$ is the set $\big\{\{x\},\{x,y\}\big\}$, so

$$\big\langle\langle a,b\rangle,c\big\rangle=\left\langle\big\{\{a\},\{a,b\}\big\},c\right\rangle=\left\{\left\{\big\{\{a\},\{a,b\}\big\}\right\},\left\{\big\{\{a\},\{a,b\}\big\},c\right\}\right\}\;,\tag{1}$$

while

$$\big\langle a,\langle b,c\rangle\big\rangle=\left\langle a,\big\{\{b\},\{b,c\}\big\}\right\rangle=\left\{\left\{a\right\},\left\{a,\big\{\{b\},\{b,c\}\big\}\right\}\right\}\;.\tag{2}$$

As the second Wikipedia quotation says, $(A\times B)\times C$ and $A\times(B\times C)$ are equal if and only if at least one of $A,B$, and $C$ is empty, so that

$$(A\times B)\times C=\varnothing=A\times(B\times C)\;.$$

Note, however, that there is always a very natural bijection $h$ between $(A\times B)\times C$ and $A\times(B\times C)$, given by

$$h:(A\times B)\times C\to A\times(B\times C):\big\langle\langle a,b\rangle,c\big\rangle\mapsto\big\langle a,\langle b,c\rangle\big\rangle\;,$$

and in most settings it’s both harmless and very convenient to pretend that they’re the same set and ignore the technical, formal difference.

Whether either $\big\langle\langle a,b\rangle,c\big\rangle$ or $\big\langle a,\langle b,c\rangle\big\rangle$ is equal to $\langle a,b,c\rangle$ depends on how the ordered triple has been defined. It is perfectly possible to define ordered $n$-tuples as in the first Wikipedia quotation; if one does, then by definition

$$\langle a,b,c\rangle=\big\langle\langle a,b\rangle,c\big\rangle\;.$$

However, for $n>2$ one can also define ordered $n$-tuples to be functions whose domain is $\{0,1,\ldots,n-1\}$. If we adopt that definition, then

$$\langle a,b,c\rangle=\{\langle 0,a\rangle,\langle 1,b\rangle,\langle 2,c\rangle\}\;,$$

the function that sends $0$ to $a$, $1$ to $b$, and $2$ to $c$. Formally this is

$$\left\{\big\{\{0\},\{0,1\}\big\},\big\{\{1\},\{1,b\}\big\},\big\{\{2\},\{2,c\}\big\}\right\}\;,$$

something quite different from the sets in $(1)$ and $(2)$. Once again, though, in most settings it’s a matter of indifference which technical definition of ordered $n$-tuple we use: the important thing is that an ordered $n$-tuple is an object with $n$ identifiable components, any of which may be equal, whose positions in the object are specified.

Solution 2:

Brian M. Scott's answer is 100% correct, at least from the viewpoint of material set theory, which is perhaps the currently dominant paradigm. Let me briefly describe a different viewpoint, namely the structural viewpoint.

According to structuralist philosophy, the appropriate question isn't whether or not the set $(A \times B) \times C$ is equal to $A \times (B \times C)$. Rather, we should ask:

1. ("Weak Sameness") Is it true that for all sets $A,B$ and $C$, the sets $(A \times B) \times C$ and $A \times (B \times C)$ are isomorphic?

2. ("Strong Sameness") Is it true that the functor $\lambda A,B,C : \mathbf{Set},(A \times B) \times C$ is isomorphic to the functor $\lambda A,B,C : \mathbf{Set},A \times (B \times C)$?

The answer to the 1st question is clearly yes, using the function Brian denotes $h$ in his answer. In fact, the answer to the 2nd question also a resounding "YES!"; you can try to prove it yourself, if you want, or else try looking up the proof in any basic category theory text. If you're interested in this viewpoint, perhaps check out Sets for mathematics by Lawvere/Rosebrugh, and/or Categories for the Working Mathematician by Saunders Mac Lane.