Copyright © James R Meyer 2012 - 2016 www.jamesrmeyer.com
The Diagonal proof is a proof concerning the question as to whether there can be a list that includes all of the real numbers. The real numbers include the whole numbers, both positive and negative (such as 3, 7, -10, -16, etc), and the fractions, both positive and negative. That leaves the numbers that are neither whole numbers nor fractions; such numbers are called irrational numbers, so called because they cannot be written as a ratio, and a ratio is essentially the same as a fraction. It is known that there can be a list of the whole numbers and of the rational numbers (see Listing the rational numbers). That means that the Diagonal argument is fundamentally about whether there can be a list that includes all irrational numbers.
Although an irrational number cannot be defined as a fraction, it can nevertheless be defined in terms of fractions – but with a proviso: any such definition needs to refer to a limitless quantity of fractions. A limitless quantity of fractions cannot be written down, but you can refer to every one of a limitless quantity of fractions by using a variable and creating a definition that refers, in a general way, to every possible value of that variable.
And while you can have fairly simple definitions of irrational numbers that are defined with only a few symbols, you can also have very complex ones which use many symbols, and for which there is no equivalent simple definition. And there is no limit to the complexity of the definition of an irrational number. Of course there can be different expressions that represent the same real number value; for any real number value, there is no limit to the number of expressions that represent that value. And of course, you can give some irrational numbers simple names (such as Pi and e), and give simple standard forms for certain types of irrational numbers (such as square roots, which we write, for example, as √57).
But in any given language, there is no inherent limit to the quantity of symbols that might be required to define an irrational number value. Some of those symbols will be the digits used for natural numbers (for example, we normally use the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9); and some of the symbols will be non-digits. But, for any given language, for any given irrational number that can be defined in that language, there will always be a minimal definition in that language – that is, an expression of the language which has the least number of non-digit symbols such that the expression represents that given value . (Footnote: Note that for some irrational numbers, there could be two or more expressions that use the same minimum number of non-digit symbols.)
Obviously, if there is a definition of a real number, then it has to be in some language. And if we want our mathematics to be logically coherent, we accept that the language must not, among other things, be ambiguous. It must not rely on the vagueness that is inherent in much of natural language. Given that we have a logical language in which real numbers can be defined, a pertinent question is:
‘Can we have an expression which lists all the real numbers of a given language, where that expression is in the same language as the real numbers that it lists?’
In mathematics, expressions that define such lists are called functions. A simple example of a function that lists all the even numbers is:
2 × x,
so that when x in the expression 2 × x is substituted by 1, the function is 2 × 1, which has a value of 2, when x in the expression 2 × x is substituted by 2, the function is 2 × 2, which has a value of 4, and so on.
So, back to the question: ‘Can we have an expression in a language which is a function that lists all the irrational numbers that can be expressed in that same language?’ Well, the answer is simple:
and the proof of this is quite straightforward. As we have noted already, there is no minimum amount of non-digit symbols that are required to define a real number, and we use this fact to prove the result.
1. First, we suppose there is some expression in a given language that is a function that lists all the real numbers that can be expressed in that same language.
2. That function must have a free variable, (Footnote: Note that the same free variable may occur several times in the expression.) and when that free variable is substituted by some natural number, we are left with an expression that has a finite number of non-digit symbols. Since the function supposedly lists all real numbers, for any substitution of the free variable by some natural number, this expression will have some real number value.
3. Now, for any expression with a finite amount of non-digit symbols, there will always be some irrational number that can only be defined in that language by using more than that quantity of non-digit symbols.
4. That means it is impossible for any expression, upon substitution of its free variable, to produce an expression of the language that expresses every real number that can be expressed in that language.
5. Hence there cannot be any expression of a given language that can list every real number in that same language.
This shows that it is easily demonstrated that there cannot be any function of a language which lists every real number of that language, a result that concurs with the correct reading of the Diagonal proof or Cantor’s 1874 proof.
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