An infinity bigger than infinity

Comparing infinite lists

Let us begin a formalized notion of “‍bigger‍”. math Given two lists of numbers, if the lists are the same size then we can pair them up such that every number from one list has a pair in the other list. If I can pair them such that everything in list A has a pair in list B, but not vice-versa, then A is no larger than B, but it might still be the same size if the lists are infinite.

Let’s try a few examples. The lists [1, 2, 3] and [x, y, z] are the same size because I can pair them up [(1, y), (2, x), (3, z)]. The positive integers and the negative integers are the same size because I can pair them up (x, –x) for any x. The list of all rational numbers (fractions) is the same size as the list of all integers, shown by interleaving digits

123

789

pairs with 172839.

So, what about lists that aren’t the same size? Well, [1, 2, 3] is not the same size as [x, y]: no matter how I pair things up, there is always an extra number with no letter. At first blush the list of integers appears to be larger than the list of positive integers since I can pair all the positives and leave all the negatives unpaired. But recall that just means that the list of positive integers is no larger than the list of integers. Another pairing shows they are actually the same size: A few pairs: (0, 1), (–1, 2), (1, 3), (–2, 4), (2, 5) pair integer i with positive integer –2i if i was negative, 2i + 1 if i was non-negative.

There are more reals

So far, every infinite list we’ve seen (integers, positive integers, rational numbers) has been the same size. Is there a list that is larger? Georg Cantor presented several proofs that the real numbers are larger. The most famous of these proofs is his 1891 diagonalization argument.

Any real number can be represented as an integer followed by a decimal point and an infinite sequence of digits. Let’s ignore the integer part for now and only consider real numbers between 0 and 1. Now we need to show that all pairings of infinite sequences of digits to integers of necessity leaves out some infinite sequences of digits.

Let’s say our candidate pairing maps positive integer i to real number r_i. Let’s also denote the digit in position i of a real number x as xⁱ. Thus, if one of our pairings was (17, 0.651249324…) then r₁₇⁴ would be 2. Now, consider the special number z, where zⁱ is the bottom digit of r_iⁱ + 1. An example:

The number z above is a real number between 0 and 1 and is not paired with any positive integer. Since we can construct such a z for any pairing, we know that every pairing has at least one number not in it. Thus, the lists aren’t the same size, meaning that the list of real numbers must be bigger than the list of integers.

Diagonalizations Everywhere

It is not clear that I care how many real numbers there are. However, Cantor diagonalization can be used to show all kinds of other things. For example, given the Church-Turing thesis there are the same number of things that can be done as there are integers. However, there are at least as many input-output mappings as there are real numbers; by diagonalization there must therefor be some input-output mappings which we can’t compute. More simply, there are more problems than there are solutions.

Diagonalization is so common there are special terms for it. A list that can be shown to be larger than the list of integers is called uncountably infinite, while lists that are the same size as the integers are countably infinite. There’s also a set of symbolsℵ is the Hebrew letter “‍alef‍”, always written in a serif typeface when referring to infinities. for infinities: there are ℵ₀ integers, ℵ₁ real numbers, etc.

Is diagonalization wrong?

I have found that Cantor’s diagonalization argument doesn’t sit well with some people. It feels like sleight of hand, some kind of trick. Let me try to outline some of the ways it could be a trick.

You can’t list all integers

One argument against Cantor is that you can never finish writing z because you can never list all of the integers. This is true; but then you can never finish writing lots of other real numbers, like π, either.

Just because you failed…

Another argument is that Cantor used proof by contradiction: “‍Assume you have a pairing. Oops, you don’t after all‍”. Some people don’t like proof by contradiction, indeed there’s a fairly popular logic Intuitionistic logic, second only to classical logic among my friends. that bans it completely. If you don’t like proof by contradiction you’re unlikely to accept diagonalization.

Most “‍real numbers‍” don’t exist

Numbers from the real world don’t have infinite precision. Numbers from mathematics have symbolic definitions. Either way, every real number I can ever encounter can be expressed finitely, either by a finite description of defining equations or a finite precision real-world measurement. And if they have finite expressions, then they are countable.

In the end, whether you accept diagonalization or not is up to you. The majority of theoreticians in the world seem to accept it; indeed, not accepting it can earn a bit of ridicule. But there’s no reason you need to bow to their logic…

When all is said and done, a proof is just a social construct, a particular kind of persuasive argument. Accept it only if it convinces you.