Countably Infinite

CountablyInfinite is a term used in mathematics, see for example http://mathworld.wolfram.com/CountablyInfinite.html

We want to examine the cardinality of infinite sets, namely the set of natural numbers N = {0, 1, 2, 3, ...}, the set of integers Z = {..., -3, -2, -1, 0, 1, 2, 3, ...} and the set of pairs of natural numbers N*N = { (0,0), (0,1), (1, 0), (0, 2), ...}

First of all, we say that the cardinality of N is infinite, since certainly no finite number can describe it accurately. We also say that it is countably infinite, since there is a way to list (count) them and eventually come to every predefined number: 0, 1, 2, 3, 4, 5, ... (The experiment is to say a number and then to wait until it appears in the list. This is always finite.) We now say that an infinite set S is countably infinite if this is possible. We know by now that there are countably infinite sets; N is an example. It is not clear whether there are infinite sets which are not countable, but this is indeed the case, see UncountablyInfinite.

We now wonder if Z is countable. Indeed it is: if we list Z by the following order we eventually come to every number: Z = {0, 1, -1, 2, -2, 3, -3, 4, -4, ...} Thus, we see that Z is countable, and we say that it has the same cardinality as N.

We now wonder in N*N is countable, and indeed, the following list contains every pair of the set: N*N = { (0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2) ... }; an alternative representation of this is to give every point (i,j) the index where it appears on the list. This will look like this:

 .
 .
 .
 6 |
 5 |
 4 |11
 3 | 7   12
 2 | 4    8   13
 1 | 2    5    9   14
 0 | 1    3    6   10   15
 -------------------------
     0    1    2    3    4 

We see that every point is eventually reached. Thus N*N is countable. The reader can now convince himself that Z*Z and (a bit more difficult) the set of rational numbers Q = { p/q : p and q are contained in Z} are countable.

---

CategoryMath