Non-Diagonal Proofs:
Enumerations in different language systems

Page last updated 14 Feb 2023

Cantor’s Diagonal proof is a very well-known proof which demonstrates that there is no enumeration (see one-to-one correspondence) of real numbers within a well-defined mathematical system. On this page we show that there is another very different method of proving that, given a well-defined mathematical system S, there cannot be an enumeration function within that system S, and which enumerates all real numbers within that system S, as follows:

Enumerations within the system

First we assume that there can be an enumeration function f (n) within the system S, which has one free variable n (the enumeration variable) and which enumerates every real number of S. A definition of the function consists of symbols that can be divided into two groups:

• symbols for numbers (which we will call digit symbols, for example 0,1,2,3,4,5,6,7,8,9)
  and
• other symbols (non-digit symbols).

The total information content of an expression thus depends on these two types of symbols. The digit symbols contain object information - information about the objects of the system, in this case numbers. The non-digit symbols contain syntactical information, which deals with information regarding relationships between the objects of the expression.

Now, according to the definition of f (n), whenever the enumeration variable n of f (n) is substituted by some specific number (which consists only of digit symbols), the resultant expression must always have the same finite quantity of non-digit symbols, regardless of whatever number is substituted (since only digit symbols are added). In addition the relative positions of the non-digit symbols are unchanged and hence the syntax of the resultant expression is always identical, regardless of whatever number is substituted. The only difference between any two such resultant expressions is the digit symbols.

This means that the assumption of the existence of the enumeration function f (n) also entails the assumption that every real number of S can be expressed by a finite quantity of non-digit symbols in a fixed order, which implies that there is a finite limit on the amount of syntactical information required to define any real number. This, of course is absurd, hence the purported function f (n) cannot possibly reference nor enumerate all real numbers.

Enumerations outside of the system

That leaves the question of an enumeration function that is defined outside of the system S. Clearly, a dictionary style lexicographical enumeration function L(n) can be defined simply by creating a dictionary style list of all sequences of the symbols of the alphabet of the system S. (Footnote: All permutations of the symbols of any given alphabet can be put in a dictionary style list, by first deciding an alphabetical order of the symbols. The first part of the list will be that list of single symbols, then continue by taking all permutations of two symbols in an alphabetical order, then all permutations of three symbols in alphabetical order, and so on. Note that there is no limit on how many times a symbol may be repeated in a sequence. The overall list may be called a lexicographical order.)

We can observe that any such lexicographical enumeration function L(n) requires at least 2 variables that cannot belong to the system S; one is a variable whose domain is all symbols of the given alphabet, and the other is a variable whose domain is all sequences of symbols of that alphabet. Neither of these variables can be a symbol or a sequence of symbols of the alphabet of the system S, since then such symbols/sequences of symbols would be at the same time both variables and non-variables, which is logically absurd. (Footnote: They must be non-variables since they must be members of the domain of a variable. Note that replacing a variable by another variable is not substitution of the variable by a member of its domain, that is simply a change of variable.) This means that the system S cannot reference that lexicographical enumeration function L(n), hence no contradiction arises, even though the function L(n) can be considered to be an enumeration function - but it is an enumeration function outside of the system S. As such, a lexicographical enumeration function such as L(n) is not available to be used in proofs within the system S.

Information content is language dependent

This is why all references to enumeration functions in general should make it abundantly clear as to whether the enumeration function being talked about is within the system or outside of the system. The failure to do so explains many of the conundrums, contradictions and paradoxes that are prevalent in current mathematics.

Note that the matter of the quantity of non-digit symbols is not relevant when the enumeration function is defined outside of the system S. The function L(n) is an expression in the syntax of the meta-language, not of the system S. And a meta-language to S, as well as referencing the symbols of the system S (only as objects, never as variables), has its own symbols, and which can be configured as a function L(n), and which is an instruction for the creation of sequences of symbols of S.

The crucial point is that sequences of symbols, of themselves, have no specific information content - any information content that can be extracted from a sequence of symbols can only be done by reference to the rules and grammar of a specific system. Indeed, the same sequence of symbols can have a particular information content within one language system, and a completely different information content within a different language system.

Outside of the system S, the information required to define the lexicographical sequences of signals of S is finite, since the object information is simply the finite set of symbols of the system S, while the same syntactical information applies for the definition of the entire lexicographical enumeration, and hence also for each individual instance. No information is required other than the order in which the symbols occur in the sequence, and there is no correlation whatsoever of that information within the meta-language to the information content of these sequences as seen within the system S, where the syntactical information content of the sequences depends completely on the axioms and rules of inference of that system S.

Enumerations of other entities

While the above paragraphs refer to enumerations of real numbers, the same principles are directly applicable to certain other infinite sets of entities of a given mathematical system, an example for the case of recursive functions can be seen at Errors in incompleteness proofs by Kleene and Rogers.