Infinity is Weird

Infinity is weird.

This post is about an odd little thing I learned about involving infinite sets quite recently. First, let’s introduce some notation. We let N = {0, 1, 2, … } denote the set of natural numbers, and Q denote the set of rational numbers (recall a number is rational if we can write it as a fraction of two integers in lowest terms. So 1/2 is rational while  2 is not). If A and B are sets then a function f mapping A to B is one-to-one if everything in B is mapped to by a unique thing in A (so, for every y in B there is at most one element x in A such that f(x) = y), and it is onto if everything in B is mapped to by something in A (so for every y in B there is some element x in A such that f(x) = y). Finally, f is bijective if it is one-to-one and onto. In other words, f is bijective if everything in B is mapped to by a unique element in A.

In elementary set theory we use bijections to define what we mean by the “size” of a set. In other words, two sets A and B have the “same size” (now called cardinality) if there is some bijection f mapping A to B. For example, if A = {1, 2, 3} and B = {a, b, c}, then we can say that A and B have the same size since the function f mapping f(1) = a, f(2) = b, f(3) = c is a bijection.

What do we get by defining “size” in this manner? Well, clearly we recover “size” in the “regular” sense. If A and B are finite sets with a bijection between them and A has 10 elements, then B certainly has 10 elements as well. The nice thing about this definition of size is that it generalizes to infinite sets in a clean way. Once you realize this you can get some remarkable observations. Here is a nice one:

Theorem 1: Let N be the set of natural numbers and Q be the set of rational numbers. Then there is a bijection f from N to Q.

So, even though there are “clearly more” rational numbers than natural numbers, really the two sets have the same size. Do all infinite sets have the same size? Cantor showed that this is false via, famously, the diagonal argument.

Theorem 2 (Cantor’s Theorem): Let N be the set of natural numbers and R be the set of real numbers. Then there is no bijection from N to R.

Now, Theorem 1 tells us that there is a bijection f from N to Q. This gives us a natural way of ordering the set of rational numbers: just order them according to f! That is, we can define Q by

Q = {f(0), f(1), f(2), …}.

In particular, for every natural number x, this gives us a finite set Q(x) defined by

Q(x) = {f(0), f(1), …, f(x-1), f(x)}.

Note that for any x < y we have Q(x) is strictly contained in Q(y), and the union of Q(x) over all natural numbers x gives us every rational number! In the language of order theory the sequence of sets

{}, Q(0), Q(1), …, Q(n), …

yields an infinite chain in the lattice of all subsets of rational numbers. Moreover, this infinite chain is countable: there is a bijection between it and the natural numbers (just map any natural x to the set Q(x)).

Now, let us consider different subsets of rational numbers. For any real number t, define the set P(t) to be the collection of all rational numbers x < t.

Now things are getting interesting. Like before, for any pair of real numbers t, u with t < u we have that P(t) is strictly contained in P(u). In the language of order theory the collection

{P(t) : t >= 0}

is an infinite chain in the lattice of all subsets of rational numbers. Also, like before, if we take the union of every set P(t) for every positive real number t, we get Q again. So, we get that there is a natural bijection from non-negative real numbers to this new infinite chain (just map t to P(t)).

But, by combining Theorem 1 and Theorem 2, there is no bijection from the set of rational numbers to the set of real numbers. Why is this weird? Well, if we consider the set of all subsets of rational numbers, we get that

  • There is an infinite chain {{}, Q(0), Q(1), …} starting from the empty set that (in the limit) covers all rational numbers, which is also countable — it can be ordered (for all i, j with i < j, Q(i) is strictly contained in Q(j)), and the elements of the chain are bijective with the natural numbers.
  • There is another infinite chain {P(t) : t >= 0}, starting from the empty set that (in the limit) covers all rational numbers, which is provably not countable — it can be ordered (for all real numbers t, u with t < u we have P(t) is strictly contained in P(u)), but there is no bijection with the natural numbers.

 

It is not as paradoxical as it first seems, once you realize that the rational numbers are dense in the real numbers. Moreover, these sets P(t) can (in a loose sense) be used to define the real numbers (this uses the notion of a Dedekind cut). A similar construction was used by John Conway to define the surreal numbers, which is detailed in a fairly entertaining novel by Donald Knuth. But, it is late and I have already ranted for too long. Math is cool.

G’night!