The Diagonal Proof (v1)

Note that this page has been superseded by a later version , see The Diagonal Proof. This version has been retained to demonstrate that there was no error in the argument presented on this page, and that the later argument was used because it enabled a simpler argument.

If you have come to this page expecting a denunciation of the method used in Cantor’s diagonal proof, you may be disappointed. There is absolutely nothing wrong with the underlying method of the Diagonal proof, and provided (as for any other proof method) that it is used without making additional unfounded assumptions, proofs using the method are perfectly valid proofs. However, the conventional presentation of the Diagonal proof does include assumptions that are unfounded and illogical, and which give rise to the conventional claim that there are ‘more’ real numbers than natural numbers.

The Diagonal proof is often called Cantor’s proof, because Cantor was the first person to come up with it, though the version of the Diagonal proof that you commonly see today is quite different to what Cantor originally published. (Footnote: Note there is a similar version of the proof, known as the Power Set proof. Also note that Cantor had previously published another proof that there cannot be a function that lists all real numbers in 1874, see Cantor’s 1874 proof.) You can see the original proof at Cantor’s original 1891 proof.

We will do a logical analysis of the proof below (you can also see a more formal version at PDF On Considerations of Language in the Diagonal Proof ). 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, ⁷⁄₁₆ in the decimal system comes out in binary notation as 0.0111.

Obviously, for some fractions such as ¹⁄₃, 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 ¹⁄₃ this repeating bit is 01, giving 0.0101, 0.010101, 0.01010101, and so on). (Footnote: Note that whatever base is chosen, there will always be fractions that cannot be represented in that base as a finite string of digits.) 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’ 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’ cannot be written down - but there can be definitions that define infinitely long lists.

Below is a typical presentation of the Diagonal proof: (Footnote: Note that in the binary system a real number can be defined in two different ways, for example, 0.1 can also be defined as the infinitely repeating 0.01111111… , and this is sometimes taken as a deficiency in the Diagonal argument, but this is not the case, as it is easily dealt with, see below: Appendix: Dual Definition.)

The Diagonal Argument

That concludes the Diagonal argument.

The Secondary Argument

Following on from the above primary result of the Diagonal proof, a secondary argument is attached to the proof. This claims that there must be ‘more’ real numbers than natural numbers.

This is a quite extraordinary claim - that although there are limitlessly many real numbers and limitlessly many natural numbers, there are more real numbers than natural numbers - that in some way, the limitlessness of natural numbers is not as ‘big’ as the limitlessness of real numbers. When faced with a claim such as this, one is entitled to ask for a very clear explanation for the claim. As Carl Sagan said:

“Extraordinary claims require extraordinary evidence.”  (Footnote: From the TV series Cosmos: A Personal Voyage Encyclopedia Galactica [Episode 12].)

The basis for the claim of the secondary argument has its origins in a paper by Gyula König, the original paper is in German, see PDF Über die Grundlagen der Mengenlehre und das Kontinuumproblem (Footnote:Julius König, Über die Grundlagen der Mengenlehre und das Kontinuumproblem, Mathematische Annalen 61 (1905) 156-160.) or for an English translation, see On the foundations of set theory and the continuum problem. The argument is commonly presented like this:

If every real number could be expressed in some language as some finite combination of symbols, then we could easily have a method of matching the natural numbers to these combinations of symbols. All that is required is an alphabetical style ordering of all the symbols used to define real numbers (in the same way as a, b, c … is the order for the English alphabet), and then you simply list them in the same way as you would order the words in a dictionary. And if you could list them, you can obviously attach natural numbers to every item in the list. But this would contradict the Diagonal argument, so there must be real numbers that cannot have any finite representation. (Footnote: Interestingly, Cantor initially refused to accept this argument; he wrote in 1906 in a letter to Hilbert, ‘Infinite definitions (which are not possible in finite time) are absurdities. … Am I wrong or am I right?’, as quoted in the book Cantor, ed. Herbert Meschkowski & Winfried Nilson, Briefe Berlin: Springer (1991).)

Does this constitute extraordinary evidence?

No - because this argument forces the enumeration of the reals to be in a different language system (a meta-language) from the real numbers of the list, where every combination of symbols that defines a real number in that language system is simply an object in that meta-language, and which has no inherent numerical value in that meta-language. The argument is risible because it introduces different levels of language while at the same time completely ignoring the implications of how the introduction of different levels of language might affect the overall proof.

But it does affect the overall proof, as will be shown below. If the underlying basis of the secondary argument is logically valid, then it must also be valid under closer inspection. So we will analyze the proof and the secondary argument in more detail.

In the Diagonal proof, it must always be possible that the definition of the Diagonal number is, for any list of real numbers, a completely clear and unambiguous definition. For the proof to be logically valid, the definition of the Diagonal number will not rely on vague expressions of natural language, and will not rely on any unfounded assumptions.

Platonist assumptions in the secondary argument

The Diagonal proof is an instance of a straightforward logically valid proof that is like many other mathematical proofs - in that no mention is made of language, because the assumption is that every mathematical entity referred to by the proof is being referenced by a single mathematical language.

However, in the case of the Diagonal proof, the secondary argument actually introduces a meta-language into the argument (a language that makes statements about another language). But in the conventional reading of the secondary argument, the fact that this has introduced different levels of language into the argument is completely ignored. The conventional reading of the Diagonal proof, which includes the secondary argument, involves Platonist assumptions which ignore considerations of language. Once these assumptions are removed, the proof becomes a simple and straightforward proof without any surprising or counter-intuitive implications.

Below we set out the basic steps of the conventional presentation of the Diagonal proof and the secondary argument, explicitly including the Platonist assumptions that are relied on:

1. The primary Diagonal argument

2. The Secondary argument

At this point the conventional Platonist reading continues:

This is a proof by contradiction, where the contradiction occurs at 2.e above. But a crucial point of any proof by contradiction is that it simply means that one or more of the assumptions made in arriving at the contradiction is incorrect. It does not tell us which of the assumptions is incorrect. The prior assumptions are:

The conventional Platonist viewpoint is that assumption 2.a is the single untenable assumption. There is no logical reason to cherry pick this assumption as the one and only untenable assumption in this list. In fact, as noted in previous chapters, there are sound logical reasons why a real number cannot be the sum of an infinite quantity of ever decreasing fractions, so that assumption 1.b is logically untenable. As for assumption 1.a, if one starts off with the assumption that real numbers are ‘actual’ things that ‘exist’ independently of any language, then it is hardly surprising if one ends up with the result that there are real numbers that ‘exist’ independently of any language ! And what are we to make of assumption 1.e, which is that although we cannot actually define a Diagonal number in any logically valid mathematical notation, it nevertheless ‘exists’ as some definite mathematical numerical value, which can never be written down in any shape or form? Having assumed that, is it really any surprise that the conclusion is that there are numbers that we cannot actually define in logically valid mathematical notation, that we can never write down in any shape or form, but that nevertheless – they ‘exist’⁠? In any case, that assumption leads directly to a logical contradiction, see Appendix: Assuming that the diagonal number “exists” below.

We see now that step 2.d above relies on the Platonist assumptions noted above. For a valid proof, the definition of the Diagonal number has to be a definition in some language. And since the definition is in terms of a list, if the list and the numbers in the list are all in the same language as the definition of the Diagonal number, then in principle, there should be no difficulty in defining the Diagonal number - provided it is a partial list, rather than a list of all real numbers. In such cases, the list consists of a finite string of symbols of the language in question. And for any given natural number, the list will define a real number that corresponds to that natural number; again, that real number will consist of a finite string of symbols of the language in question. (Footnote: Obviously, since all such numbers in the list are given in terms of a finite string of symbols, none of the irrational numbers in the list can actually be written down as an infinitely long string of numeric digits.) And for such a case, the Diagonal proof is a perfectly logical and valid proof.

However, if the list is in a meta-language to the real numbers, which actually is the case for the Secondary argument (see Secondary Argument and 2.b. above) then it is not obvious that a Diagonal number can be defined from such a list. A dictionary style list may be a list that is in a language that is a meta-language to the language in which the real numbers are expressed, i.e: a language that can talk about a language of real numbers (this is covered in more detail in Real Numbers and Language). And, as shown in A List of Real numbers with no Diagonal Number, for the case of a list which is in a different language to the numbers in the list, if we do not make any Platonist assumptions, the Diagonal argument fails to give a mathematically valid definition of a new number that is not in that list.

And since that is the case, then it is illogical to simply assume that there is no difficulty in defining a Diagonal number from such a list, or that a Diagonal number nevertheless ‘exists’ in some undefinable way. In a meta-language, the strings of symbols of the sub-language of real numbers are simply that - strings of symbols which are devoid of any mathematical value in that meta-language. And as pointed out above, any representation of the value of an irrational number in any language is not by any binary or decimal expansion, but by some definition that defines that value. The problem of how the n^th digit of the decimal or binary string is obtained in this meta-language from this definition, when the strings of symbols are devoid of any mathematical value in that language is a problem that is not even mentioned by the Diagonal proof. In short, the secondary argument is devoid of any logical derivation of its conclusion from its premises.

All we can conclude from the Diagonal argument, when divested of its unfounded assumptions that real numbers ‘exist’ as ‘actual’ things independently of language, is that there cannot be a matching function from all natural numbers to all real numbers in the same language as the language for those real numbers. That’s all.

When the Platonist assumptions that underlie the Diagonal argument are revealed by a logical analysis, the absurdity of the argument becomes readily apparent. The secondary argument can now be seen as an implausibly circular argument, where the initial assumption that real numbers ‘exist’ as ‘actual’ things independently of language serves, unsurprisingly, to lead to the conclusion that there are real numbers that ‘exist’ as ‘actual’ things independently of language.

Without the unfounded Platonist beliefs that prop it up, the Diagonal argument cannot provide any proof that there cannot be a list of all real numbers. It doesn’t prove that there are ‘more’ real numbers than natural numbers, nor does it prove that some infinities are ‘bigger’ than other infinities. It doesn’t prove that there are any such things as real numbers that are not expressible by any finite combination of symbols.

All it shows is that if you start off with an assumption that mathematical entities can ‘exist’, but which cannot be written down in any shape or form, even in principle, then you end up with the result that there are mathematical entities can ‘exist’, but which cannot be written down in any shape or form (inaccessible​/​indefinable numbers). But why would anyone want to assume such archaic beliefs when a simple logical consideration of language gives a penetrating insight into the real reason why there can be no list of all real numbers in the same language as those real numbers?

For more on Platonism see Platonism, The Myths of Platonism and Platonism’s Logical Blunder

Fully Formal proofs of the Diagonal proof

You may come across formal proofs of the diagonal argument; an example can be found online at PDF A Cantor Trio: Denumerability, the Reals, and the Real Algebraic Numbers by Ruben Gamboa & John Cowles. Or you may find formal proofs of arguments similar to the diagonal proof and that also proves that there is no function that defines a one-to-one correspondence between the natural numbers and the real numbers, for example see The Real Numbers are Uncountable at the Metamath Proof Explorer.

These proofs state that they are formal proofs of the non-denumerability of the real numbers. However, the reality is that such proofs only prove the primary argument, that is, they only prove that there cannot be matching function from all natural numbers to all real numbers in the same language as the language for those real numbers. Of course, in a correctly formulated fully formal proof, it must be the case that the function that is assumed to exist and which maps the natural numbers to the real numbers must necessarily be in the same language as the real numbers of the proof.

For this reason, it is important to note that these formal proofs do not prove that there cannot be a language with a finite number of symbols and which can express all real numbers. And so these fully formal proofs cannot prove the secondary argument - that is, they cannot prove that there are ‘more’ real numbers than natural numbers. Yet you will find people making the erroneous claim that these formal proofs are conclusive evidence that there must be real numbers that cannot have any finite representation.

Problems with Indefinable real numbers

For an amusing example of how mathematicians can manage to tie themselves into knots trying to explain away the contradictions arising from the secondary argument, see the answer on the math-overflow site by Joel David Hamkins to a simple question regarding indefinable​/​inaccessible numbers. Hamkins begins with, “The concept of definable real number, although seemingly easy to reason with at first, is actually laden with subtle metamathematical dangers … ”. A very apt observation, but the very concept of indefinable real number itself arises from ignoring these subtle meta-mathematical dangers in the first place, i.e: ignoring levels of language and meta-language.

Hamkins gets close to admitting that the diagonal argument cannot apply across different levels of language, at one point essentially remarking that given a set of countably many formulas which are true for only one single value of the free variable, there is no definable function that gives a one-to-one correspondence of the formulas to those singular values, and because of that, a diagonal procedure cannot be defined, so it is not possible to produce a new formula that is not in the list.

But what he fails to address is why this situation is in essence any different to the situation of real numbers rather than formulas – surprising, since for every real number anyone has ever encountered, there is a corresponding formula. Instead he sticks to the Platonist belief that real numbers somehow ‘exist’ independently of any symbolic notation whereas formulas do not.

Applicability to all similar proofs

The conclusion above also applies to other similar proofs. This includes Cantor’s 1874 proof that there can be no function that gives a one-to-one correspondence of real numbers and natural numbers; as for the above the proof demonstrates this for a function that is in the same language as the function and the real numbers referred to by the function.

Another proof is that of the Power Set proof, which is essentially the Diagonal proof in another guise; the Power Set proof states that, given a set A with an infinite number of elements, there cannot be a function that matches each element of the Power Set of A to each element of the set A; that is, there is no function that matches every element of the set A to every subset of the set A. Again, as above, this proof demonstrates that this applies for a function that is in the same language as the sets referred to by the function.

Appendix: Platonist assumptions of ‘existence’

Platonists believe that every list of irrational numbers is an ‘actual’ thing that ‘exists’, and that in some way lists numbers that ‘exist’ as limitlessly large sums of fractions of ever decreasing size. Platonists say that any expression that we write down as a definition is not the ‘actual’ thing itself, but is a representation of some such ‘actual’ thing. For example, the list

1, ⁶⁄₇, √ 5 , Pi, ^1.7√ 31 

is for the Platonist, not a list of numbers, but is a symbolic representation of an ‘actual’ list of ‘actual’ real numbers. So, when a Platonist presents the diagonal proof and the proof proceeds by saying something like:

 

“Let us suppose that the beginning of a list of real numbers is as follows:

r(1) = 0.101011110101 …

r(2) = 0.00010100011 …

r(3) = 0.0010111011110 …

r(4) = 0.111101010111 …

 

where the dots … represent infinitely long strings of digits.”

 

the Platonist ignores the fact that one cannot define any list including irrational numbers in this way - not even a list consisting of only one irrational number. The presentation of the list in this way obscures the fact that any definition of a list of real numbers that includes irrational numbers must provide the values of these numbers as definitions.

 

Wilfrid Hodges, in a well-known paper says: (Footnote: Wilfrid Hodges, PDF An Editor Recalls Some Hopeless Papers, The Bulletin of Symbolic Logic, Vol 4, No. 1, March 1998.)

“Of course nobody would suggest that in order to carry out Cantor’s proof you actually have to write out the infinite diagram, would they? Would they?”. He then goes on to quote from Kleene’s ‘Introduction to metamathematics’ (Footnote: Stephen Cole Kleene, Introduction to metamathematics, North-Holland, Amsterdam, 1952.) as follows:

 

Now suppose that x₀, x₁, x₂, x₃, … is an infinite list or enumeration of some but not necessarily all of the real numbers belonging to the interval. Write down one below another their respective non-terminating decimal fractions … [and here follows a diagram with some dot-dot-dots].

 

Hodges continues, “Taken literally, what Kleene says is quite mad. Of course one can avoid taking it literally by saying something like (3) in my version.” But Hodges’ version is the version above with a finite number of digits followed by dots, and Hodges claims that he avoids Kleene’s impossible instruction by his own instruction to write the numbers as finite strings of digits that terminate with dots. But that fails to address the problem; if one had such a list, then this list cannot distinguish between any numbers whose initial digits (those before the dots) happen to be identical, and it would not be a list of specific numbers at all. What it would be is a list of sets of numbers - each set being the set of real numbers that start with a certain set of digits.

 

Of course, what Hodges is really doing here is making a Platonist assumption that real numbers exist as ‘actual’ things independently of any human symbols, and that in his ‘list’ that consists of finite strings of digits followed by dots, although there can be infinitely many identical such strings of symbols in his ‘list’, each item in the list nevertheless corresponds to some individual unique real number that somehow ‘exists’ completely independently of the symbols in his ‘list’.

Footnotes:

Appendix: Assuming that the diagonal number “exists”

The Platonist notion that we can ignore considerations of language, and which claims that given any set of numbers that can constitute a list, there “exists” an associated diagonal number for that list, and which “exists” completely independently of any language, leads directly to a contradiction, as follows: (Footnote: See also PDF On Considerations of Language in the Diagonal Proof.)

 

Given an infinite list of real numbers between 0 and 1 (such as the binary expansion of all numbers that are the square root of n, where n is a natural number), we analyze the consequences of the Platonist assumption that a diagonal number “exists”, regardless of what any definitions we might make regarding that list.

 

Given an infinite list of real numbers and the assumption that the diagonal number “exists”, then there “exists” another new list, which is the same as the previous list except that it also has that diagonal number in the list, as the first number in the list, and where all the other numbers are each shifted up one place (as in Hilbert’s hotel). The new list has one more item than the previous list, and every real number in the new list is thus uniquely associated with a natural number.

 

And for that new list, a different new diagonal number must also “exist”, and which is different to every number in that list. And so, from that new list there “exists” another newer list which includes that new diagonal number. And so on, and so on. Every new list gives rise to a new diagonal number, and every such list and every such diagonal number gives rise to a new list that includes that diagonal number.

 

By the Platonist assumption, every diagonal number that can be given by such lists “exists”. And every such list “exists”. That means that there “exists” a list that consists of the original list and all such diagonal numbers. (Footnote: Note that it is completely immaterial to the point in question (that numbers that “exist” independently of any definition leads to a direct contradiction) as to whether that list constitutes all real numbers.)  (Footnote: Note that a list is simply a set of ordered pairs - in this case the first of the pair is a natural number, and the second of the pair is either a number of the original list or a diagonal number. So if there is an assumption that sets of numbers “exist”, then lists of numbers “exist”.)

 

But we now have a contradiction, since on the one hand, there “exists” a list that includes every number of the original list and every consequent diagonal number; but on the other hand, by the principle of the diagonal proof, for any list, there must always “exist” a diagonal number that is not in that list.

 

That is a contradiction that is the direct consequence of Platonist assumptions that mathematical entities “exist” independently of any definition.

 

The reason why definitions of diagonal numbers cannot give rise to such a contradiction is because such definitions involve recursive iterations that can never terminate. And although one can define a set as the limiting resultant set of such recursions, one cannot logically define a list that is the limiting resultant list of such recursions. And since the definition of a diagonal number requires a list, a contradiction cannot arise from the definitions.

Footnotes: