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.

The set $S$ of all pairs of integers can be represented as $\{i \ | \ i \in \mathbb{Z} \} \times \{j\ | \ j \in \mathbb{Z}\}$. In other words, all coordinates on the cartesian plane where $x, y$ are integers.

I also know that a set is countable when $|S|\leq |\mathbb{N}^+|$. I attempted to map out a bijective function, $f : \mathbb{N}^+ \rightarrow S$.

$1 \rightarrow (1,1) \\ 2 \rightarrow (1,2)\\ 3 \rightarrow (1,3) \\ \quad \vdots $

I determined from this that the natural numbers can only keep up with $(1,*)$. But there is the ordered pairs where $x=2,3,4,\cdots$ not to mention the negative integers. In other words, $|S|\geq |\mathbb{N}^+|$ and therefore $S$ is not countably infinite.

Is this correct? (I don't think it is... Something to do with my understanding of infinite sets)

share|improve this question
    
As Brian mentions "Cantor's pairing function" will do the job directly. However, it may be easier to understand: First prove that the union of countably many countable sets is countable (See Cantor's first diagonal argument). Then we can write $\mathbb{N}\times\mathbb{N} = \bigcup(\mathbb{N}\times\{n\})$ and hence the product is countable –  Deven Ware Aug 28 '12 at 4:24
    
Perhaps you mean natural numbers, rather than integers ($\mathbb N$ usually denotes natural numbers while $\mathbb Z$ denotes integers)? Either way, the set of pairs of natural numbers/integers is countably infinite; just because the function you found is not a bijection does not mean no bijection exists. –  Alex Becker Aug 28 '12 at 4:26
    
yes, i meant integers. sorry about that –  James Aug 28 '12 at 4:29
add comment

2 Answers

up vote 2 down vote accepted

Natural Numbers: There are many pairing functions that map $\mathbb{N}\times \mathbb{N}$ bijectively to $\mathbb{N}$. A simple example is the mapping $f$ such that $f(a,b)=2^{a-1}(2b-1)$. For every positive integer $y$ can be uniquely expressed as a power of $2$ times an odd integer.

Integers: If you want a mapping $g(x,y)$ that maps $\mathbb{Z}\times \mathbb{Z}$ bijectively to $\mathbb{N}$, it is simplest to split the work into two parts.

Let $\phi$ be any mapping that maps $\mathbb{Z}$ bijectively to $\mathbb{N}$. For a concrete example of such a mapping, let $\phi(t)=2t+2$ if $t \ge 0$, and let $\phi(t)=-(2t+1)$ if $t \lt 0$. The non-negative integers are sent to the even integers $\ge 2$, and the negative integers are sent to the positive odd integers.

Then the mapping $g(x,y)=f(\phi(x),\phi(y))$ works, where $f$ is any bijective map from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$. For example, we can use the mapping $f$ of the first paragraph, or the Cantor pairing function.

Remark: For most purposes, there is no particular virtue in having an explicit bijection, as long as we can prove that a bijection exists.

share|improve this answer
add comment

You simply haven’t yet found a function that works. One that does is the Cantor pairing function, which is described quite well in the Wikipedia article to which I linked.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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