Many of us recall the sense of wonder we felt upon learning that there is no biggest number; for some of us, that wonder has never quite gone away. It is obvious that, given any counting number, one can be added to it to give a larger number. But the implication that there is no limit to this process is perplexing.
The concept of infinity has exercised the greatest minds throughout the history of human thought. It can lead us into a quagmire of paradox from which escape seems hopeless. In the late 19th century, the German mathematician Georg Cantor showed that there are different degrees of infinity — indeed an infinite number of them — and he brought to prominence several paradoxical results that had a profound impact on the subsequent development of the subject.
Set Theory
Cantor was the inventor of set theory, which is a fundamental foundation of modern mathematics. A set is any collection of objects, physical or mathematical, actual or ideal. A particular number, say 4, is associated with all the sets having four elements. For any two of these sets, we can find a 1-to-1 correspondence, or bijection, between the elements of one set and those of the other. The number 4 is called the cardinality of these sets. Generalizing this argument, Cantor treated any two sets as being of the same size, or cardinality, if there is a 1-to-1 correspondence between them.
Bijection between two sets of cardinality 4.
But suppose the sets are infinite. As a concrete example, take all the natural numbers, 1, 2, 3, … as one set, and all the even numbers 2, 4, 6, … as the other. By associating any number n in the first set with 2n in the second, we have a perfect 1-to-1 correspondence. By Cantor’s argument, the two sets are the same size. But this is paradoxical, for the set of natural numbers contains all the even numbers and also all the odd ones so, in an intuitive sense, it is larger. The same paradoxical result had been deduced by Galileo some 250 years earlier.
Cantor carried these ideas much further, showing in particular that the set of all the real numbers (or all the points on a line) have a degree of infinity, or cardinality, greater than the counting numbers. He did this using an ingenious approach called the diagonal argument. This raised an issue, called the continuum hypothesis: is there a degree of infinity between these two? This question can not be answered within standard set theory.
Infinities without limit
Cantor introduced the concept of a power set: for any set A, the power set P(A) is the collection of all the subsets of A. Cantor proved that the cardinality of P(A) is greater than that of A. For finite sets, this is obvious; for infinite ones, it was startling. The result is now known as Cantor’s Theorem, and he used his diagonal argument in proving it. He thus developed an entire hierarchy of transfinite cardinal numbers. The smallest of these is the cardinality of the natural numbers, called Aleph-zero:
Aleph-zero, the cardinality of the natural numbers and the smallest transfinite number.
Cantor’s theory caused quite a stir; some of his mathematical contemporaries expressed dismay at its counter-intuitive consequences. Henri Poincaré, the leading luminary of the day, described the theory as a “grave disease” of mathematics, while Leopold Kronecker denounced Cantor as a renegade and a “corrupter of youth”. This hostility may have contributed to the depression that Cantor suffered through his latter years. But David Hilbert championed Cantor’s ideas, famously predicting that “no one will drive us from the paradise that Cantor has created for us”.
https://thatsmaths.com/2014/07/31/degrees-of-infinity/
Cantor’s paradise is an expression used by David Hilbert (1926, page 170) in describing set theory and infinite cardinal numbers developed by Georg Cantor. The context of Hilbert’s comment was his opposition to what he saw as L. E. J. Brouwer’s reductive attempts to circumscribe what kind of mathematics is acceptable; see Brouwer–Hilbert controversy.
“From the paradise that Cantor created for us no-one shall be able to expel us.” Hilbert (1926, p. 170), in a lecture given in Münster to Mathematical Society of Westphalia on 4 June 1925
https://en.m.wikipedia.org/wiki/Cantor's_paradise
Georg Ferdinand Ludwig Philipp Cantor (3 March [O.S. 19 February] 1845 – 6 January 1918) was a mathematician who played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets, and proved that the real numbers are more numerous than the natural numbers. Cantor’s method of proof of this theorem implies the existence of an infinity of infinities. He defined the cardinal and ordinal numbers and their arithmetic. Cantor’s work is of great philosophical interest, a fact he was well aware of.
https://en.m.wikipedia.org/wiki/Georg_Cantor
Take the set of natural numbers {1, 2, 3, 4, … }. How many members are there in the set? Infinitely many, right? OK, now take the set of real numbers. How many members are there in the set? Infinitely many, right? So far so good.
Here is where it starts to get tricky. The number of members of a set is called its cardinality. If the cardinality of the natural numbers is infinity, and the cardinality of the real numbers is infinity, then do these two sets have the same cardinality? Are there the same amount of natural numbers as real numbers?
Whatever your intuition is about that last question, your intuition will hardly do. We need to be methodical about this. So now lets begin the proof […].
Suppose we have devised some way to list all the real numbers between 0 and 1. This list will naturally be infinitely long, and we can write each entry in an infinitely-long decimal form. Here is how it might start, and note that I have marked some digits in bold.
The digits in bold run down the diagonal of this list. Use them to construct a new real number between 0 and 1.
.1531190918…
Like all the other numbers on the list, this number will have an infinite number of digits; this is because the list is infinitely long.
Now increase each individual digit by 1. If the digit is 9, make it 0:
.2642201029…
Is this new number on the original list?
On one hand, it must be, because the list is infinitely long and contains all the real numbers between 0 and 1. The new number is a real number between 0 and 1.
On the other hand, if we work through the number and the list methodically, we will see that it cannot be on the list. Is the new number the first number on the list? No, because the first digit of the number differs from the first digit of the first entry. Is the new number the second number on the list? No, because the second digit of the number differs from the second digit of the second entry. Is the new number the _n_th number on the list? No, because the _n_th digit of the number differs from the _n_th digit of the _n_th entry. Therefore, the new number, a real number between 0 and 1, cannot appear on an infinitely-long list of real numbers between 0 and 1.
We have contradicted ourselves, and that concludes the proof. It is impossible, even in principle, to denumerate the real numbers between 0 and 1. There are not just infinitely many reals between 0 and 1—there are uncountably many. There are so many that they cannot all be placed in correspondence with the natural numbers (i.e., given a spot on an infinitely-long list). Fun, right?
You may be wondering if there is a correspondence between the cardinality of the set of natural numbers and the cardinality of the set of real numbers. You’re in luck; there is! The cardinality of the set of natural numbers is of course infinity, but it is a kind of infinity that is called aleph-null (ℵ₀). The cardinality of the set of real numbers (“the cardinality of the continuum”) is 2ℵ₀ ! That is a very big number.
Finally, if you’re still with me, I’ll offer a bonus. We can divide the real numbers into two sets: the algebraic numbers, which are numbers that can be solutions to one-variable polynomial equations with rational or integer coefficients, and transcendental numbers, which cannot be. It turns out that there are countably many algebraic numbers. You might already see where this is going. If there are 2ℵ₀ real numbers, and aleph-null algebraic numbers, how many transcendental numbers are there? 2ℵ₀ – ℵ₀, which is exactly equal to 2ℵ₀ . (If you have difficulty seeing this, try 100 instead of aleph-null: 2100 – 100 is very close to 2100 , no?). What this means is that “almost all” numbers are transcendental.
https://www.elidourado.com/p/cantors-diagonal-argument
For convenience, we are going to give the proof in terms of the binary system (see Number Systems), though it applies equally well for the decimal system. We will use the binary system because this makes everything a lot simpler – in the binary system, the only symbols used to define numbers are 0, 1 and the binary point, e.g.
0.1 in decimal notation this means a tenth, in binary notation it means a half,
0.01 in decimal notation this means a hundredth, in binary notation it means a quarter,
0.001 in decimal notation means a thousandth, in binary notation it means one-eight. And so on. For example, 7⁄16 in the decimal system comes out in binary notation as 0.0111.
Obviously, for some fractions such as 1⁄3 , the number cannot actually be written in binary notation, and the binary expansion continues infinitely with a repeating string of digits (in the case of 1⁄3 this repeating bit is 01, giving 0.0101, 0.010101, 0.01010101, and so on). Similarly, no irrational number can be represented by a finite string of the 0s and 1s of binary notation.
Again, for convenience, when the term ‘list’ or ‘enumeration’ of real numbers is used below, the term is used to indicate a function that gives a one-to-one correspondence between natural numbers and real numbers, that is, each real number is uniquely matched to one natural number. Since it refers to an infinite number of things, such a ‘list’/‘enumeration’ cannot be written down - but there can be definitions that define infinitely long lists.
Having dealt with the preliminaries, below is a typical presentation of the Diagonal proof itself:
To prove: that for any list of real numbers between 0 and 1, there exists some real number that is between 0 and 1, but is not in the list.
Obviously we can have lists that include at least some real numbers. In such lists, the first real number in the list is the number that is matched to the number one, the second real number in the list is the number that is matched to the number two, and so on. For any such list, we call the list a function, and we give it the name r(x). So r(1) means the real number matched up to the number 1, while r(2) means the real number matched up to the number 2, and r(17) means the real number matched up to the number 17. And so on. There can be many such lists, and we know that we can have lists that have some finite quantity of real numbers, and some lists that have an infinite quantity of real numbers. We will later address the question of whether there can be such a list that includes every real number.
Now, we suppose that the beginnings of the binary expansions of some list of real numbers are as follows (of course, we cannot actually write down infinitely long binary expansions):
r(1) = 0.101011110101 …
r(2) = 0.00010100011 …
r(3) = 0.0010111011110 …
r(4) = 0.111101010111 …
r(5) = 0.10111101111 …
r(6) = 0.11101011111001 …
- For any list of real numbers, there exists a number (which we will call d ) which is defined by the following rule. We start off with a zero followed by a point, viz: ‘0.’ Then we take the first digit of the first number in the list, and if the digit taken is 0 we change it to 1 and we write it down; if it is 1 we change it to 0 and we write it down. This is called the complement, so the complement of 0 is 1 and the complement of 1 is 0. We then take the second digit of the second number in the list and do the same, writing the changed digit after the previous one. And so on, and so on. For the first few numbers in our list above, this would work out like this (here we show the relevant digits in bold text):
r(1) = 0.101011110101 …
r(2) = 0.00010100011 …
r(3) = 0.0010111011110 …
r(4) = 0.111101010111 …
r(5) = 0.10111101111 …
r(6) = 0.11101011111001 …
From this list, we obtain the following number: d = 0.010001. This is commonly called the ‘diagonal’ number. This real number d differs from every other real number in the list since it is different from every number in the list by at least one digit. For any finite list, the number d is a rational number, since the sequence of digits is finite. But if the list is limitless, then d is an endless expansion that is a real number. In this case, we cannot follow the instruction to write down the digits, and the number d is given only by definition - it is defined as the number where its nth digit is the complement of the nth digit of the nth number in the list…
So, given any list of real numbers we can always define another real number that is not in that list – the Diagonal number.
We now assume that there can be a list that includes every real number.
And now we have a contradiction – because the Diagonal number would be at the same time defined as a number that is in the list and also cannot be in the list – because it differs from every number in the list, since it is always different at the nth digit.
That means that the assumption that there can be a list that includes every real number (Step 7 above) is incorrect.
Therefore there cannot be a list that includes every real number.
That concludes the Diagonal argument.
https://www.jamesrmeyer.com/infinite/diagonal-proof
He also showed that they were “non-denumerable” or “uncountable” (i.e. contained more elements than could ever be counted), as opposed to the set of rational numbers which he had shown were technically (even if not practically) “denumerable” or “countable”. In fact, it can be argued that there are an infinite number of irrational numbers in between each and every rational number. The patternless decimals of irrational numbers fill the “spaces” between the patterns of the rational numbers.
Cantor coined the new word “transfinite” in an attempt to distinguish these various levels of infinite numbers from an absolute infinity, which the religious Cantor effectively equated with God (he saw no contradiction between his mathematics and the traditional concept of God). Although the cardinality (or size) of a finite set is just a natural number indicating the number of elements in the set, he also needed a new notation to describe the sizes of infinite sets, and he used the Hebrew letter aleph (Aleph). He defined Aleph0 (aleph-null or aleph-nought) as the cardinality of the countably infinite set of natural numbers; Aleph1 (aleph-one) as the next larger cardinality, that of the uncountable set of ordinal numbers; etc. Because of the unique properties of infinite sets, he showed that Aleph0 + Aleph0 = Aleph0, and also that Aleph0 x Aleph0 = Aleph0.
All of this represented a revolutionary step, and opened up new possibilities in mathematics. However, it also opened up the possibility of other infinities, for instance an infinity – or even many infinities – between the infinity of the whole numbers and the larger infinity of the decimal numbers. This idea is known as the continuum hypothesis, and Cantor believed (but could not actually prove) that there was NO such intermediate infinite set. The continuum hypothesis was one of the 23 important open problems identified by David Hilbert in his famous 1900 Paris lecture, and it remained unproved – and indeed appeared to be unprovable – for almost a century, until the work of Paul Cohen in the 1960s.
Wonderful post thank you!
This was awesome, thank you! Not sure if it’s a voyager client issue, but the bolded numbers in the diagonal proof did not show as bolded for me.
