Cantor’s Diagonal Proof
(On an Elementary Question of Set Theory)
Page last updated 08 Aug 2023
If you have come to this page expecting a denunciation of the method used in Georg Cantor’s diagonal proof, you may be disappointed. There is absolutely nothing wrong with the underlying method of the Diagonal proof, provided (as for any other proof method) that it is used without making additional unfounded assumptions. The method gives perfectly valid proofs; for example, in a given mathematical system, it proves that there cannot be a one-to-one correspondence of the real numbers and natural numbers of that system.
However, most conventional presentations of the Diagonal proof take the fundamental result of the proof and attach untenable illogical assumptions to that result, and which unsurprisingly give rise to untenable and illogical conclusions.
It was Cantor himself who started this by simply assuming that if there could not be any one-to-one correspondence between the elements of two infinite sets, then if the sets could be said to have the same number of elements, then that would be a contradiction. His “solution” to this imaginary “contradiction” was to introduce instead a brazenly obvious contradiction - that one set, that has no limit to how many elements it can have - can somehow have fewer elements than another set with no limit to how many elements it can have.
And, despite the blatant fact that, over the 150 years since Cantor introduced it, there has never been any proof of his assumption that the absence of a one-to-one correspondence between the elements of two infinite sets implies that one infinite set has “more” elements than the other, in today’s mathematics it has become an unchallengeable dogma that must not be questioned. But in fact there is an incredibly simple reason why it might not be possible to put two infinite sets into a one-to-one correspondence - it can happen simply because of the particular properties of their elements - and which has nothing whatsoever to do with how many elements the sets have - we will deal with this in more detail later on this page.
Taking the above considerations into account, we will now proceed to an analysis of the diagonal proof. It is often called Cantor’s proof, because Georg 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:
Georg Cantor, “Über eine elemtare Frage de Mannigfaltigkeitslehre”, Jahresberich der Deutsch. Math. Vereing. Bd. I, S. pp 75-78 (1891)
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 an online English translation of the original proof, together with the original German at On an Elementary Question of Set Theory (Über eine elemtare Frage de Mannigfaltigkeitslehre).
An analysis of the proof is given 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, 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). (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’ 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’/
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
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. (Footnote: Note: the phrase “any list of real numbers” does not imply (contrary to the belief of some people) that any such list must include a list of all real numbers, it simply refers to some list of real numbers; for example 1⁄2, 1⁄3, 1⁄4, … is an example of a list of real numbers.)
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. (Footnote: For example, a list that has infinitely many real numbers (but not all), including irrationals is the function f (n) = Square root of n, where n can be any natural number. ) 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. (Footnote: Note that this proof outline is simplified, and that the notion that there exists a sum of infinitely many fractions (here as decimal digits) is contradictory, see Sums of infinitely many fractions: 1 and Sums of infinitely many fractions: 2. But a definition of a diagonal number as the limit of the summation of digits defined by every nth digit being the complement of the nth digit of the nth number in the list could be valid.)
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.
The Secondary Argument
Following on from the above primary result of the Diagonal proof, a Secondary Argument is commonly attached to the proof. This is the claim that if there cannot be a one-to-one correspondence between two limitlessly large sets then one of the limitlessly large sets must be smaller than the other limitlessly large set. It was Cantor who started the promulgation of this bizarre notion by simply assuming (as he does in the second part of his 1891 paper) that if there could not be any one-to-one correspondence between the elements of two infinite sets, then if the sets could be the same size, then that would be a contradiction. His “solution” to this imaginary “contradiction” was to introduce instead a brazenly obvious contradiction - that one limitlessly large set can be smaller than some other limitlessly large set.
In fact the absence of a one-to-one correspondence between the elements of two infinite sets actually results from differences in the properties of their elements, not from any difference in their quantity, see One-to-one Correspondences and Properties.
For finite sets, a one-to-one correspondence between two sets with the same number of elements can always be given without any reference to the properties of the elements of the sets, by simply creating an actual list (e.g. 1:A, 2:B, 3:C). Replacing any element by some other element (not already in the set) cannot change the cardinal number of the set, so that the cardinal number of any finite set is a property that is independent of the properties of its elements.
For infinite sets it is not possible to create an actual list (since such a list would be infinitely long). A one-to-one correspondence can only be given by a definition of a function that defines that one-to-one correspondence in terms of the properties of the elements of the sets. (Footnote: For example, the function 2x defines a one-to-one correspondence between the set of positive integers and the set of even positive integers.)
Hence, although the impossibility of defining a one-to-one correspondence between two finite sets implies that there is a difference in a property of the sets, where that property is independent of the actual details of the elements of the sets, the impossibility of defining a one-to-one correspondence between two infinite sets implies that there is a difference in the properties of the elements of the sets, rather than a difference in a property of the sets that is independent of the actual details of the elements of the sets. (Footnote: The same applies to the impossibility of a surjection between two given infinite sets, this is discussed in more detail on the page Surjections and Cardinal Numbers.)
The entire field of transfinite numbers has arisen from the uncritical acceptance of Cantor’s unfounded assumption, (Footnote: Cantor’s deeply held religious beliefs led him to believe that transfinite numbers were like a path to god, see Cantor’s religious beliefs and his transfinite numbers.) and continues to turn a blind eye to this fundamental difference between finite sets and between infinite sets in relation to the presence or absence of a one-to-one correspondence between two sets. It remains as nothing more than an illogical assumption - no proof of this assumption has ever been discovered, see Proof of more real numbers than natural numbers? and Cardinal Numbers and The Origins of Transfinite Numbers. It is hardly surprising that no logically valid proof of it has ever been found since the notion of one limitlessly large set being smaller than another limitlessly large set is inherently contradictory. (Footnote: In spite of the obvious contradiction, most mathematicians and logicians bow to the conventional adherence to the unproven assumption, see Why do people believe weird things?)
Inherent in the claim that infinite sets can be of different sizes is the concomitant Platonist claim that there must be ‘indefinable’ real numbers - numbers that somehow ‘exist’, but which can never be defined and that there are ‘more’ of these ‘indefinable’ numbers than definable numbers, even though there is no limit to the quantity of definable numbers (see also The contradictions of “indefinable” numbers). (Footnote: Note: from this point onwards, this page has been updated to provide a much simpler demonstration of the flaw in the Secondary Argument. There was no error in the previous demonstration which can still be viewed at diagonal proof v1 in its entirety.) This is a quite extraordinary claim. As Christopher Hitchens said: (Footnote: Christopher Hitchens 1949–2011 English-born American journalist and writer, in the book God Is Not Great: How Religion Poisons Everything, McClelland & Stewart, 2008. See also Hitchens’s razor.)
“What can be asserted without evidence can also be dismissed without evidence.”
“… exceptional claims demand exceptional evidence.”
So what is the evidence to support the claim? The basis for this claim has its origins in Section 1 of 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 online
For any language with a finite alphabet, the sequences of symbols of that alphabet are denumerable; first enumerate all single symbols by setting them in a definitive order (an alphabetical dictionary style order, also called a lexicographical order), then enumerate all sequences of two symbols, again using the same definitive order already established. Sequences of three symbols are similarly enumerated, and so on for longer sequences. (Footnote: Note that any such enumeration is infinite, and cannot be given as an actual finite list, it can only be given by some definition.)
The argument continues:
However, the set of real numbers is not denumerable. That means that it doesn’t matter how comprehensive the language is, there exist numbers that can’t be defined in that language. This means that there must exist real numbers that cannot have any finite definition. (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 valid evidence that cannot be summarily dismissed? Is it exceptional evidence?
No - and it will be explained why in the following:
When the argument states that the set of real numbers is not denumerable, this is a statement that relies completely on the unproven assumption that given any enumeration, the diagonal argument shows that there always ‘exists’ a diagonal number that is not in that enumeration. (Footnote: Note that there is an earlier version of this page that uses a similar but slightly different argument to that given below - this newer version replaced it simply because it provides an easier argument - there was nothing wrong with the earlier argument, which can be seen at The diagonal proof - version 1.)
But a simple logical analysis shows that this assumption cannot be correct. Observe that the diagonal proof necessarily defines a diagonal number in terms of an enumeration where the nth digit of that number is given by taking the nth digit of the nth number in the enumeration and replacing that digit by a specified different digit. Hence every diagonal number is a definable number. (Footnote: Provided it is well-defined. For the proof to be logically valid, the definition of the diagonal number will not rely on vague expressions of natural language; it must always be the case that the definition of the diagonal number is, for any enumeration of real numbers, a completely clear and unambiguous definition.) So we have the contradiction where, given a list of all definable numbers of a given language, the diagonal number must be one of the items in the enumeration, since it is definable, but at the same time the diagonal number is supposedly a new number that is not in the enumeration.
To understand the origin of the contradiction, consider any given mathematical language L with a well-defined alphabet A and which is capable of stating the diagonal argument. (Footnote: If the diagonal argument is actually mathematics, then it must be possible to state it in a mathematical language. And in fact there are formal expositions of the diagonal argument in well-defined formal mathematical languages, see Fully Formal proofs of the Diagonal proof below.) The conventional claim is that for any given enumeration of real numbers (which can also be an enumeration of a set of some but not all real numbers) the diagonal proof defines a real number that is not in that enumeration. If that is the case, then there must be a sequence of symbols in that language L that defines a diagonal number in terms of any given enumeration of some set of real numbers. Let E be the enumeration of all sequences of symbols of that alphabet A, and which can be defined as in the Secondary Argument stated above.
The conventional claim is that given any enumeration, the diagonal argument shows that there always ‘exists’ a diagonal number that is not in that enumeration. And since the diagonal number in this case is defined in the language L using symbols of the alphabet A, then there must be a sequence of symbols in the alphabet A that defines the diagonal number in terms of the enumeration E.
But this gives rise to a contradiction, since now there must be some n where the diagonal number is the nth real number in the enumeration E - since it is a sequence of symbols of the alphabet A - but at the same time it cannot be in the enumeration since its nth digit is defined as being different to its nth digit, which is impossible.
The unfounded assumption that definitions are independent of language
When we have a contradiction, as in the above, then either there is at least one step that is not logically valid, and/or at least one of the assumptions used in the argument is untenable. In this case, the contradiction arises directly from the naive assumption that any definition of the diagonal number is completely independent of the language in which the enumeration is defined.
By simply rejecting that naive assumption, we have the result that the Diagonal argument shows that, within a given mathematical system, there cannot be any enumeration of the set of all real numbers that can be defined within that mathematical system. And all the conundrums, contradictions and paradoxes that are consequent to that naive assumption simply disappear.
Of course, we can observe that there can be enumerations of the definitions of real numbers of a given mathematical system outside of that mathematical language, in a meta-language that is outside of that mathematical system - but the crucial point is that the Diagonal argument tells us absolutely nothing about such an enumeration, since it cannot show that there can be a logically valid definition of a diagonal number outside of that mathematical system.
It is a commonly accepted mathematical method of proof that if an argument which entails certain assumptions leads to a contradiction, then one or more of those assumptions is untenable or there is one or more illogical steps in the argument. But for the case of infinite sets mathematicians have turned this principle completely upside down. They claim that they can “solve” the above apparent contradiction by replacing it with a blatant contradiction - that one set with limitlessly many elements can have fewer elements that another set with limitlessly many elements.
A Simple Proof of the Diagonal result
The aforementioned apparent contradiction disappears when it is observed that the enumeration of all sequences of symbols of the alphabet A cannot be expressed by a sequence of symbols of the alphabet A. This provides a very simple proof of the primary conclusion of the diagonal proof, which is that there cannot be a list of real numbers and which is in the same language as those real numbers, viz:
Suppose that there was an enumeration of all sequences of symbols of an alphabet A. That enumeration would be a function with a free variable, which must be represented either by a single symbol, or by a string of symbols, and which has the domain of natural numbers. Immediately we see that regardless of what number replaces that variable, the result is a different sequence of symbols to that which expresses the enumeration function, since the variable is replaced by a number. Hence there is no number for which the function results in the exact sequence of symbols that is that function itself, and hence there can be no complete enumeration of all the sequences of symbols of that alphabet, and which is itself a sequence of symbols of that alphabet.
Furthermore, it is easily shown by another method that in any language there cannot be a function that enumerates all the real numbers that can be expressed in that language. This is fully detailed on the page Non-Diagonal Proofs: Enumerations in different language systems.
The assumption that the diagonal number is totally independent of language has no logical basis, and as shown above, it results in a direct contradiction. Having seen the obvious flaw in the argument that there ‘exist’ numbers that are ‘indefinable’, why would anyone want to believe in this arcane mystical notion that arose in the 19th century when supernatural beliefs were widespread? Similar metaphysical notions that were prevalent in various branches of science in the 19th century have long since been rejected as supernatural nonsense. Surely mathematics should be leading the way in the application of strict logic, rather than trailing miserably in the wake of the sciences?
A List of Real numbers with no Diagonal Number
For a proof that there can be a valid list of real numbers for which no Diagonal number exists, see A List of Real numbers with no Diagonal Number. This analyses the case of a list which is in a different language to the numbers in the list.
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 conventionally 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 presentation of the Diagonal proof, which includes the Secondary Argument, is a Platonist presentation which ignores crucial considerations of language.
Conventionally, Platonists assume that the diagonal number must always ‘exist’ independently of any definition of the diagonal number. And a Platonist might try to circumvent the contradiction demonstrated above by claiming that the diagonal number somehow nevertheless ‘exists’, even if it cannot be defined. But that is an absurdly circular argument, since it requires assuming the ‘existence’ of a number that cannot be defined in order to prove that there ‘exist’ numbers that cannot be defined. That isn’t mathematics, it isn’t logic, it is philosophical hogwash.
Once such assumptions are removed, the proof becomes a simple and straightforward proof without any surprising or counter-intuitive implications.
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 for certain partial lists of real numbers. (Footnote: Provided the partial list is in the same mathematical language as the definition of the diagonal number and the real numbers; for example f(n) = √ n (the square root of n) for n a natural number, gives a partial list of real numbers. As noted elsewhere on this page, a complete enumeration of all sequences of a language in that same language is not possible.) 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 then a diagonal number cannot be defined from such a list, and the assumption that it can be defined from such a list results in a contradiction. For more on meta-language and real numbers see Real Numbers and Language.
All we can conclude from the Diagonal argument, when divested of any unfounded assumptions that 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 the diagonal number ‘exists’ as an ‘actual’ thing 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 mystical Platonist beliefs that prop it up, the Diagonal argument 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 mathematical entities can ‘exist’, but which cannot be written down in any shape or form (‘inaccessible’ or ‘indefinable’ numbers). But why would anyone want to assume such outdated circular 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?
‘More’ than limitlessly many numbers…
There is an absurd assumption that if there cannot be a one-to-one correspondence between two infinite sets, then one set must have more elements than the other. While this is true for finite sets, there is no logical reason why this should also apply to infinite sets. In fact, the assumption that it does flies directly in the face of the obvious contradiction - which is that you cannot have a set that has more elements than a set that has a limitless quantity of elements. Mathematicians and logicians simply turn a blind eye to this blatantly obvious contradiction.
Note that the claim that there are ‘more’ real numbers than natural numbers is a claim that has no mathematical foundation whatsoever. You will never encounter a step by step logical proof of the notion that, since two finite sets have different numbers of elements if there cannot be a one-to-one correspondence between the sets, then the same applies to infinite sets. There’s no mathematics to be found underlying this bizarre claim, only puerile pseudo-philosophy. For more detail on this, see One-to-one Correspondences and Properties.
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 which also prove 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 ‘indefinable’ numbers, or 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 - see also the page The contradictions of “indefinable” numbers.
More problems with “Indefinable” real numbers
Besides the blatant Contradictions of “indefinable” numbers, an amusing example of how mathematicians can manage to tie themselves into knots trying to explain away the contradictions arising from the Secondary Argument is given by an 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 denumerable set of 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.
König’s non-finite definitions
Interestingly, shortly after his 1905 paper, König wrote a follow-up to that paper where he considers an enumerable set where the elements are all finitely defined, and considers that the diagonal method defines a diagonal entity that must be - on the one hand, different to every member of the enumeration, but at the same time - since it is a finite definition, it must be one of the members of the enumeration. Having observed this contradiction, König then engages in an argument where he adds more than ω characters to his finite definitions (where there are different levels of infinity, and ω is the lowest level). He then declares that since these are not finite definitions, a diagonal entity obtained from an enumeration of these definitions is not contradictory since the diagonal method can only deal with ω many characters, and so the diagonal entity is not a member of the enumeration.
Now, while it is the case that the purpose of König’s argument was to show that “the continuum cannot be well-ordered”, it is remarkable that the contradiction that König originally noted remains without any attempt of a resolution or an explanation. But as shown above the explanation is simple: the diagonal method may not be applicable in cases where an enumeration is in a different language to the entities being enumerated. You can see an English translation of König’s Part 2 at König: On the foundations of set theory and the continuum problem: (Part 2).
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.
Why do people continue to defend the indefensible?
It is an intriguing question - why do people prefer to continue to believe something that is blatantly contradictory - that there can be limitlessly large sets that are smaller than other limitlessly large sets? Why is there an immediate knee-jerk reaction against any suggestion that one might be able to remove this contradiction by a full logical analysis of everything involved? See Why do people believe weird things? for some of the reasons for this strange attitude.
For further reading, see also Proof of more Real numbers than Natural numbers and A List of Real numbers with no Diagonal Number and the papers PDF On Considerations of Language in the Diagonal Proof and PDF On the Reality of the Continuum and Russell’s Moment of Candour.
Appendix: Dual Definition
A common criticism of the Diagonal argument is based on the fact that if a number has a finite binary definition, it will also have a definition which ‘ends’ in an infinitely continuing series of 1s; for example, 0.1011101, which is 93⁄128 in standard notation, can also be defined by 0.1011100111… where the expansion continues with infinitely many 1s. The criticism is that there could be a list which gives a number which ‘ends’ in an infinitely continuing series of 1s and which has the same value as a number in the list which has a finite binary definition - or a list which gives a number which ‘ends’ in an infinitely continuing series of 0s and which has the same value as a number in the list which ‘ends’ in finitely many 1s. However, there is a simple way to counter this - instead of changing a single digit of each number in the list, simply take each consecutive pair of digits and change them according to the following rule:
Change 10 to 01 and change every other pair of digits to 10.
In this way, the diagonal number cannot be a number that ‘ends’ in infinitely many 1s. Furthermore, since the diagonal number does not terminate, it cannot have a dual representation, so that it cannot be a finite representation of a number in the list that ‘ends’ in infinitely many 1s. For the list of six numbers considered above, the pairs of digits for the numbers are 10, 01, 11, 01, 11 and 01, and this would give the diagonal number as 0.011010101001.
Appendix: Platonist assumptions of ‘existence’
Platonists believe that every list of irrational numbers is an ‘actual’ thing that ‘exists’, and that such a list 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, 6⁄7, √ 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 x0, x1, x2, x3, … 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’.
Appendix: “Indefinable” Lists that ‘exist’
In response to the above demonstration of the fallacies in the Secondary Argument, a professor made the bizarre claim there might be lists of real numbers that cannot be expressed in any language, and that this would negate the demonstration of those fallacies. However, this just adds yet another Platonist assumption, which is:
● Lists of ‘actual’ real numbers can ‘exist’ independently of any language.
And this in turn gives rise to a further assumption which is:
● If the list cannot be expressed in any language, but ‘exists’ independently of any language, there nevertheless ‘exists’ a diagonal number, even though no method of defining such a diagonal number is given.
The only difference here is that there are additional assumptions – that not only can there ‘exist’ lists that cannot be expressed in any language, but also that a diagonal number ‘exists’ for such a list, even though there is no possibility whatsoever of ever defining such a number. But the entire diagonal argument is based on an argument that specifically defines the diagonal number. How can anyone seriously entertain such absurdities? See also The contradictions of “indefinable” numbers.