Another Day for You and Me in Paradise

← May 25, 2023 →

HOW DO YOU COUNT SOMETHING INFINITE?

What does it mean for one set to be larger than another set? Or for two sets to be the same size?

When the two sets are finite, it’s simple: just count them. But when the sets are infinite, what should you do? You can’t actually count them. You don’t have the time! But also, there’s a more difficult problem. Some sets have an obvious place to start and some don’t.

For example, suppose you wanted to count all the numbers which have a decimal expansion (‘real numbers’) in between 0 and 1 (inclusive, if you like). Where should you start?

Well, 0 is least, so maybe start there? Then 1? Then what? You can’t just list them in order of their size. Suppose you started with

    0.00000000000001.

That’s not the next smallest number after 0! For example, what about

    0.00000000000000000001?

But that’s not a good place to start either, if you want to list them in order. What about

    0.000[ ...fifteen thousand more zeros... ]01?

OK, so there’s a practical problem, which is we can’t list all the real numbers between 0 and 1 in order from least to greatest. This is the first hint that there’s something funny about infinite sets and will be related to how we prove that there are more numbers in [0, 1] than positive integers.

COUNTING SHEEP

Let’s return to our starting question: how can you compare the size of sets? We need a procedure that works for finite sets but will generalize to infinite sets. In other words, we’re not looking for “just count them”.

Imagine you were a shepherd thousands of years ago and your language is one that can’t name numbers larger than a certain limit. “One, two, many”, for example. You want to graze your flock in an unfenced pasture but sheep are valuable and you want to make sure that at the end of the day you didn’t lose any.

Here’s something you can do. Get two baskets. Start the day with one empty basket (the ‘counting basket’) and one full of stones (the supply basket). As you let your sheep out of their pen, move one rock from the supply to the counting basket. At the end of the day as they’re rounded up, move a rock from counting basket back into the supply.

Once you are done rounding up the sheep, how many stones should be in the counting basket? None! If you have stones left in the counting basket then there are wayward sheep somewhere. If you ran out of stones early then you gained sheep.

So, we can answer the question: was the number of sheep you let out in the morning equal to the number you rounded up in the evening without ever actually finding out the number of sheep. You don’t have to count the stones in the counting basket in order to answer that size-comparison question.

ONE-TO-ONE CORRESPONDENCE

Why did it work? There was a “one-to-one correspondence” between the outward-bound sheep and the stones, and a similar correspondence between the stones and the inward-bound sheep. That’s enough.

What does the jargon “one-to-one correspondence” mean? It means: in the morning, for each sheep there was exactly one stone and for each stone exactly one sheep. Maybe it was this:

Where ‘U ⟷ S’ means “Sheep U left the pen and stone S went into the counting basket”.

In the evening, there was also a one-to-one correspondence, but it doesn’t have to be the same one! Maybe it was

where this time ‘S ⟷ U’ means “Stone S was put back into the supply when sheep U came home.”

If you can construct a one-to-one correspondence between two sets means that there are just as many in one set as in the other.

In the morning you know there are the same number of outgoing sheep as stones. In the evening you know there are the same number of stones as incoming sheep. Therefore you conclude you finished the day with the same number of sheep as you started with. Perhaps Ewesain Bolt made a run for it and the neighbor’s Harry Ewedini appeared in your flock; but this method doesn’t address that question.

Here’s what’s critical: no repeats, and nothing left out. You’ve always got to make sure there’s exactly one stone for one sheep. That makes it one-to-one. And that guarantees the sets are the same size.

You DON’T have to match the stones and sheep up in the evening as you did in the morning. Rambo happened to get paired up with the lumpy speckled rock both times, but Woolverine was paired with the coarse gray pebble in the morning and the clear quartz crystal in the evening. The orange marble cylinder was paired with Ewesain Bolt in the morning but Lady Baabaa in the evening. No problem. We still know the number of outbound sheep was the same as the number of stones in the morning and the number of stones was equal to the number of incoming sheep in the evening. Therefore the number of outbound sheep and the number of inbound sheep were the same.

This method of constructing one-to-one correspondences works for finite sets, as good as counting. But we go further: we define two sets to be the same size when they can be put in a one-to-one correspondence. Two sets are of different size when there is no possible one-to-one correspondence.

SOME EXAMPLES

Let’s use this definition a little bit.

I have the same number of fingers and toes. If I sit in butterfly pose it’s easy for each finger to touch exactly one toe and for each toe to touch exactly one finger: left thumb touches the left big toe, left pointer was left at home, the left middle finger left their roast beef over, the left ring finger left none, and the left pinky went wee wee wee all the way to it’s home last on the left. Same for the right fingers and right toes. Each finger touches exactly one toe, each toe touches exactly one finger. Therefore the number of fingers and the number of toes are the same. I could make up a different choice (left hand touches right toes, or whatever) but I don’t need to. I demonstrated even a single one-to-one correspondence, that is enough.

I have more fingers than nostrils. Suppose each nostril can fit only one finger. Then, no matter how I stick my fingers in my nose I always have clean fingers left. It is NOT enough to say: I stuck my pinkies in my nose and had clean fingers left over. You have to know that every way of pairing fingers and nostrils leaves clean fingers.

There are more counting numbers (1, 2, 3, and on and on…) than any finite number. For instance, there are more than 3 counting numbers. One correspondence you might try is

but we’ve got counting numbers left over. Try any choice of counting numbers on the right hand side of the correspondence, you’ll always have at least one left over. Here’s a proof: find the maximum of all the numbers on the right. Add one. That number is a counting number but didn’t appear! So there are more counting numbers than 3.

This argument doesn’t just show that the particular thing I tried failed. It shows that any attempt is bound to fail.

The same argument works for any finite number! 3 wasn’t important, could have been 17. So there are more counting numbers than any finite number. That’s what we mean by infinite. We call the number of counting numbers “countable infinity”.

If a set is finite we can definitely count it. We call finite sets and infinite sets the same size as the counting numbers “countable”. Sets that are bigger are “uncountable”.

THE BURDEN OF PROOF

You can’t just say “I tried one [or two, or fifty-three] correspondence[s], didn’t find any one-to-one.” and declare victory. You’ve got to show that NO possible correspondence is one-to-one. And there are a lot of possible ways to try!

Here’s why it’s important to rule out the success of any arbitrary attempt: some tries are better than others.

For example, let’s compare the counting numbers and the even numbers. There’s an infinite number of both. But somehow it’s intuitive that there’s only half as many even numbers? Because you left half out! In other words, here’s a correspondence

but it’s not one-to-one, because there are counting numbers that don’t appear: all the odd numbers. So maybe there really are more counting numbers than even numbers?

But here’s another correspondence

Every even number appears on the left exactly once and every counting number appears on the right exactly once! There are no repeats, and nothing left out! So it’s one-to-one. There are a countably infinite number of even numbers. Just as many as the counting numbers.

There are an infinite number of prime numbers. Are there more counting numbers than primes? Or maybe there are the same number of primes as counting numbers? (It seems unlikely there are more primes than counting numbers, since each prime is a counting number.)

Here’s a way to build up a one-to-one correspondence between counting numbers and primes. The first prime number is 2. The next prime number is 3. 4 isn’t prime, so the next prime number is 5. Always find the least prime that isn’t yet on the list.

Is this one-to-one? Yes. Here’s why: There is always a smallest prime not yet on the list, because we can increase the most recent addition to the list one by one until we find a prime. So, this is a one-to-one correspondence between the counting numbers and the primes. Therefore there are as many primes as counting numbers. Since there are as many even numbers as counting numbers, there are also as many primes as even numbers. (We can use the two one-to-one correspondences to construct a one-to-one correspondence between even numbers and primes: the correspondence is basically to go to the counting numbers as an intermediate step.)

There are the same number of integers (… -3, -2, -1, 0, +1, +2, +3, …) as counting numbers. One one-to-one correspondence basically puts the integers in order, but by absolute value:

So the integers are countable. Notice that unlike the primes, there is no smallest integer; integers can get as negative as you like. So we can’t order the correspondence by the value of the integers; we could never get started, just like the beginning of this story.

Constructing a one-to-one correspondence of a set with the counting numbers is called “enumerating the set”; the correspondence is “an enumeration”.

AN ASIDE ON DENSITY

So, it’s a bit unintuitive, but there really are as many even numbers as counting numbers. How can we make sense of our intuition that there’s only half as many?

We can do that by computing the density of the evens in the counting numbers. But we’ve got to do it carefully. Let’s pick a really high number N. How many counting numbers are there up to and including N? Not a trick question: there are N. How many even numbers are there up to and including N? Well, it’s about N/2. If N is even it’s exactly N/2. If N is odd it’s (N-1)/2. So the ratio is

The first term of the last expression is ​$N/2/N = 1/2$ no matter what N is. The subtracted term is ​$[0\textrm{ or } 1]/2/N$ which gets smaller and smaller as N gets bigger and bigger. So as N gets large the ratio of the sizes of these finite sets approaches 1/2. But if you don’t put a cutoff N there’s an equal number of counting and even numbers!

Essentially what we have found is that if you count up one by one, only half of the numbers you count are even, the intuitive result. The surprise is that this fact is compatible with the assertion that there just as many even numbers as counting numbers! But our one-to-one correspondence above proves it!

An interesting theorem due to Riemann is that the number of the primes less than N is proportional to ​$N / \log N$ as N gets large and the density is therefore proportional to ​$1 / \log N$, which goes to 0 as N gets large. In other words, the primes get rarer and rarer. But there’s still an infinite number of them!

THE RATIONALS ARE COUNTABLE

The rational numbers are numbers that can be written as fractions with integers upstairs and downstairs. ⊕Just don’t put 0 downstairs please! Let’s consider just the positive rationals for simplicity. ⊕A similar trick sign-alternating scheme that we used to show the integers are countable works for the rationals but adds complication.

Here’s an enumeration of the positive rational numbers: for each counting number list every pair of counting numbers that sum to that number (let different orders matter). To build a fraction put the first one upstairs, put the second downstairs, for example:

and so on. Note that for a given sum the number of possible rationals is one less than the total.

Now just string these lists together in order:

Does every positive rational number appear? Yes. Suppose the fraction was ​$n/d$ (numerator divided by denominator; you might have to use d=1). The total is n+d, and all those numbers appear in the (n+d)th row; in the concatenated list before item (n+d)². Therefore every positive rational appears on the list; the rationals are countable. It doesn’t matter that the rationals aren’t in order by value, that’s fine. What matters is that none are missing and none appear twice: the correspondence is one-to-one.

NUMBERS BETWEEN 0 AND 1

The rationals between 0 and 1 are countable too; just repeat the above construction but require the upstairs be less than the downstairs.

So, there are a countably infinite number of rationals between 0 and 1. They’re also “dense” which means that no matter which two rationals you pick you can always find one in between ⊕The average of two rationals is rational, for example. (and then you can use that new in-between number as a new starting point). So there’s no “getting away” from the rationals. Famously π is not rational, but if we play a game where you say some small positive number ε ⊕ε is the Greek letter epsilon, and is often used in math to represent some tiny positive number I can always find a rational number closer to π than the number you said. That is, I can always name a rational r such that π-ε < r < π+ε, as long as you name ε first.

At the beginning of this story we tried to list the real numbers between 0 and 1 in order and found that we couldn’t, because no matter where we started we could always find a smaller number. That’s true of the rationals! You can’t list them in order of size, because there’s always a smaller one, but you can list them in this other funny order.

Does that mean there are as many numbers between 0 and 1 as there are rationals (which are countably infinite)?

This is a very subtle question, but the answer is no. There are more numbers between 0 and 1 than counting numbers, as we will now show.

The numbers between 0 and 1 all have a unique decimal expansion, which is just a list of digits. ⊕Let’s agree that expansions that end in repeating 9s aren’t allowed, for example 0.499999… is just 0.5 For example, here are some numbers between 0 and 1 and their decimal expansions:

    1/2:        0.5000000000000000[0 forever]
    π-3:        0.1415926535897932...
    √(2)-1:     0.4142135623730950...

Remember: we need to show that no matter what correspondence we try to make between the countables and the reals in [0,1] we have some reals left over. For example, this correspondence

leaves out a lot of numbers. 3/4 and 5/12 and π-3 for example. But maybe this choice is like the evens and the countables and there’s some non-obvious way to enumerate every real number?

George Cantor proved that no, there is NO way to pair up the reals and counting numbers without having reals left over. The proof proceeds by contradiction.

Suppose I claimed to have such a one-to-one pairing. Let’s list them by their counting number.

You’re suspicious that my list is incomplete, which would mean it’s not a one-to-one correspondence. So it’s your job to find a number that’s not in the right column of this list; something I left out. Here’s how you build a missing number:

1. Look at the first digit of the first number. It happens to be a 1. So the first digit of your number should be some other digit. Say 7. Now we know that the number you’re building isn’t the first number on my list, because it disagrees in the first digit.
2. Look at the second digit of the second number. It’s a 2. So the second digit of your number shouldn’t be 2. Maybe you pick 3. Now we know that the number you’re building isn’t the second number on my list, because it disagrees in the second digit.
3. Look at the third digit of the third number on my list. It’s a 1. Again, pick a different digit. 8. Now we know the number you’re building isn’t the third number on my list, because it disagrees in the third digit.

and so on and so on. So you build 0.7384517… This number is not on my list, because we know it differs from each number on my list in at least one digit.

“Oh sorry, I just forgot that one!” I say. “Just take my list, shove each item down one, and put this number at the front. That patches the hole.” No. You do the procedure again, this time building 0.47384517…

No matter the pairing I present to you, claiming it to be an enumeration, you can always find a missing number. So there are more real numbers than counting numbers!

How many more? A LOT MORE! One way to see this is that at each digit you’ve got to pick a digit and only one is forbidden, 9 are allowed. So instead of 0.738… you could have picked 0.238, 0.338, 0.438, 0.538, 0.638, 0.738, 0.838, 0.938, and that’s only fiddling with the first digit. In fact, as long as your number doesn’t start 0.12110009… it’s guaranteed to be different.

If we just look at the first d digits of the first d numbers on my list, how many numbers could you write that are guaranteed not to be in these first d numbers? There’s 10^d possible strings of digits and you just cannot write d of them. In this sense there are exponentially more real numbers than counting numbers: just let d get larger and larger and larger.

The number of real numbers in [0, 1] is infinite. But it’s bigger than the countable infinity. It’s the “size of the continuum”, the continuum being a fancy name for “the entire number line with no holes”.

This method for finding omissions is called “Cantor’s diagonal argument” because the missing number is different from the list of real numbers along the diagonal digits.

OK BUT THAT’S IT RIGHT? JUST TWO?

No. There’s a whole hierarchy like this! But it’s much harder to give a concrete example; things get abstract quickly.

Mathematicians found a way to take Cantor’s argument and pull itself up by its bootstraps. ⊕Famous, contemporary mathematicians accused Cantor of being a scientific charlatan. He had a number of mental health episodes and died in involuntary commitment in a sanitorium. On the other hand David Hilbert proclaimed ‘No one shall expel us from the paradise Cantor has created.’ So Cantor’s difficult ideas were not universally derided in his day. The idea at each level is roughly the same idea: Given a nonempty set (finite or infinite) it’s possible to construct a set exponentially larger, and to show there is no possible one-to-one correspondence between the starting set and this exponentially larger set.

Are there any sets with more elements than the counting numbers but fewer elements than the continuum? The claim that there are no such sets is called the Continuum Hypothesis.

Surprisingly, this question is independent of the standard choice of axioms of mathematics. If all you pick are the standard axioms (called ZFC), you can’t decide. Fucking hellish answer.

I HATE THIS INFINITY PLUS ONE!

The entire discussion above is about comparing sizes (“cardinality”) of sets. But that’s not about counting something in order. In fact, we explicitly gave this whole story about how to compare sizes you don’t have to actually count all the elements.

But, like, maybe if you just keep counting up higher and higher you … get? … to infinity? Like, infinity comes … after? all the counting numbers?

George Cantor’s answer was: YEAH MAN, JUST FUCKING KEEP GOING! You can put anything in order if you’re brave enough!

He said: I’m just going to put numbers in order, like I was counting. “After” all the natural numbers comes ω (omega). “After” comes in quotes because if you set out to do it you’d never finish counting the counting numbers, so “After” doesn’t mean in time.

1, 2, 3, … ω, ω+1, ω+2, …, ω×2, ω×2+1, ω×2+2, …, ω×3, …, ω×4, …, ω×ω = ω^2, … ω^3, … ω^ω, and so on…

where the first few … all stand for the same amount of counting, but “then” [it never happens in time] you hit ω^2 and I use each … to elide a lot more numbers, to show the pattern. Also “and so on…” is carrying a lot of water; we’ve counted an infinite infinite number of numbers and yet compared to what mathematicians call, with dramatic understatement, “large ordinals”, they’re just the start.

I understand these “ordinals” a lot less. But these explanations by John Baez are pretty good! ⊕John is Joan Baez’s cousin.

← May 25, 2023 →