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.

  • $\begingroup$ 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))$ $\endgroup$ – 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})$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.