**Example 1.** The integers are denumerable. Here is one possible correspondence
between the integers and the natural numbers:

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, ...} | | | | | | | | | { 0, 1, -1, 2, -2, 3, -3, 4, -4, ...}

Notice that, given any natural number N, you can figure out what integer I it corresponds to, and vice versa:

**if** even(N) **then** I:=N/2 **else** I:=-((N-1)/2);

**if** I<0 **then** N:=(-2*I)+1 **else** N:=2*I;

Since we can put these two sets into a one-to-one correspondence, they must
have the same number of elements, namely, _{0}.

**Example 2.** There are as many odd natural numbers as there are even natural
numbers. To prove this, we note the following correspondence:

{ 1, 3, 5, 7, 9, ...} | | | | | { 2, 4, 6, 8, 10, ...}

**Example 3.** There are as many even natural numbers as there are numbers.

{ 1, 2, 3, 4, 5, ...} | | | | | { 2, 4, 6, 8, 10, ...}

Thus, "half of infinity is infinity." More precisely, _{0}/2=_{0}.

**Example 4.** _{0}-1
= _{0}. Proof:

{ 2, 3, 4, 5, 6, ...} | | | | | { 1, 2, 3, 4, 5, ...}

**Example 5.** The set of positive rational numbers (positive fractions) is
denumerable.

A set is denumerable if it *can* be put into a one-to-one correspondence with the
natural numbers. You can't prove anything with a correspondence that doesn't work. For
example, the following correspondence doesn't work for fractions:

{ 1, 2, 3, 4, 5, ...} | | | | | { 1/1, 1/2, 1/3, 1/4, 1/5, ...}

This correpondence doesn't work because there are fractions we never get to, e.g. 2/3. But here's a more complex correspondence that does work:

{ 1, 2, 3, 4, 5, ...} | | | | | { 1/1, 1/2, 2/1, 1/3, 2/3, ...}

This ordering comes from arranging the fractions in the order shown in the leftmost table below, then taking them in the order shown by the table at the right.

________________________ ____________________ | 1/1 1/2 1/3 1/4 ... | 1 2 4 7 ... | 2/1 2/2 2/3 2/4 ... | 3 5 8 12 ... | 3/1 3/2 3/3 3/4 ... | 6 9 13 18 ... | 4/1 4/2 4/3 4/4 ... | 10 14 19 24 ... | ... ... ... ... ... |... ... ... ... ...

Copyright © 1996 by David Matuszek

Last modified Mar 31, 1996