# Proving the existence of a Bijection between Cartesian Products of Sets by Induction

Prove by induction that for any sets $A_1, \ldots , A_n$, there is a bijection from $(((A_1 \times A_2) \times A_3) \times \ldots \times A_n)$ to $A_1 \times (A_2 \times ( \ldots (A_{n-1} \times A_n) \ldots ))$

I know that I have to start with a base case since it is by induction. By letting $n=3,$ then I have $(A_1 \times A_2) \times A_3 = A_1 \times (A_2 \times A_3)$ by associativity. For the inductive step, let $n=k$ so that we have $(((A_1 \times A_2) \times A_3) \times \ldots \times A_k)$ and we want to show that there is a bijection from this to $A_1 \times (A_2 \times ( \ldots (A_{k-1} \times A_k ) \ldots ) )$. But then couldn't I just claim to use associativity?

I can define a function $f: ((A_1 \times A_2) \times A_3) \to A_1 \times (A_2 \times A_3)$ by $f((a_1,a_2),a_3) = (a_1, (a_2,a_3))$ which seems to be the most intuitive way to begin.

Is this the proper way to proceed or am I doing something wrong? As always, any help is greatly appreciated.

• I don't think the cartesian product is associative, because $((a,b),c) (\in ((A_1 \times A_2) \times A_3) \neq (a,(b,c)) (\in A_1 \times (A_2 \times A_3))$ – user2103480 Jan 26 '15 at 20:42

It’s not in general true that $(A_1\times A_2)\times A_3=A_1\times(A_2\times A_3)$. Suppose, for instance, that $A_1=A_2=A_3=\{0\}$; then the only element of $(A_1\times A_2)\times A_3$ is $\big\langle\langle 0,0\rangle,0\big\rangle$, while the only element of $A_1\times(A_2\times A_3)$ is $\big\langle 0,\langle 0,0\rangle\big\rangle$, and

$$\big\langle\langle 0,0\rangle,0\big\rangle\ne\big\langle 0,\langle 0,0\rangle\big\rangle\;,$$

because $\langle 0,0\rangle\ne 0$.

What is true, and what you’re supposed to prove, is that there is a bijection $f$ between the Cartesian products $(A_1\times A_2)\times A_3$ and $A_1\times(A_2\times A_3)$. Suppose that $\big\langle\langle a_1,a_2\rangle,a_3\big\rangle\in(A_1\times A_2)\times A_3$, and you want to pick an element of $A_1\times(A_2\times A_3)$ to be $f\left(\big\langle\langle a_1,a_2\rangle,a_3\big\rangle\right)$; what is the most obvious choice? Remember, it has to be something of the form $\big\langle x,\langle y,z\rangle\big\rangle$, where $x\in A_1$, $y\in A_2$, and $z\in A_3$.

Once you’ve defined $f$, we can worry about how to proceed further.

Added: For the induction step, suppose that for any $n$ sets $A_1,\ldots,A_n$ you have a bijection from $((A_1 \times A_2) \times A_3) \times \ldots \times A_n$ to $A_1 \times (A_2 \times ( \ldots (A_{n-1} \times A_n) \ldots ))$, and you want to get one from $$(((A_1 \times A_2) \times A_3) \times \ldots \times A_n)\times A_{n+1}\tag{1}$$ to

$$A_1 \times (A_2 \times ( \ldots (A_{n-1} \times (A_n\times A_{n+1}) \ldots )))\;.$$

Let $B=A_n\times A_{n+1}$. Your induction hypothesis gives you a bijection from

$$(((A_1\times A_2)\times A_3)\times\ldots A_{n-1})\times B\tag{2}$$

to $$A_1\times(A_2\times(\ldots(A_{n-1}\times B)))=A_1 \times (A_2 \times ( \ldots (A_{n-1} \times (A_n\times A_{n+1}) \ldots )))\;,$$

so you’re done if you can find a bijection between $(1)$ and $(2)$. But you’ve essentially done that in the first part of this answer: if you let $C=((A_1\times A_2)\times A_3)\times\ldots A_{n-1}$, then $(1)$ is $(C\times A_n)\times A_{n+1}$, and $(2)$ is $C\times(A_n\times A_{n+1})$.

• Would the most obvious choice be $f((a_1,a_2),a_3) = (a_1,(a_2,a_3))$? – Jamil_V Jan 27 '15 at 3:53
• @Jamil_V: It would indeed. – Brian M. Scott Jan 27 '15 at 3:59
• Ok, so after defining this function, how would we proceed with the induction. Thank you for your assistance, it is truly appreciated. – Jamil_V Jan 27 '15 at 4:00
• @Jamil_V: You’re welcome. I’ve added most of what you need to the answer. – Brian M. Scott Jan 27 '15 at 4:14