Tell people there

On Infinity 4 - Countable Sets
Tue, 17 Jan 2012 20:15:00 GMT

We have seen a basic introduction to infinity and its definition in part 1 of this series, and in part 2, we have seen that infinitary processes might have a finite outcome. In part 3, we have seen a lot of nice examples getting deeper into the topic of infinite curves and planes. However, we moved away from the actual question about how many elements a set has, as the curves are more demonstrative in the beginning. With this post, we want to turn back to this question again.

Let us recall how we defined infinity in part 1: A set is infinite if and only if there is a bijection into a proper subset.

While it is pretty clear that there are multiple finite sets with different numbers of elements, the question whether there are infinite sets that contain more elements than \mathbb{N} has not been answered yet. And while it is pretty clear that for two finite sets, we can always say which of them is greater, this is not clear when talking about infinite sets. The definition is pretty obvious: If there is a bijection from a set A into a subset of B, then A has more or equally many elements as B, we will denote this by |A|\le |B|.
So as said, the first question which arises is, whether two sets are always comparable. This follows directly from the well-ordering theorem, but we will not discuss this proof here, since it is sophisticated. We just keep in mind that for any two sets A and B, we have |A|\le |B| or |B|\le |A|.

Let us denote by |A|=|B| that the sets A and B contain equally many elements, that is, there is a bijection between them. Then the obvious question is whether |A|\le |B| and |B|\le |A| implies |A|=|B|. Do not let yourself confuse by the notation: This is not clear! Essentially, the question is whether when we have a bijection from A to a subset of B and a bijection from B into a subset of A, we also have a bijection between A and B.
By the Cantor-Bernstein-Theorem, this holds, but we will not discuss this here, and just accept that it works for all sets we will consider.

Now, when thinking about the "number" of Elements of the set \mathbb{N}_1 of positive integers, two obvious questions arise: Whether there is an infinite set smaller than \mathbb{N}_1, and whether there is an infinite set greater than \mathbb{N}_1. For the first question, it is sufficient to prove that every infinite subset of \mathbb{N}_1 has a bijection into \mathbb{N}_1. This can be done by the minimum principle defined in part 1, and is left to the interested reader. So indeed, \mathbb{N}_1 is the "smallest" infinite set, in the sense that every other infinite set has at least as much elements as \mathbb{N}_1.

In part 1, we have already seen, that the first obvious "larger" set, the set \mathbb{Z} of integers, is not larger than \mathbb{N}_1: The mapping \varphi(n)=(-1)^n\lceil\frac{n}{2}\rceil, that is, \varphi(0),\varphi(1),\varphi(2),\varphi(3),\varphi(4),\ldots is 0,-1,1,-2,2,-3,3,-4,4,\ldots, is a bijection. So in fact, there are as many non-negative integers, as there are integers at all.

The next obvious candidate is the set \mathbb{N}_0\times\mathbb{N}_0 of pairs (a,b) of nonnegative integers. You can imagine them as points of a "grid":


The question can now be seen more geometrical: Is it possible, to arrange these points on a curve? And of course, it is:



We get the sequence (0;0), (0;1), (1;0), (2;0), (1;1), (0;2), \ldots. This sequence is defined by the Cantor-Pairing-Function \pi. It is a bijection, and we call its inverse for the right side \pi_R and its inverse for the left side \pi_L, thus, \pi(\pi_R(a),\pi_L(a))=a.

So, \mathbb{N}_0\times\mathbb{N}_0 is not larger than \mathbb{N}_1. In fact, therefore, trivially, also the set of triples, quartuples, etc., of natural numbers are not larger than the set of natural numbers, as we can encode for example triples by (1;2;3)=(1;(2;3)).

So, the next obvious candidate would be to unite all of these sets, gaining the set \mathbb{N}_1^\omega of finite sequences of natural numbers. As you might expect, this set is also countable, and there is a more general theorem that states that every union of countably many countable sets is countable itself, which would hold here. But in this case, we can show it more directly, by giving a bijection. Firstly, let \pi_n:\mathbb{N}_1^n\rightarrow\mathbb{N}_1 be the bijection from the n-tuples into the natural numbers (where \pi_1(x)=x), which exists as shown above. Then define

\pi_\omega(x_1,\ldots,x_n)=\pi(n,\pi_n(x_1,\ldots,x_n))

Its inverse is given by

\pi_\omega^{-1}(x)=\pi_{\pi_{L}(x)}^{-1}(\pi_R(x))=\left\{\begin{array}{cl} \pi_{R}(x) & \mbox{ for } \pi_{L}(x)=1 \\ \pi_2^{-1}(\pi_R(x)) &\mbox{ for } \pi_{L}(x)=2 \\ \pi_3^{-1}(\pi_R(x)) &\mbox{ for } \pi_{L}(x)=3 \\ \pi_4^{-1}(\pi_R(x)) &\mbox{ for } \pi_{L}(x)=4 \\ \cdots & \cdots \end{array}\right.


As this looks rather theoretic and confusing, here is a Java-Program which actually does this (I hope):

public class CantorStuff {

    public static int cantorPair (int x, int y) {
    x--; y--;
    return (x+y)*(x+y+1)/2+y+1;
    }

    public static int[] cantorPairToNumbers (int z) {
    z--;
    int w = (int) Math.floor((Math.sqrt(8*z+1)-1)/2);
    int t = (w*w+w)/2;
    int y = z-t;
    return new int [] { w-y+1, y+1 };
    }

    public static int sequenceToNum (int[] seq) {
    int ret = seq[seq.length - 1];
    for (int i = seq.length - 2; i >= 0; i--) {
        ret = cantorPair(seq[i], ret);
    }
    return cantorPair(seq.length, ret);
    }

    public static int[] numToSequence (int num) {
    int[] ctpn = cantorPairToNumbers(num);
    int[] ret = new int[ctpn[0]];
    for (int i = 0; i < ret.length - 1; i++) {
        ctpn = cantorPairToNumbers(ctpn[1]);
        ret[i] = ctpn[0];
    }
    ret[ret.length - 1] = ctpn[1];
    return ret;
    }

    public static void main (String[] args) {

    if (args[0].equals("num")) {
        int num = Integer.parseInt(args[1]);
        int[] seq = numToSequence(num);
        for (int i = 0; i < seq.length; i++) {
        System.out.print(seq[i] + " ");
        }
        System.out.println("");
    } else if (args[0].equals("seq")) {
        int len = args.length - 1;
        int[] seq = new int[len];
        for (int i = 1; i <= len; i++) {
        seq[i-1] = Integer.parseInt(args[i]);
        }
        System.out.println(sequenceToNum(seq));
    }
    }
}


So in fact, not even the set of finite sequences of natural numbers is larger than the set of natural numbers.

Ok, the next canonical candidate would be the set of rational numbers, \mathbb{Q}. But every rational number is of the form \pm\frac{a}{b},a,b\in\mathbb{N}, where a and b are coprime, and this form is unique except for 0. That is, \mathbb{Q} can be regarded as a subset of \{+,-\}\times\mathbb{N}_0\times\mathbb{N}_1, which means that it is, actually, countable.

Ok, the rationals are not larger than the set of natural numbers. But now, we finally approach to a set which is actually larger: The set \mathbb{R} of real numbers.

In part 1 we have seen the following bijection, which makes it sufficient to show that there is no bijection f:\mathbb{N}\rightarrow]0;1[, because the connection of two bijections is a bijection again, obviously.



So assume there was a bijection f:\mathbb{N}\rightarrow]0;1[. Every element of ]0;1[ has a decimal representation, say, f(n)=\sum\limits_{i=1}^\infty 10^{-i}a_{ni}= 0.a_{n1}a_{n2}a_{n3}\ldots with a_{ij}\in\{0,1,2,3,4,5,6,7,8,9\}, and we may assume that, if possible, this representation is stationary, that is, ends with infinitely many zeroes (we must assume this, since for example 0.1=0.0\overline{9} as we have seen in part 1).

Now define for all i\in\mathbb{N}

b_i = \left\{\begin{array}{cl} 1 & \mbox{ for } a_{ii}=0 \\ 0 & \mbox{ otherwise} \end{array}\right.

Then there is a real number b:=\sum\limits_{i=1}^\infty 10^{-i}b_i=0,b_0b_1b_2\ldots, and this real number is distinct from all f(j),j\in\mathbb{N}. So, f cannot be surjective. Contradiction.

The same argument also proves that there is no surjective such f, that is, \mathbb{R} contains strictly more elements. The powerset \mathfrak{P}(\mathbb{N}), the set of subsets of \mathbb{N}, is another example, and the proof for this is somewhat similar: Considering a function f:\mathbb{N}\rightarrow\mathfrak{P}(\mathbb{N}), the set \{i\in\mathbb{N}|i\not\in f(i)\} is not in the range of f (proof: exercise!), so f cannot be surjective.

Now of course, the question arises whether \mathfrak{P}(\mathbb{N}) is larger or smaller than \mathbb{R}. They are of equal cardinality, and it is possible to give a bijection, but it is rather sophisticated, so this is left as an exercise for the interested reader.
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)