Is the Cartesian product of sets associative?

Question

Is it associative? In general sense, if we compare $A \times (B \times C)$ and $(A \times B) \times C$, then $(a,(b,c))$ does not equal $((a,b),c)$, but both of those pairs may be interpreted as one triplet $(a,b,c)$. Is it correct to do that and can we use associativity of Cartesian product in set theory problems?

Answer 1

Equality in $(A\times B) \times C=A\times (B\times C)$ holds if, and only if, at least one of the sets is empty. As mentioned already, there is a canonical isomorphism $(A\times B) \times C\to A\times (B\times C)$, mapping $((a,b),c)$ to $(a,(b,c))$. Many authors thus treat $\times $ as if it is an associative operation on sets, though it is not. However, the true reason why one can safely pretend $\times $ is associative and not get into any problems is due to coherence. As a warm-up, assume you have $127$ sets and you multiply them, using $\times $ in some way. You get an incredibly complicated set whose elements contain lots and lots of parenthesis in all sorts of places. You would like to say that this set is essentially just the set of tuples of length $127$ where the $k$-th coordinate is taken from the $k$-th set, but are you now really sure that's the case? The expressions can be so complicated that maybe it is now not so obvious anymore. And besides, do we really only care whether two sets admit a bijection between them in order to identify them? Of course not. So, what is going on here is that it is not so much the sets we should care about as much as it is the functions between them.

Consider again the canonicity of the functions used for the identification $(A\times B) \times C \cong A\times (B\times C)$ but now take four sets. When you have four sets you can multiply them together (in a given fixed order) in five different ways. These five different sets are, we would like to say, essentially the same, but, minding the above, that is not what we wish to say. We don't want to identify them, since they are different. What we want to know is that the canonical functions between them compose coherently. The precise meaning of that is a bit technical, and you may wish to read Mac Lanes's "Categories for the working mathematician" to properly understand coherence, but basically you will discover the definition yourself if you take four sets, multiply them to get five sets, place them at the vertices of a pentagon, connect the dots using the canonical maps, and claim that the different compositions along the perimeter are the same. The point then is Mac Lane's coherence theorem: starting with any finite number of sets, any two compositions of the canonical functions between one way to multiply the sets and another way to multiply the sets are the same.

So, we can safely pretend $\times $ is associative on sets because there are canonical maps between different choices which (and this is really important) always compose to give the same function when used on any number of sets, multiplies in any way you like.

An illustrative example where coherence fails for the 'wrong' choice of canonical maps is when you consider signed elements. Suppose that all your sets have elements, each of which is designated as either positive or negative, and that each element $x$ can change sign to $-x$. Now, you can map $A\times (B\times C)\to (A\times B)\times C$ by $(a,(b,c))\mapsto -((a,b),c)$. Mathematically, it's just as canonical as the other possibility. However, this one is not coherent (you can check that with the pentagon).

Answer 2

Set theory wise, no they are different sets due to being based on ordered pairs.

However in many contexts where one deals with triplets etc and higher, the grouping doesn't really matter so in those instances it is associative.

Answer 3

There is a canonical isomorphism between $A \times (B \times C)$ and $(A \times B) \times C$. They are different objects, but they behave in the same way, much as $D_6$ and $S_3$ are different groups but they behave in the same way.

Answer 4

The product construction is not associative. You're right that $(A\times B) \times C$ is a different set than $A\times (B \times C)$ (for nonempty $A,B,C$). Their members are of different shapes, or types. The two sets aren't literally identical (equal) — but they are equivalent, in a natural, or canonical way: the function $$ ((a,b),c)\mapsto (a, (b,c)) $$ is a bijection between the two sets which lets us convert between them and treat them as for many purposes interchangeable.

In basic set theory problems, the distinction might matter. However, they would probably indicate that it matters by using explicit parentheses.

Usually it doesn't matter, and then one writes $A\times B\times C$, indicating that the set will be treated as containing ordered triples with elements from $A,B,C$ in that order. We're using ordered pairs to represent, or implement, ordered triples. There are two ways to do so; each way implements access to e.g. the first element differently; but the truth or falsity of what we're really concerned with will be unaffected by the choice and its implementation details.

In practice, when 3 or more more sets are combined in a product, we think of its members as finite sequences, or tuples. We have certain requirements of tuples:

• a tuple $s$ has a length $\lvert s\rvert\in \Bbb N$
• for each $i, 0\le i<n$, there's an $i^{\text{th}}$ element $s_i$
• tuples are uniquely determined by their lengths and elements: if $s,t$ are tuples with $\lvert s\rvert =\lvert t\rvert$ and $(\forall i< \lvert s\rvert)\,s(i)=t(i)$, then $s=t$.

These requirements can be thought of as a "tuple interface", in programming parlance.

The sets obtained by repeating the $\times$ construction meet these requirements — they can be used to "implement the tuple interface". Given sets $A_0,\dotsc,A_k$, each way of fully parenthesizing $A_0 \times\dotsc\times A_k$ specifies an order in which $\times$ is performed. Each of these ways is a particular representation of $n$-tuples as nested pairs of ... possibly nested pairs of ... elements from $A_0,\dotsc,A_k$ — in other words, as labelled binary trees of a fixed shape. The tuples that we intend are the leaves of those trees, enumerated left to right.

Another definition of the product of $A_0,\dotsc,A_k$ dispenses with the nesting and implements finite sequences as functions: $$ \prod_{i\le k} A_i = \{t\mid \text{$t$ is a function, $dom(t)=\{0,\dots,k\}$, and $(\forall i\le k)\,t(i)\in A_i$}\}. $$

If $A_0 = A, A_1 = B$ and $A_2 = C$, $k=2$, of course this set is not the same as either $(A\times B) \times C$ or $A\times (B \times C)$. But again they're equivalent, interchangeable, via canonical bijections such as $$ ((a,b),c) \mapsto \{(0,a), (1,b), (2,c)\}\colon (A_0\times A_1) \times A_2 \to \prod_{i\le k} A_i $$

This definition of the product as a set of functions generalizes to arbitrary, possibly infinite families of sets: $$ \prod_{i\in I} A_i = \{t\mid \text{$t$ is a function, $dom(t)=I$, and $(\forall i\in I)\,t(i)\in A_i$}\}. $$ This allows constructions that can't be achieved by iterated pairing — for example, if $I=\Bbb N$.

Answer 5

There is an abstract notion of products in category theory. A category where every finite collection of objects has a product is called a cartesian category. In those categories (and Set is one of them) the product is associative. That means that you can identify the two different sets $A\times(B\times C)$ and $(A\times B)\times C$ in any discussion where isomorphism is accepted as synonymous with identity.