# Showing two functions are bijections

I would like to verify my proofs for the following problems.

(a) Show that for $n > 1$ there is a bijective correspondence of $A_1 \times A_2 \times ... \times A_n$ with $(A_1 \times A_2 \times ... \times A_{n-1}) \times A_n$.

Let $f: A_1 \times A_2 \times ... \times A_n \to (A_1 \times A_2 \times ... \times A_{n-1}) \times A_n$ defined by $f((a_1,a_2,...,a_n))=((a_1,a_2,...,a_{n-1}),a_n)$.

One-to-one: Let $(a_1,a_2,...,a_n)$ and $(a_1^{'},a_2^{'},...,a_n^{'})$ be in $A_1 \times A_2 \times...\times A_n$. The $f((a_1,a_2,...,a_n))=f((a_1^{'},a_2^{'},...,a_n^{'})) \Rightarrow ((a_1,a_2,...,a_{n-1}),a_n)=((a_1^{'},a_2^{'},...,a_{n-1}^{'}),a_n^{'}) \Rightarrow (a_1,a_2,...,a_n)=(a_1^{'},a_2^{'},...,a_n^{'})$. Hence this is one-to-one.

Onto Let $((a_1,a_2,...a_{n-1}),a_n) \in (A_1 \times A_2 \times ... \times A_{n-1}) \times A_n$. Then there exists $(a_1,a_2,...,a_n) \in A_1 \times A_2 \times ... \times A_n$ such that $((a_1,a_2,...a_{n-1}),a_n)=f((a_1,a_2,...,a_n))$.

(b) Given the indexed family $\{A_1,...\}$, let $B_i=A_{2i-1} \times A_{2i}$ for each positive integer $i$. Show that there is a bijective correspondence between $A_1 \times A_2 \times ...$ with $B_1 \times B_2 \times...$.

Let $f:A_1 \times A_2 \times ... \to B_1 \times B_2 \times...$ defined by $f((a_1,a_2,...))=((a_1,a_2),(a_3,a_4),...)$

One-to-one: Let $(a_1,a_2,...)$ and $(a_1^{'},a_2^{'},...)$ be elements of $A_1 \times A_2 \times ....$. Then $f((a_1,a_2,...))=f((a_1^{'},a_2^{'},...)) \Rightarrow ((a_1,a_2),(a_3,a_4),...)=((a_1^{'},a_2^{'}),(a_3^{'},a_4^{'}),...)\Rightarrow (a_1,a_2,...)=(a_1^{'},a_2^{'},...)$. Hence one-to-one.

Onto: Let $((a_1,a_2),(a_3,a_4),...)$ be an element of $B_1 \times B_2...$. Then there exists an $(a_1,a_2...) \in A_1 \times A_2 \times A_3....$ such that $((a_1,a_2),(a_3,a_4),...)=f( (a_1,a_2...))$. Hence onto.

-
Yes, those things are so easy. – Hagen von Eitzen Jan 24 '13 at 14:00
So they are correct? It seems like I'm just restating definitions. – emka Jan 24 '13 at 14:17

First of all, regarding the unhelpful comment: "those things are so easy"; this strikes me as presumptuous; how "easy" the tasks at hand are is a matter of experience.

The questions posted (or the request for verification of the work) are perfectly appropriate questions to post here: For students first encountering proof methods, and/or definitions of onto, one-to-one functions, and/or Cartesian Products of sets, the exercises are aimed at helping to develop facility with the material and with proofs.

So emka, your request for verification of your work is perfectly welcome here; I appreciate the effort you've shown. And yes, emka, your proofs are correct: in proofs like this, it is a matter of letting the definitions do the work, and it's clear you understand those definitions and how to utilize them in a proof. Many proofs can be proven simply by "unpacking" definitions. And since, in cases like this, it may seem "too easy" or "too obvious" (perhaps leading to self-doubt) -- is simply due to the fact that the statements to prove follow directly from the definitions.

But these types of problems are often exercises in making sure students understand what being "one-to-one" and "onto" require of function, and or, understanding what cartesian products of sets are.

That said, your work is just fine! You clearly have a grasp of the material.

-
Neat explanation! ++ – Babak S. Jan 24 '13 at 19:24
Just for emphasis, the technique of unpacking/packing definitions is very useful :) – Musa Al-hassy Jun 27 '14 at 22:37