Footnotes:
The Diagonal Proof (v1)
Page Contents
Platonist assumptions in the secondary argument
Fully Formal proofs of the Diagonal proof
Problems with Indefinable real numbers
Applicability to all similar proofs
Indefinables and the Secondary Argument
Appendix: Platonist assumptions of ‘existence’
Appendix: Indefinable Lists that ‘exist’
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, 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’ 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
1.
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.
2.
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. We will later address the question of whether there can be such a list that includes every real number.
3.
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 …
4.
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 …
5.
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.
6.
So, given any list of real numbers we can always define another real number that is not in that list – the Diagonal number.
7.
We now assume that there can be a list that includes every real number.
8.
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.
9.
That means that the assumption that there can be a list that includes every real number (Step 7 above) is incorrect.
10.
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 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
1.a.
Assumption: Real numbers are ‘actual’ things that ‘exist’ independently of any language.
1.b.
Assumption: Real numbers ‘exist’ as the sum of an infinite quantity of ever decreasing fractions.
1.c.
Take any list of real numbers.
1.d.
Given a list of real numbers where the list is in the same language as the real numbers, a Diagonal number can be defined in terms of the list, such that the Diagonal number is not a number in the list.
1.e.
Assumption: If the list is in a different language to the language of the numbers in the list, there nevertheless ‘exists’ a Diagonal number, even though no method of defining such a Diagonal number is given.
1.f.
Assumption: There can be a list of all real numbers
1.g.
Then there is a contradiction, since the Diagonal number would be both in the list and not in the list.
1.h.
Therefore there is no list of all real numbers.
2. The Secondary argument
2.a.
Assumption: There is a language that can express all real numbers.
2.b.
Then a dictionary style list of all possible expressions of that language can be made, and this list includes all the real numbers of that language.
2.c.
Therefore, if there was a language that could express all real numbers, then we would have a list of all real numbers.
2.d.
Then we would have a new Diagonal number.
2.e.
Then there is a contradiction, since the Diagonal number would be both in the list and not in the list.
At this point the conventional Platonist reading continues:
2.f.
Therefore the assumption 2.a that there is a language that can express all real numbers must be incorrect.
2.g.
Therefore there is no language that can express all real numbers.
2.h.
Therefore there must be real numbers that cannot be expressed by any language. (Footnote: Also called inaccessible numbers or indefinable numbers.)
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:
1.a.
Assumption: Real numbers are ‘actual’ things that ‘exist’ independently of any language.
1.b.
Assumption: Real numbers ‘exist’ as the sum of an infinite quantity of ever decreasing fractions.
1.e.
Assumption: If the list is in a different language to the language of the numbers in the list, there nevertheless ‘exists’ a Diagonal number, even though no method of defining such a Diagonal number is given.
1.f.
Assumption: There can be a list of all real numbers
2.a.
Assumption: There is a language that can express all real numbers.
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 nth 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.
Indefinables and the Secondary Argument
As we have noted above, the secondary argument claims that there are real numbers that cannot have any finite definition (indefinable/inaccessible numbers). If that is the case, for any such real number there can be no definable function that gives a one-to-one correspondence between the natural numbers and the decimal digits of such a number - otherwise the number would be definable.
Now, it is obvious that we can enumerate all symbol combinations of the form of 0⁄10, 0⁄100, 0⁄1000, … to define a set A; and that we can enumerate all symbol combinations of the form of 1⁄10, 1⁄100, 1⁄1000, … to define a set B. So both of the sets A and B are denumerable.
And it can easily be shown that the union of the two sets A and B is also denumerable. Furthermore, by the conventional rules, any subset of a denumerable set is also denumerable. This means that every possible set of combinations of symbols of the form of 0⁄10, 0⁄100, 0⁄1000, … and of the form of 1⁄10, 1⁄100, 1⁄1000, … is denumerable. So every decimal expansion is denumerable.
This means that the secondary argument implies that we can have a set that is denumerable, but that there is no definable function that can define an enumeration of that set. Otherwise, every real number would be definable, while the secondary argument asserts that this cannot be the case. In other words, the secondary argument claims that there can be sets where there is a one-to-one correspondence from the natural numbers to the elements of the set, but that one-to-one correspondence cannot be defined.
Now, given that the secondary argument leads to that conclusion, let’s look again at the Diagonal proof. At the outset of the proof we assume that there can be a one-to-one correspondence of the natural numbers and any set of real numbers. But the secondary argument asserts that there are one-to-one correspondences to natural numbers that are not definable, and therefore, according to the secondary argument we have to admit the possibility that there is a list of the real numbers, but that list is not definable. And if such a list ‘exists’ but is not definable, then there is no way of defining which real number is associated with any given natural number, and so in that case it is impossible to define a diagonal number - we couldn’t even tell what the first digit is ! So, if you accept the secondary argument, you must also admit the possibility that there are indefinable lists of real numbers, in which case you also have to assume that a diagonal number can ‘exist’ even though there can be no definition of such a number. For more on this, see Appendix: Indefinable Lists that ‘exist’ below.
And this is not because of any inherent flaw in the Diagonal proof - which is a perfectly logically valid proof provided the limitations of language are observed. No, in this case it fails because the secondary argument includes assumptions which are without any logical or evidential foundation.
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 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, √
, Pi, 1.7√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’.
Footnotes:
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.
If we explicitly include these assumptions along with the previously noted Platonist assumptions we now have:
1. The primary Diagonal argument
1.a.
Assumption: Real numbers are ‘actual’ things that ‘exist’ independently of any language.
1.b.
Assumption: Real numbers ‘exist’ as the sum of an infinite quantity of ever decreasing fractions.
1.b2.
Assumption: Lists of ‘actual’ real numbers can ‘exist’ independently of any language
1.c.
Take any list of real numbers.
1.d.
Given a list of real numbers where the list is in the same language as the real numbers, a Diagonal number can be defined in terms of the list, such that the Diagonal number is not a number in the list.
1.e.
Assumption: If the list is in a different language to the language of the numbers in the list, there nevertheless ‘exists’ a Diagonal number, even though no method of defining such a Diagonal number is given.
1.f.
Assumption: There can be a list of all real numbers
1.g.
Then there is a contradiction, since the Diagonal number would be both in the list and not in the list.
1.h.
Therefore there is no list of all real numbers.
2. The secondary argument
2.a.
Assumption: There is a language that can express all real numbers.
2.b.
Then a dictionary style list of all possible expressions of that language can be made, and this list includes all the real numbers of that language.
2.c.
Therefore, if there was a language that could express all real numbers, then we would have a list of all real numbers.
2.d.
Then we would have a new Diagonal number.
2.e.
Then there is a contradiction, since the Diagonal number would be both in the list and not in the list.
2.f.
Therefore the assumption that there is a language that can express all real numbers must be incorrect.
2.g.
Therefore there is no language that can express all real numbers.
2.h.
Therefore there must be real numbers that cannot be expressed by any language.
As before, we have a contradiction at step 2.e above, hence at least one of the assumptions before that step must be inadmissible, that is, that one or more of the following assumptions is untenable:
1.a.
Assumption: Real numbers are ‘actual’ things that ‘exist’ independently of any language.
1.b.
Assumption: Real numbers ‘exist’ as the sum of an infinite quantity of ever decreasing fractions.
1.e.
Assumption: If the list is in a different language to the language of the numbers in the list, there nevertheless ‘exists’ a Diagonal number, even though no method of defining such a Diagonal number is given.
1.e2.
Assumption: 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.
1.f.
Assumption: There can be a list of all real numbers
2.a.
Assumption: There is a language that can express all real numbers.
Again, as noted before, the conventional Platonist viewpoint is that assumption 2.a is the single untenable assumption. The only difference here is that there are additional assumptions that may be the source of the contradiction – 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. How can anyone seriously entertain such absurdities?
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:
Rationale: Every logical argument must be defined in some language, and every language has limitations. Attempting to construct a logical argument while ignoring how the limitations of language might affect that argument is a bizarre approach. The correct acknowledgment of the interactions of logic and language explains almost all of the paradoxes, and resolves almost all of the contradictions, conundrums, and contentious issues in modern philosophy and mathematics.
Site Mission
Please see the menu for numerous articles of interest. Please leave a comment or send an email if you are interested in the material on this site.
Interested in supporting this site?
You can help by sharing the site with others. You can also donate at where there are full details.