Countably infinite

Reference mathematics

Something is countably infinite if a one to one mapping can be made between it and the integers or a subset of the integers.

For example, the even integers are countably infinite as displayed by the mapping:

• 0 maps to 0
• 2 maps to 1
• 4 maps to 2
• ...
• N maps to (N/2) where N is an [even number]?

Likewise, pairs of integers are countably infinite through the following mapping:

• (0,0) maps to 0
• (0,1) maps to 1
• (1,0) maps to 2
• (0,2) maps to 3
• (1,2) maps to 4
• (2,0) maps to 5
• ...
• (m,n) maps to 0.5*k*(k+1)+m, where k=m+n

Sometimes it is necessary to use more than one mapping. This is where you map the set you want to show as countably infinite to another set. You then map this other set to the natural numbers. For example, the Rational numbers can easily be mapped to (a subset of) the pairs of integers through p/q maps to (p,q).

---

There are other, uncountable infinites. It is easy to show, for instance, that the set of real numbers is not countably infinite, using Cantor's diagonal argument. The size of the countable infinite sets is the smallest infinity.