Copyright © James R Meyer 2012 - 2016 www.jamesrmeyer.com
Here we will show that it is possible to have a list of real numbers where there is no logical reason to suppose that a Diagonal number can 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. (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. Given this complete list we can easily create a new partial list that does not contain every real number of the language L, for example, by making a list containing every second item in the complete list. Furthermore, provided we have an appropriately well-defined language we can create a precise definition of such a partial list, such that the definition is a logically precise definition. This definition will be a function, with a free variable that can be substituted by any whole natural number (1, 2, 3…). This function will be able to refer to all symbols of the language L in a general manner and to all symbol combinations of the language L in a general manner. In a mathematical function, such general reference is by the use of variables.
We will call this partial 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. Any other 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. 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.
We note at this point that presentations of the Diagonal proof and the associated secondary argument make no mention of such a function, nor how one might begin to make a precise definition of such a function.
And we note at this point that in this analysis we are merely demonstrating that there can be a partial list of real numbers for which the Diagonal proof, as it stands and without invoking Platonist assumptions, fails to define a Diagonal number. Since the Diagonal proof and the associated secondary argument fail to provide any logical proof of the existence of such a function Translate[x], then the above analysis shows that there is no proof that a Diagonal number can be defined from such a list as indicated by List(n) above. It is important to note that there is no onus on this analysis to prove that there can be no such function that is the hypothetical function Translate[x]. (Footnote: As in all proofs, the onus is on the proof to prove all steps of the proof; unfounded assumptions are only admissible as assertions that are declared to be axiomatic. However, in the Appendix: A Hypothetical Translate Function, a discussion is given on the implausibility of the claim that there can be such a function.)
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 complexity behind a facade of simplicity. When divested of its Platonist 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. Looking at it objectively, we can see that there are simple reasons why it appears counter-intuitive.
One reason is that it appears counter-intuitive is that we can look at some expression of a language such as language L, and we can work out what the equivalent value is in some other language. But, and this is the all-important but, we only ever do this with a finite number of expressions, and when we do this we move in and out from one language to another. Which is all very well for a finite number of instances, but defining that for infinitely many instances is a different matter completely. So, yes, we can process part of some list of real numbers, and we can produce some rational number from part of that list. So what? That isn’t producing the desired 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 – you cannot ever produce a Diagonal number in this way. That leaves you with only one alternative, and that is to make a logical definition that can refer to every one of those expressions in the desired manner – and there is no reason to suppose that it is possible to do so.
Another reason is appears counter-intuitive is that the idea of actually providing valid logical definitions rather than relying on intuitive notions about limitless amounts of information is probably quite a novel concept to many people. This is the result of years of Platonist mathematicians disseminating Platonist beliefs rather than strict logic. The bottom line is that regardless of intuition, we have shown that the secondary argument that is commonly attached to the Diagonal argument does not stand up to logical scrutiny, and it cannot provide logical definitions for its vaguely described notions.
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’ !
This appendix gives a further analysis of the hypothetical Translate function referred to above, and is intended to be read in conjunction with the above.
The reason why such a function is very implausible is similar to the reason that we can’t have an expression in a language which is a function that lists all the irrational numbers of that language.
Recall that irrational numbers are defined by expressions that include non-digit symbols, and that for any given language, there is no inherent limit to the quantity of non-digit symbols that there might be required to define an irrational number.
If there could be an expression that is the function Translate[x], it would be an expression that has a finite quantity of non-digit symbols as well as the free variable x. And when that 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 given by Translate[List(n)] for any value of n, such as 1012581, is an expression that has only a fixed finite quantity of non-digit symbols.
To prove that it must always be possible to define a Translate function in a meta-language H one would need to prove that any such Translate function must be such that the meta-language can always define any real number that can be defined in the sub-language by an expression that has a finite quantity of non-digit symbols, in spite of the fact that in the sub-language, there is no limit to the quantity of non-digit symbols required to define that real number. And still further, one would need to prove that for every possible mathematical language, and for every possible meta-language that refers to that language, it is possible to define such a Translate function in that meta-language.
It might also be noted that would be straightforward to define a Translate 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[List(n)], we are no further forward than before.
It might be speculated that perhaps there might be some other function, rather than the Translate[List(n)] function, that could calculate the nth digit of any List(n), without actually having to find the value of that List(n). Again, there is no evidence that such a function can be defined, and again, the Diagonal proof does not make any mention of such a function, nor how one might begin to make a precise definition of such a function.
Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked (comments will be checked before appearing on this site). Difficulties in understanding the site content are usually best addressed by contacting me by e-mail. Note: you will be asked to provide an e-mail address - this will only be used to notify you of replies to your comments - it will never be used for any other purpose, will never be displayed and does not require verification. Comments are common to the entire website, so please indicate what section of the site you are commenting on.
If you cannot see any comments below, it may be that a plug-in on your browser is blocking Disqus comments from loading. Avast anti-virus in particular is known to do this, especially with Internet Explorer and Safari. See Disqus Browser plug-in/extension conflicts or Why isn’t the comment box loading?.
Please wait for comments to load …
There is a new addition to the page Yet another flawed incompleteness proof, where Berto’s proof of incompleteness in his book There’s something about Gödel comes under scrutiny.
I found that making, adding or deleting footnotes in the traditional manner proved to be a major pain. So I developed a different system for footnotes which makes inserting or changing footnotes a doddle. You can check it out at Easy Footnotes for Web Pages (Accessibility friendly).
I have now added a new section to my paper on Russell O’Connor’s claim of a computer verified incompleteness proof. This shows that the flaw in the proof arises from a reliance on definitions that include unacceptable assumptions - assumptions that are not actually checked by the computer code. See also the new page Representability.
There is now a new page on Chaitin’s Constant (Chaitin’s Omega), which demonstrates that Chaitin has failed to prove that it is actually algorithmically irreducible.
For convenience, there are now two pages on this site with links to various material relating to Gödel and the Incompleteness Theorem
– a page with general links:
– and a page relating specifically to the Gödel mind-machine debate:
All pages on this website are printer friendly, and will print the main content in a convenient format. Note that the margins are set by your browser print settings.
Comments on this site are welcome, please see the comment section.
Please note that this web site, like any other is a collection of various statements. Not all of this web site is intended to be factual. Some of it is personal opinion or interpretation.
If you prefer to ask me directly about the material on this site, please send me an e-mail with your query, and I will attempt to reply promptly.
Feedback about site design would also be appreciated so that I can improve the site.
Copyright © James R Meyer 2012 - 2016