In my last post I introduced the notion of the size of an infinite set and proved two of the fundamental theorems about them.
In particular I pointed out that infinite sets could be the same size as proper subsets of themselves, and that they were strictly smaller than power sets of themselves.
One of the reasons why the fact that there are different sizes of infinity is a little surprising is that it turns out that a lot of things you’d think of as being different sizes are actually the same size.
This post is mostly worked examples of that. Along the way I’ll also use these examples to introduce some of the basic ideas of cardinal arithmetic, but this is mostly about showing how some of this works in practice.
A piece of notation: The set of real numbers is denoted \(\mathbb{R}\), the set of rational numbers \(\mathbb{Q}\) (a rational number is anything that can be represented as \(\frac{m}{n}\) for integers n\) and the set of integers \(\mathbb{Z}\). I’m not going to attempt to give a formal definition of the real numbers here, but I also shouldn’t rely on anything too surprising about them.
How large are these sets? They’re the same size as the two main sets we’ve already studied.
- \(\mathbb{Z} = \aleph_0\)
- \(\mathbb{Q} = \aleph_0\)
- \(\mathbb{R} = 2^{\aleph_0}\)
In order to prove the first two, we’re first going to look at a slightly different set. Consider \(\mathbb{N}^2\), the set of ordered pairs of natural numbers (e.g. \((1, 2)\), \((7, 3)\), etc). How large is this set?
In fact, \(|\mathbb{N}^2| = \aleph_0\).
Why? Well, certainly \(|\mathbb{N}^2| \geq \aleph_0\), because the function \(f(n) = (n, 0)\) is an injection \(f : \mathbb{N} \to \mathbb{N}^2\). But we can also construct an injection \(g : \mathbb{N}^2 \to \mathbb{N}\) as \(g((i, j)) = 2^i 3^j\). Uniqueness of prime decomposition then gives us that this is an injection, and thus \(|\mathbb{N}|^2 = \aleph_0\).
You can also construct a bijection explicitly. It’s kinda informative to do so, but the details are fiddly enough that I confess I can’t really be bothered with them.
But this fact now gives us the cardinalities of \(\mathbb{Z}\) nearly for free. Let \(f : \mathbb{Z} \to \mathbb{N}^2\) be such that \(f(n) = (s, \mathrm{abs}(n)\), where \(s = 0\) if \(n < 0\) and \(s = 1\) otherwise. Then this is an injection \(f : \mathbb{Z} \to \mathbb{N}^2\). We already know \(\mathbb{Z} \geq \aleph_0\) (because it contains \(\mathbb{N}\) as a subset), so \(|\mathbb{Z}| = \aleph_0\).
We can then do the same with \(\mathbb{Q}\). Express a rational \(x = \frac{m}{n}\) as a reduced fraction (i.e. \(n > 0\) and m and n have no common divisor). Define \(g(x) = (f(x), n)\) where \(f\) is our injection from above. This is an injection into \(\mathbb{N}^2\) and thus \(|\mathbb{Q}| = \aleph_0\).
The use of pairs for studying cardinality turns out to be quite useful. In fact it’s the case that for any infinite set that \(|A^2| = |A|\). It will be some time before we have the tools to prove this and I don’t know if I’m going to, but it’s worth knowing. We will prove it later for another concrete example though.
In general, pairs like this give us a notion of multiplication for cardinal numbers. We can construct the pair set \(A \times B\) as the set of ordered pairs where the first is an element of \(A\) and the second is an element of \(B\). Then we write \(|A \times B| = |A| |B|\).
If \(|A| \leq |C|\) and \(|B| \leq |D|\) then \(|A| |B| \leq |C| |D|\). We can see this by just pairing together the two injections we have from this inequality: If \(f : A \to C\), \(g : B \to D\) are injections then the function \(h((a, b)) = (f(a), f(b)\) is an injection \(A \times B \to C \times D\). This also shows that our notion of multiplication is well defined in the sense that if different sets have the same cardinality then their pair sets also have the same cardinality.
In particular this means that e.g. \(|\mathbb{Q}^2| = |\mathbb{Z} \times \mathbb{N}| = \aleph_0\). Any pairing of sets of size \(\aleph_0\) will give a set of size \(\aleph_0\).
Now lets look at the real numbers. Why is \(|\mathbb{R}| = 2^{\aleph_0}\)?
Well. First consider the set of all functions \(f : \mathbb{N} \to \{0,1\}\). We’ll call this set \(2^\mathbb{N}\). This has a natural bijection with \(\mathcal{P}(\mathbb{N})\) by identifying a set with its indicator function. i.e. \(f(A)(n) = 1\) if \(n \in A\) else \(f(A)(n) = 0\). We’ll show this set is in bijection with the real numbers.
First, here’s an injection \(f : 2^\mathbb{N} \to \mathbb{R}\): Let \(f(t)\) be the number whose decimal representation is \(1\) if \(t(n) = 1\) or \(0\) otherwise. This is an injection because decimal representations are unique if they contain no infinite sequence of trailing 9s.
In the other direction, choose a binary representation for \(x\) (it doesn’t matter which, but lets arbitrarily pick the version without trailing 1s where there’s ambiguity). Then the function \(g(x)(n) = \) the nth binary digit of \(x\) is an injection \(g : \mathbb{R} \to 2^\mathbb{N}\). Hence \(|\mathbb{R}| = |2^\mathbb{N}| = 2^{\aleph_0}\).
Note the bit at the end there where we wrote \(|2^\mathbb{N}| = 2^{\aleph_0}\)? This is of course where the notation \(2^{\aleph_0}\) actually comes from.
In general we can define a notion of cardinal exponentiation: \(|A|^|B| = |A^B|\), where \(A^B\) is the set of functions \(f : B \to A\). This is consistent with the above notation because \(|\{0,1\}| = 2\).
Note that if \(|A| \leq |C|, |B| \leq |D|\) then \(|A|^{|C|} \leq |C|^{|D|}\). If \(f, g\) are our injections then pick some point \(c \in C\). Define \(h : A^B \to C^D\) as \(h(t)(d) = g(t(f^{-1}(d)))\) if \(f^{-1}\) is defined there, else \(h(d) = c\). This is an injection because if \(t \neq t’\) then we can find \(a\) with \(t(a) \neq t'(a)\). Therefore \(h(t)(f(a) \neq h(t’)(f(a)\) and so \(h(t) \neq h(t’)\).
While we’re here, we should also define cardinal addition. The idea of cardinal addition is that we want a disjoint union option. \(|A| + |B|\) is \(|A \cup B|\) ignoring the fact that \(A\) and \(B\) might overlap. We can do this by defining it as \(|A| + |B| = |\{0\} \times A \cup \{1\} \times B|\), with the pairing just there to force that disjointness. We’ll write that disjoint union operation \(A \sqcup B\).
Turns out a lot of the nice properties you’d hope held do hold. In particular:
- \(|A| |B| = |B| |A|\)
- \(|A| + |B| = |B| + |A|\)
- \(|A| (|B| + |C|) = |A| |B| + |A| |C|\)
I’m going to label these “exercise for the reader”. There are fairly natural bijections in all cases.
One thing which I will do because it’s important for the next bit is show that the following exponentiation law holds: \(|A|^{|B|} \times |A|^{|C|} = |A|^{|B| + |C|}\).
Proof: This is because we can define a function on \(A \sqcup B\) by defining it piecewise on \(A\) and \(B\). So given a pair \(t = (f, g) \in |A|^{|B|} \times |A|^{|C|}\) we can define \(h(t)((0, a)) = f(a)\), \(h(t)((1, b)) = g(b)\). \(h\) is a bijection. QED
This will let us prove that \(|\mathbb{R}^2| = |\mathbb{R}|\).
First note that \(\aleph_0 + \aleph_0 = \aleph_0\) because the definition of \(\mathbb{N} \sqcup \mathbb{N}\) actually defines it as a subset of \(\mathbb{N}^2\).
This then gives us that \(|\mathbb{R}^2| = |\mathbb{R}|^2 = (2^{\aleph_0})^2 = 2^{\aleph_0 + \aleph_0} = 2^{\aleph_0} = \mathbb{R}\).
So there as many pairs of real numbers as real numbers.
It turns out to be more extreme than that. \(|\mathbb{R}^\mathbb{N}| = |\mathbb{R}|\). i.e. there are as many infinite sequences of real numbers as there are real numbers.
Why?
Well, first: we have the exponentiation rule that \((|A|^{|B|})^|C| = |A|^{|B| |C|}\). This is because given a function \(f : B \times C \to A\) you can map it to the function \(f'(b)(c) = f((b, c))\) and this mapping is a bijection.
This means that \(|\mathbb{R}^\mathbb{N}| = 2^{\aleph_0 \times \aleph_0} = 2^{\aleph_0} = |\mathbb{R}|\).
One thing that is strictly larger than \(\mathbb{R}\) is of course \(\mathbb{R}^\mathbb{R}\). This is because \(|\mathbb{R}^\mathbb{R}| \geq |2^\mathbb{R}| > \mathbb{R}\). So there are strictly more functions from \(\mathbb{R} \to \mathbb{R}\) than their are real numbers.
This isn’t true for continuous functions though. Let \(\mathcal{C}\) be the set of continuous functions \(\mathbb{R} \to \mathbb{R}\). Then \(|\mathcal{C}| = |\mathbb{R}|\).
Why? Well because a continuous function is uniquely defined by its value on the rationals (because every real number has rationals arbitrarily close to it), so the function \(h : \mathcal{C} \to \mathbb{R}^\mathbb{Q}\) defined by \(h(f) = f|_\mathbb{Q}\) is an injection. But \(|\mathbb{R}^\mathbb{Q}| = |\mathbb{R}^\mathbb{N}| = |\mathbb{R}|\).
So, there you have it. Some examples of infinity, some things that are the same size as each other, and some that aren’t. Hopefully this makes some of the ideas slightly more familiar.