# Finding bijection between ordered n-tuple of integers and integers

I've got a question for an assignment, but I don't really understand the question. I have however thought of a strategy to solve it. I'm looking for an explanation of the question and feedback on my strategy for finding a bijection.

Question:

Let $$S = \{(a_1, a_2, . . . , a_n)| n \geq 1, a_i \in Z^{\geq 0} \text{ for } i = 1, 2, . . . , n, a_n \neq 0\}$$. Find bijection from set $$S$$ to set $$Z^+$$.

What I understand from the question is that $$S$$ is the set $$(a_1,a_2,...,a_n)|n \geq 1$$ and each element of that set, $$a_i$$, is an element of $$Z^{\geq 0}$$, which to me looks like $$S=Z$$. What I don't understand is what $$\text{ for } i = 1, 2, . . . , n, a_n \neq 0\}$$ means and how it relates to the problem.

My strategy for solving this problem is to create a function from $$f:S\rightarrow Z^+$$ and then to find the inverse function, then use the inverse function to find a bijection for an element of $$Z^+$$. Is that the best way to solve this?

Also thought about proving the cardinality, $$|S|=|Z^+|$$, and saying that implies that the sets are bijective, but I don't know if the tutor would accept that.

• What are $Z^+$ and $Z^{\geq 0}$? Commented Sep 22, 2019 at 3:52
• $Z^+$ are non-negative non-zero integers. I'm assuming $Z^{\geq 0}$ is just $Z$. Commented Sep 22, 2019 at 3:57
• $S$ is contained of $n$-tuples for a fixed number $n$, where the first $n-1$ entries are non-negative integers and only the $n$-th entry must be a positive integer. Commented Sep 22, 2019 at 4:06
• Possible duplicate of Defining a function with a bijection Commented Sep 22, 2019 at 4:07
• Also notice that for $n=1$ you really have $S = Z^+$, but for $n=2$ you have $S = Z^{\geq 0} \times Z^{+}$ and so forth for bigger $n$. Commented Sep 22, 2019 at 4:12

Hint

Finding a function between $$S$$ and $$Z^+$$ is not so difficult. But proving that it is bijection will be much more difficult if the map has not been correctly engineered.

A way is to proceed by induction on $$n$$. For $$n=2$$, this question will be useful. Based on the bijection $$f$$ for $$n=2$$, you can proceed from $$n$$ to $$n+1$$ using

$$f_{n+1}(a_1, \dots ,a_{n+1})=f_2(f_n(a_1, \dots, a_n),a_{n+1})$$

If you know the theorem of Cantor-Bernstein, then finding an injection from $$S$$ into $$Z^+$$ and one from $$Z^+$$ into $$S$$ will be sufficient.

Injection from $$Z^+$$ into $$S$$ is easy...

For an injection from $$S$$ into $$Z^+$$ consider $$f(a_1,\dots,a_n) =p_1^{a_1}, \dots p_n^{a_n}$$ where $$p_1,\dots, p_n$$ are différent prime integers.