Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Bijecting a countably infinite set $S$ and its cartesian product $S \times S$
The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable

I wanna know if $\mathbb{Z^+}\times \mathbb{Z^+}$ is countably infinite and how should one construct a bijection and check if it is a bijective function

share|improve this question
5  
$$\color{red}{(1,1)},\\ \color{green}{(1,2), (2,1)}, \\\color{blue}{(1,3), (2,2), (3,1)},\\ \cdots$$ –  user2468 Mar 15 '12 at 6:33
    
As i remember,An infinite set A is countably infinite if A<->$\mathbb{Z^+}$ Which are integer only, how to show there is a bijection to $\mathbb{Z^+}$?? –  Mathematics Mar 15 '12 at 6:38
    
The formula is, for example, here: math.stackexchange.com/a/16615/2468 –  user2468 Mar 15 '12 at 6:43
    
i don't quite get why it is a bijection, after all, $Z^+$ is only a integer and $Z^+\times Z^+$ is coordinates –  Mathematics Mar 15 '12 at 6:47
1  
Elements of $\mathbb{N} \times \mathbb{N}$ are pairs of the form $(x,y)$. Each pair can be encoded as a unique natural number, for example, $n = 2^x 3^y.$ By the fundamental theorem of arithmetic this factorization in unique. More here from a previous question on math.SE –  user2468 Mar 15 '12 at 6:53
show 5 more comments

marked as duplicate by t.b., Asaf Karagila, Sivaram Ambikasaran, Jonas Teuwen, anon Mar 15 '12 at 12:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4 Answers

up vote 4 down vote accepted

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.)

share|improve this answer
    
for the first example, how come it is a bijection? Let say if we take n=3,then there is 2 possible paires,1+2 and 2+1 , but a function cannot map 3 to 2 distinct element in $Z^+ \times Z^+$ is it still consider to be bijection or even a function, and how should we make use of the example you suggest to construct a bijection????? –  Mathematics Mar 15 '12 at 7:20
    
@Mathematics: I think you slightly misinterpreted what I meant. If $f$ is the bijection we are trying to construct from $\mathbb{Z}^+$ onto $\mathbb{Z}^+ \times \mathbb{Z}^+$, then $f(1) = (1,1)$, and $f(2), f(3)$ will together list all those $(i,j)$ where $i+j=3$, and then $f(4),f(5),f(6)$ will together list all those $(i,j)$ where $i+j = 4$, and then $f(7),f(8),f(9),f(10)$ will together list all those $(i,j)$ where $i+j = 5$, and we continue like this ad infinitum. –  Arthur Fischer Mar 15 '12 at 7:42
    
but i think f(3) can only map to one element in $Z^+\times Z^+$ only if it is a function, (1,2) and (2,1) are 2 different element, how can f(3) list all (i,j) –  Mathematics Mar 15 '12 at 9:57
    
@Mathematics: I still think there is some sort of miscommunication going on. I have attempted to give a "higher level" view of a common approach (basically the same as in David Wheeler's answer). I have apparently failed at this. I will attempt to edit my answer above. –  Arthur Fischer Mar 15 '12 at 11:57
    
I find your answer quite satisfying. +1. –  David Wheeler Jun 14 '12 at 19:06
add comment

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}$.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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$

share|improve this answer
    
What do you mean by the dirst pair of sequences? –  Mathematics Mar 15 '12 at 6:40
    
The first pair in the sequence $(1,1),(1,2),(2,1),\dots$. –  Stefan Geschke Mar 15 '12 at 10:02
add comment

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