Counting, uncounting, and dust, part two

Extending countability
Having looked at the definition of countability and the natural numbers N, it is but natural (no pun intended) to ask how far this concept can be extended. The natural numbers are pretty awesome, after all, but there are a huge number of things you can't do with natural numbers, including something as basic as subtraction.

Integers
The only operations under which N is closed are addition (that is, you can add two natural numbers and the result will be a natural number) and multiplication, but the latter is pretty limited in the sense that it's basically just repeated addition. So all we can do with natural numbers is "go forth and multiply"; there is no way to reduce them. In other words, there is no "inverse"operation to addition under which N is closed.

So let's define the integers, traditionally noted by Z (from the German zahlen, to count), as an extension of the natural numbers that is closed under subtraction. (Technically Z is a group under the operation of addition.) Among other things, this means zero is in Z, so that you have an "identity element", something that you can add to any number while keeping it the same. This also means that you have "additive inverses", something you can add to a number to produce zero.

More simply put, Z = {…, -2, -1, 0, 1, 2, …}. It is infinite in two directions, so to speak. Now intuition would suggest that this means Z is bigger than N, n'est-ce pas? Except that our earlier exploration of countability should suggest that our intuitions cannot always be relied upon when it comes to the infinite.

A different intuition—call this the intuition of the mathematician, if you will—would suggest that the even numbers 2N, despite missing every second number of N, are nevertheless of the same size as N, meaning that you can essentially "double" the size of a countably infinite set and get another countably infinite set. And since Z is essentially N "doubled", it should also be countably infinite!

How can we be certain about this? Just to make things a little more mathematically convenient, let's take a slightly different set, the whole numbers W = {0, 1, …}. Now clearly W is countably infinite because there is a bijection between W and N (given any whole number w, you can index it using the natural number w + 1; given any natural number n, you can index it using the whole number n - 1). What we shall do is show that there is a bijection between Z and W, which automatically means that there is a bijection between Z and N. So what can this bijection be?

Very conveniently for us, we can see that both sets can be neatly divided into three different subsets:

• W is the union of the set consisting of the single element 0 (let's call it 0 = {0}), the even numbers (2N, as we called them last time), and the odd numbers (2N - 1). In set notation, W = 0 ∪ 2N ∪ (2N - 1).
• Z is the union of 0, the positive integers (that is to say, N), and the negative integers (call them N_). In set notation, Z = 0 ∪ N ∪ N_.

We already know that the four lettered sets are all countably infinite, so all we need to do to build a bijection between Z and W is to do the following:

• Given an integer z (in mathematical notation, z ∈ Z, which is read as "z is an element of Z"):
• If z = 0, index it to the whole number 0. (For now, let's think of the two 0s as being different, just as a matter of convenience. We can call them 0_Z and 0_W if you want. So if z = 0_Z, then index it using 0_W.)
• If z is a positive integer (z ∈ N), then index it to the even number 2z. Note that this clearly maps all positive integers N to all even numbers 2N.
• If z is a negative integer (z ∈ N_), then index it to the odd number 2 |z| - 1. Note that we've used the absolute value function here in order to strip away the negative sign of z and to produce a positive number instead. This way we are guaranteed to get a result that belongs to the set 2N - 1.
• And for the reverse process, given a whole number w ∈ W:
• If w = 0_W, then index it using the integer 0_Z.
• If w is an even number (w ∈ 2N), then map it to the positive integer w / 2. (Because w is even, it can be divided by two to produce an even number.)
• If w is an odd number (w ∈ 2N - 1), then map it to the negative integer (-1)(w + 1) / 2. (Multiplying by -1 guarantees us that we will produce a negative number, and then the other parts of the definition guarantee that this will be a negative integer.)

This is a little more complicated than the procedure for showing that the even numbers are countably infinite, but it is even more satisfying! This also tells us something interesting: we can essentially "double" the size of a countably infinite set and still stay countably infinite. This in turn suggests that we can "multiply" the size of a countably infinite set by any finite number and still stay countably infinite. But what happens if we try something more ambitious?

Rational numbers
With the integers, we can now perform addition (and subtraction), but we still cannot divide two arbitrary integers and expect to get an integer. So we expand the set of integers Z to create the set of rational numbers Q, formally defined as Q = {p/q | p, q ∈ Z and q ≠ 0 and p, q are in lowest terms}. This is the standard mathematical notation for a set, and is to be read thus: Q is the set of all fractions p/q [p being the numerator and q the denominator, of course] such that both p and q are elements of the set of integers Z, and q does not equal 0, and p and q do not share any multiplicative factors in common (i.e., you can't simplify them any more). The "such that" sign, which is the vertical bar '|', is sometimes replaced by the colon ':'.

This set Q clearly contains far more numbers than Z. We can clearly see this if we look at a number line. Whereas the points that represent the integers are separate and visibly far from one another, the rational numbers are not. They are "densely" clustered on the line, limitlessly packed so close that between any two rational numbers we can always find a third rational number (essentially, if you have a ∈ b ∈ Q, then (a + b) / 2 ∈ Q clearly, and furthermore it lies between a and b). We are now surely at a stage where we have a set larger than N.

Alas, our intuition fails us once again. As it turns out, Q is also countably infinite; in other words, there exists a bijection between N and Q.

But what on earth is this bijection? How do you create a bijection between one set and another that is, in some sense, the first set "squared"? The answer is tremendously simple to see, although my inability to draw an image will make it rather tricky to represent it in words.

For convenience's sake, let us only consider the subset Q₊ = {p / q | p, q ∈ N and q ≠ 0 and p, q are in lowest terms}. This excludes half of the rational numbers, but that is really not a problem as we have seen before; if we can prove that Q₊ is countably infinite, then it won't be hard to "double" that property to all of Q. Since every rational number can be represented as the ratio of two integers, we can write them (theoretically, if we had an infinite amount of time and nothing better to do!) in a table whose columns and rows are indexed by the natural numbers. Our table should look something like
1/1, 2/1, 3/1, 4/1, …
1/2, 2/2, 3/2, 4/2, …
1/3, 2/3, 3/3, 4/3, …
1/4, 2/4, 3/4, 4/4, …
and so on. It should be evident that every positive rational number from Q₊ is on this list (and in fact, more than once; after all, 1/1, 2/2, 3/3, and so on all represent the same number, the rational number 1). Since we have an infinite amount of time, we decide to scratch out all the numbers that are represented more than once, thus leaving holes in our table:

1/1, 2/1, 3/1, 4/1, …

1/2, xx, 3/2, xx, …

1/3, 2/3, xx, 4/3, …

1/4, xx, 3/4, xx, …

Now comes the fun part. Imagine drawing a curve that starts from 1/1 and then zigs and zags through this square: 1/1, 2/1, 1/2, 3/1, 1/3, 4/1, 3/2, 2/3, 1/4, … and so on. (This is where the image would have been really useful; if you like, it sort of resembles the diagram that illustrates the Aufbau principle that is used to describe the order in which atomic orbitals are named.) If we now index each point with a natural number in sequence, we will have created a bijection (loosely speaking) between Q₊ and N. In other words, we will have successfully enumerated all the rational numbers using the natural numbers, and vice-versa.

Thus, even though the rational numbers contain so many numbers that are not natural numbers (consider the fact that just between 0 and 1, you have all the numbers 1/2, 1/3, 1/4, and so on, which themselves form a countably infinite set), they are still exactly the same size as the natural numbers.

Irrationality and madness
It would only be rational (no pun intended) to decide at this point that our definition of infinity is good enough for all purposes, and that this is the "largest" that a set can be. But mathematicians are usually gripped by a certain kind of madness: the desire to abstract and to generalize, to push properties to see just how far they can go before collapsing under their own nonsensicality.

In our case, for instance, it turns out that there are a lot of numbers that are just not expressible as rational numbers. The most famous of these numbers is of course the ratio of the circumference of a circle to its diameter, represented by the Greek letter π. Another famous example is √2, about which it is said that the Pythagorean cult in ancient Greece jealously hid the proof of its irrationality because their metaphysics would collapse under such madness. Yet another example is the number e that shows up just about everywhere in the universe. How many such numbers are there after all? And do we really need them?

As it turns out, we really do need them, for what seems like an obscure mathematical reason. Q is very useful because it is well-behaved when it comes to all four major operations (addition, subtraction, multiplication, and division)—in mathematical terms, Q is called a "field". However, Q has one major deficiency: you can have sequences of rational numbers that do not converge to a rational number.

What on earth does that mean? And why does that matter?