A List of Real numbers with no Diagonal Number
Here we will show that it is possible to have a list of real numbers where it can be logically proven that a Diagonal number cannot be defined from that list. Before we get into the details, we will first have a short digression on functions. Consider a simple example of a function that maps every natural number to an even number. The expression ‘2 × x’ is such a function, where x is the free variable of the function. When we substitute the variable x by a specific number, then we get another expression, for example:
for x substituted by 3, we have the expression ‘2 × 3’
for x substituted by 7, we have the expression ‘2 × 7’
for x substituted by 23, we have the expression ‘2 × 23’
Now, as long as we correctly use the rules of the mathematical language to which these expressions belong, there are other expressions that have equivalent values, for example:
2 × 3 = 7 − 1 = 6
2 × 7 = 11 + 3 = 14
2 × 23 = 23 + (4 × 5) + 3 = 46
In common mathematical parlance, we might write:
f (2) = 2 × 3 = 6
f (7) = 2 × 7 = 14
f (23) = 2 × 23 = 46
where f (23) is simply an expression that also represents the expression ‘2 × 23’. In the language of the mathematical system being used, the two expressions are equivalent.
A crucial point to note here is that, of itself, in isolation, the expression ‘2 × 23’ does not necessarily have a value of 46. We normally assume that is the case, because we assume that the expression ‘2 × 23’ is an expression of our standard mathematical language. But, for example, the × symbol does not have to be a multiplication symbol, and in some other language, it could be the symbol for addition, so that, in that language, we would have that ‘2 × 23’ has a value of 25. (Footnote: Provided this language also uses the decimal system and the symbols 0, 1, 2, 3, … for natural numbers.)
We now proceed with the Diagonal argument, without including any Platonist assumptions that there ‘exist’ any ‘actual’ real numbers or ‘actual’ lists of numbers. First we describe a function that defines all of the real numbers that are expressible in some specific language. This language is a mathematical language with a well-defined alphabet of symbols, and is capable of expressing real numbers, some of which will be irrational numbers. We are going to call this the language L. Given the complete alphabet of language L, then it is a straightforward matter to make a list of every possible symbol combination of the alphabet of language L – simply by taking every symbol combination of language L and putting them in a dictionary style order (a lexicographical order). (Footnote: We can arbitrarily choose any alphabetical ordering of the symbols of the language L that we want.)
Obviously this list includes every expression of language L that evaluates in language L as a real number. (Footnote: The list will include symbol combinations that are not numbers, and it will include multiple instances of any given real number. This does not invalidate the principle of the argument. One could specify that for any symbol combination that is not a number, the corresponding digit of the Diagonal number be 0 (if the Diagonal number is definable). For the case of multiple instances of the same number, the Diagonal number (if definable) would still be different to any instance of the number.)
As is demonstrated in Real numbers and Language, such a function cannot be defined in the language L itself. However, we can have a meta-language that can make statements about the language L, and which is capable of defining the list function that we require; we will call this the language H. Provided the language H has sufficient expressiveness, it will have its own unique symbols, and it will also be able to refer to the symbols of language L.
And provided the language H has sufficient expressiveness, there can be an expression of language H that defines a list of all possible symbol combinations of language L. We will call list List and we call the nth symbol combination in this list List(n). Again, we note that List is a clearly defined function. (Footnote: Note that we can have a language that only uses the symbols 0 and 1. Another language can be translated into such a language, for example, by translating each single symbol into a combination of the symbols 0 and 1. Note that numbers will then be represented not as binary numbers but by some coding of the symbols 0 and 1.)
For the language H, this is a simple expression, since it follows a simple pattern and ignores any meaning that is attached to the symbols by the language L. This expression will have a free variable (which we call n), which can be substituted by any natural number. And when it is substituted, we get a new expression, where there now is some natural number in the place of the free variable n. (Footnote: Note that the free variable can appear several times in the expression – when we talk about the free variable being substituted, we mean that all occurrences of the free variables in the expression are substituted.)
Now consider what happens if we try to apply the Diagonal argument to this partial list. Central to the Diagonal argument is the assertion that if there is a list of real numbers, then the Diagonal argument defines a Diagonal number, a number that is not in the list. Logically, it must be possible to clearly define that definition of the Diagonal number in some specific language; otherwise it cannot be a logical definition. It might be worth noting that Cantor himself accepted that definitions of numbers must be unambiguous. (Footnote: ‘One is only obliged with the introduction of new numbers to give definitions of them through which they achieve such a definiteness and possibly such a relation to the older numbers that in given cases they can be distinguished from one another. As soon as a number fulfills all these conditions, it can and must be considered in mathematics as existent and real.’ Georg Cantor: ‘Über unendliche lineare Punktmannigfaltigkeiten’, Mathematische Annalen 5, 21 (1883) pp 545-586.)
Clearly, in this case, the Diagonal number is not defined in language L, since the Diagonal number is defined in terms of the list and the list is defined in language H. So perhaps the Diagonal number is defined in the language H? Perhaps like this: (Footnote: Note that we are working in binary notation.)
The Diagonal number is defined by defining its nth digit to be 0 if the nth digit of List(n) in binary notation is 1, or 1 if the nth digit of List(n) in binary notation is 0. If List(n) is a symbol combination that is not a real number, then let the nth digit of this Diagonal number be 0. We still end up with a new real number, don’t we? – since it is still different to every actual real number in the list.
This may appear quite convincing at first glance. But in such a glance we are making a Platonist assumption that every List(n) is referring to some ‘actual’ real number that ‘exists’ independently of List(n). But in the logical argument we are proceeding only by logical steps, and without making any such unfounded assumptions. Instead, we need to consider what, for example, is List(1)? What is List(6753)? What is List(1012581)?
Well, List(1), List(6753) and List(1012581) are all only convenient names for actual but different symbol combinations of the language H. So, for example, List(1012581) is just a convenient name for the expression of language H that is obtained when we replace the free variable n of the expression that is List by the natural number 1012581. That new expression is a symbol combination of language H.
Now, according to the rules and grammar of language H, the symbol combination of language H that is given the name List(1012581) is a definition, in that language H, that defines some unique symbol combination of language L. (Footnote: Note that this representation applies only within the language H, not within the language L.)
The important point here is that when we talk about the ‘nth digit of List(n) in binary notation’, we are not actually referring to the nth digit of this unique symbol combination of language H, nor are we referring to the nth digit of the actual symbol combination of language L that List(n) refers to. So what are we actually referring to when we refer to the nth digit of List(n) in binary notation? Clearly, the intention is that we should be referring to an expression in binary format, for example 0.1110111000001.
Now, List(1012581) might refer to a symbol combination of language L that represents an irrational number, and that means it cannot be an expression that is simply a finite sequence of digits – since an irrational number cannot be expressed in that way. So it has to be defined in some other way. (Footnote: Of course an irrational can be defined in terms of other irrationals, but ultimately there is a baseline where each irrational is defined in terms of rational numbers.)
In that case, we still haven’t got a definition that gives the “nth digit of List(n) in binary notation”, since it does not necessarily refer to the nth digit of that particular symbol combination of the language L.
Clearly, whatever way we might be trying to define the Diagonal number, we aren’t actually defining the Diagonal number in terms of the nth digit of that particular symbol combination of language L. No, we are trying to define it in terms of the nth digit of the value of that particular symbol combination in binary notation, where the value is the value according to the syntax of language L ). Given any language, the mathematical value of an expression in that language simply is that expression. (Footnote: If the expression is a valid mathematical expression in the language and has a numerical value.)
For example, in our standard mathematical language, 1.34656, 36⁄59 + 375, and √ 67 are all expressions which are actual values, in that mathematical language. But it is important to realize that, of themselves, without any information as to which language they belong to, they have no mathematical value at all.
It can be very difficult to shake off the normal assumption that every mathematical expression is intended to be an expression of our standard mathematical language. But what, for example, might an alien visitor make of such expressions on his first acquaintance? To him they would just be meaningless squiggles; in the language of the alien visitor, those expressions have no mathematical value whatsoever - neither as a rational nor as an irrational number.
In precisely the same way, symbol combinations of language L are, as seen by the syntax of language H, simply combinations of symbols, and which have no innate numerical value in the language H. But in order to define the Diagonal number, the Diagonal proof requires that we must be able to give a numerical value in the language H for every expression of List(n) for every possible n. To do so would mean that we need to translate every expression of List(n) to an expression in language H that gives the correct numerical value in the language H. That is, we need a make a correspondence of every expression of List(n) to some expression in language H that is a numerical value in the language H, and which is the same numerical value as the value of List(n) according to the syntax of the language L. In other words, we now require a translation function in language H that can match up every instance of List(n) to:
‘the numerical value in the syntax of the language H of the numerical value of the symbol combination of the language L (according to the syntax of language L) that is represented by List(n)’.
Yes, this is starting to get rather convoluted, but if we are to give a proper logical analysis of the Diagonal proof and the associated secondary argument we cannot simply ignore inconvenient details, however intricate they may be. If an analysis turns out to be complicated, we have to follow through on the details, rather than simply ignore them.
Assuming that there is such a function as referred to above, we will call this hypothetical function Translate[x], where x is some expression given by List(n).
It might now appear that the Diagonal number can now finally be defined in terms of the nth digit of Translate[List(n)]. But that assumes that there can always be a valid definition of a function Translate for any such language H, and which does precisely what it is required to do, as indicated above.
However, it can be proved that this is impossible, as follows:
A Hypothetical Translate Function
First, assume that there is an expression of the language H that is the function Translate[x]. Such an expression can only have a finite quantity of non-digit symbols. Similarly the function List(n) is an expression of the language H that can only have a finite quantity of non-digit symbols. So when the variable x is substituted by some valid value, for example, List(1012581), since List(1012581) can only have a finite quantity of non-digit symbols, the resultant expression is also an expression that has only a fixed finite quantity of non-digit symbols. And this applies for Translate[List(n)] for any substituted value of n.
We now have a contradiction.
Irrational numbers are defined by expressions that include non-digit symbols; for any given language, there is no limit to the quantity of non-digit symbols that there might be required to define an irrational number. Hence the assumption that there can be a valid Translate function is logically invalid and it is impossible for the language H to define a diagonal number from the function List(n). (Footnote: It might also be noted that would be straightforward to define a Translate_2 function in a language that is a meta-language to both the language H and the language L; we might call this language HH. However, this does not solve the problem; it simply moves the definition of the Diagonal number up another level, from the language H to the language HH. We now have the situation where the symbol combinations of both the language L and the language H would be, according to the syntax of the language HH, simply combinations of symbols which have no innate numerical value in the language HH. But since the Diagonal number has to be defined in terms of Translate_2[List(n)], we are no further forward than before.) (Footnote: If a Platonist might try to rescue the situation by claiming that a hypothetical function Translate[x] (as discussed above) might ‘exist’, and which would match up every item in List to an actual existing ‘value’ (or to a calculated value), and that it is a function that ‘exists’ in some Platonist ‘reality’, even if there might not be any actual representation of that function in any valid logical language. That would be richly ironic indeed, for the Platonist would then be assuming that a certain function ‘exists’ which enables a correspondence of natural numbers and real numbers – in order to rescue the ‘proof’ that a function that gives a one-to-one correspondence of natural numbers to real numbers cannot ‘exist’ ! )
Failures of intuition
When faced with the impossibility of the existence of a Translate[x] and the existence of an enumeration of real numbers for which no diagonal exists, some people, instead of accepting the logical analysis, are so wedded to their intuitive assumptions that they postulate various hypothetical suggestions to try to evade the logical conclusion. But it must be stressed that the onus on anyone making such a suggestion is to provide a rigorous logical proof rather than a vague suggestion (and at the same time prove there is an error in the above analysis).
We can see now that the secondary argument of the Diagonal proof, which is commonly referred to as a simple and trivial proof, is in fact a proof that hides a mass of subtle assumptions behind a facade of simplicity. When divested of its assumptions, the secondary argument fails to define the Diagonal number, and it fails to give the commonly accepted result.
It may appear counter-intuitive that the Diagonal proof fails to provide a logical definition of the Diagonal number for our function List(n). But the history of mathematics teaches us that we should never ignore logic in favor of intuition.
Perhaps the reason that the assumption that the language H can define a diagonal number is so readily accepted is because people intuitively consider whether the language H can decipher and evaluate a finite number of expressions of L. This can be done, but it is not relevant to the case where a general method is required over infinite quantities. In that case the meta-language H, to define the expression that is the List(n) must have a variable whose domain is the symbols of the sub-language L, and a variable whose domain is symbol sequences of the sub-language L. In that case all variables of L are objects in H and cannot be variables in H. For a finite quantity of expressions, no List(n) function is required and so these two variables are not required. In the finite case a finite number of variables of L can also be variables of H.
For that case we could process a finite part of some list of real numbers, and we could produce some rational number from part of that list (and which is in the list). But that isn’t producing the desired irrational Diagonal number from every one of the numbers in a limitlessly long list – you simply can’t do this with a limitless quantity of such expressions.
For further details, there is a detailed analysis of enumerations within and outside a given language system at Non-Diagonal Proofs: Enumerations in different language systems.
It is no coincidence that almost all mathematical paradoxes involve infinity. And it seems to be the case that the most subtle errors of intuition occur when both infinity and levels of language are involved, where the apparently obvious turns out to be an erroneous case of assuming that a finite number of cases implies the infinite case. It is probably also not coincidental that the error in the assumptions behind different sizes of infinity, and the assumption in Gödel’s proof of incompleteness, both involve the assumption that a finite number of cases implies the infinite case.
Many years of Platonist mathematicians disseminating Platonist beliefs rather than strict logic has led people to eschew the idea of actually providing valid logical definitions, and instead rely on intuitive notions about limitless amounts of information. For more on Platonism see Platonism, The Myths of Platonism, Platonism’s Logical Blunder, Numbers, chairs and unicorns and the posts Moderate Platonism and Descartes’ Platonism.
For more on the notion that there can be sets that have limitlessly many elements that have fewer elements than other sets with limitlessly many elements, see also Proof of more Real numbers than Natural numbers 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.