Real Numbers and Language
Page last updated 11 Feb 2023
The Diagonal proof is a proof concerning the question as to whether there can be a list that includes all of the real numbers. This page demonstrates a simple method that is completely different to the diagonal method to prove that there cannot be a function that creates a one-to-one correspondence of natural numbers to real numbers in any given well-defined mathematical system.
First of all, we note that 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 an enumeration (list) of the rational numbers, that is that a one-to-one correspondence can be set up between natural numbers and 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, and that is what we deal with on this page.
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. (Footnote: Note that every such definition of an irrational is essentially a function with at least one free variable which has been substituted by a numerical value.)
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; in fact, for any real number value, there is no limit to the number of expressions that represent that value. Some irrationals, which are called algebraic numbers, can arise from certain types of equations, and these can have a relatively simple definition, for example, √ 57 is the square root of 57. But for transcendental real numbers, while you can give such numbers simple names (such as Pi and e), a name is not a definition, and the definition of such numbers is more complex.
The consequence is that 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.
- 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.
- 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.
- 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.
- 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.
- 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 Georg Cantor’s 1874 proof.
A more detailed analysis of enumerations within and outside a given language system can be seen at Non-Diagonal Proofs: Enumerations in different language systems.
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.