Construct a bijection between $\mathbb{Z}^+\times \mathbb{Z}^+$ and $\mathbb{Z}^+$ [duplicate]

Solution 1:

Yes, it is countably infinite. The basic idea is to visualise $\mathbb{Z}^+ \times \mathbb{Z}^+$ as written out in an infinite table, and then let the enumeration weave through the table, avoiding taking any "infinite paths is any one direction."

As an example, notice that for any $n > 1$ there are only finitely many pairs $(i,j) \in \mathbb{Z}^+ \times \mathbb{Z}^+$ such that $i + j = n$ (in fact, there are exactly $n-1$ many of these). So our enumeration can begin by listing out all those pairs $(i,j)$ with $i+j = 2$ (that is, begin with $(1,1)$). The next $3-1=2$ spots will list all those pairs which sum to $3$. After this we take all those that sum to $4$. then $5$. etc.

Added due to comments below

The way to look at this is as follows. I am trying to describe what a bijection $f : \mathbb{Z}^+ \to \mathbb{Z}^+ \times \mathbb{Z}^+$ might look like. I am going to use the fact that for all $n > 1$ there are exactly $n-1$ pairs $(i,j)$ with the property that $i+j = n$. With this in mind, I can split up the positive integers into different groupings. The first grouping consists of $1$ by itself. The second grouping is $2,3$. The third grouping is $4,5,6$; the fourth $7,8,9,10$. And so on. Essentially, the $n$th grouping consists of the $n$ least positive integers that haven't been yet assigned to a grouping.

Instead of giving a specific formula, I just stipulate that for each $n$, if you consider the values of $f$ taken on the individual numbers of the $n$th grouping, this results in exactly all those pairs $(i,j)$ where $i+j = n+1$.

As an example, $f$ may look like this on the first four groupings:

• $f(1) = (1,1)$. (Actually, this is the only possibility.)
• $f(2) = (1,2), f(3) = (2,1)$.
• $f(4) = (2,2), f(5) = (3,1), f(6) = (1,3)$.
• $f(7) = (2,3), f(8) = (3,2), f(9) = (1,4), f(10) = (4,1)$.

And we continue like this for every grouping.

Such a function will be bijective because of the following:

• If $f(k) = (i,j) = f(\ell)$, then it must be that $k , \ell$ belong to the same grouping (in fact, they belong to the $(i+j-1)$th grouping). However since the $i+j-1$ numbers from this grouping get mapped by $f$ onto the $i+j-1$ pairs whose coordinates sum to $i+j$, it follows that no pair can be repeated. (This uses the fact that if we have finite sets $A,B$ of the same size, then a function $f:A \to B$ is one-to-one if and only if it maps $A$ onto $B$.)
• Given any $(i,j)$ we know that the numbers in the $(i+j-1)$th grouping are mapped by $f$ onto the set of all pairs whose coordinates sum to $i+j$; in particular, $f(k) = (i,j)$ for one of the numbers $k$ in this grouping.

Resuming original response

(This is by no means the only way to do this.)

Another method for showing the countability of $\mathbb{Z}^+ \times \mathbb{Z}^+$ replies on the fact that every subset of a countable set is countable. With this in mind, we can define a function $f : \mathbb{Z}^+ \times \mathbb{Z}^+ \to \mathbb{Z}^+$ by $f(i,j) = 2^i3^j$. It is easy to show that $f$ is one-to-one, and is therefore a bijection between $\mathbb{Z}^+ \times \mathbb{Z}^+$ and some subset of $\mathbb{Z}^+$. Since this subset must be countable, so, too, is $\mathbb{Z}^+ \times \mathbb{Z}^+$. (This method scales up quite nicely, and can even be used to show that the family of all finite sequences in $\mathbb{Z}^+$ is countable.)

Solution 2:

Let $g(x,y)=2^{x-1}(2y-1)$. The fact that $g(x,y)$ is a bijection follows from the fact that any positive integer can be uniquely written as a power of $2$ times an odd number. The power of $2$ may be $2^0$; that is why we used $2^{x-1}$.

Solution 3:

I believe the bijection you are looking for is:

$f(i,j) = \frac{(i+j-1)(i+j-2)}{2} + i$

EDIT: consider first all pairs for which $i+j = k$. for each $k > 1 \in\Bbb{N}$, there are $k-1$ such pairs. for any two such pairs $(i,j)$ and $(i',j')$, if $f(i,j) = f(i',j')$, we have:

$\frac{(k-1)(k-2)}{2} + i = \frac{(k-1)(k-2)}{2} + i'$, so $i = i'$ and thus $j = k - i = k - i' = j'$.

Note that for a given $k$, $\frac{(i+j-1)(i+j-2)}{2} + i \geq \frac{(i+j-1)(i+j-2)}{2} + 1 = 1+\sum_{i = 1}^{k-2} i$,

and that $\frac{(i+j-1)(i+j-2)}{2} + i \leq \frac{(i+j-1)(i+j-2)}{2} + k-1 = \sum_{i = 1}^{k-1} i$.

This means that pairs corresponding to different $k$'s must be distinct pairs. So f is injective.

On the other hand, every $n \in \Bbb{N}$ lies between $\sum_{i=1}^{k-2} i$ and $\sum_{i=1}^{k-1} i$ for some $k > 1$, and there are $k-1$ such natural numbers. Since f takes on these $k-1$ distinct values for each $k$, we conclude that f is surjective, as well, since $f(1,1) = 1$.

Solution 4:

Yes, the set is countable. This can be seen as follows: Enumerate $\mathbb Z^+\times\mathbb Z^+$ as $(1,1)$, $(1,2)$, $(2,1)$, $(3,1)$, $(2,2)$, $(1,3)$, and so on (draw a picture). (I will not write out an explicit formula for this.) Map 1 to the first pair in the sequence, $2$ to the second and so on. This is a bijection between $\mathbb Z^+$ and $\mathbb Z^+\times\mathbb Z^+$.

Also, this was discussed here: Bijecting a countably infinite set $S$ and its cartesian product $S \times S$