Copyright © James R Meyer 2012 - 2016 www.jamesrmeyer.com
Representability is a notion employed by many incompleteness proofs. Informally, we can say that the notion is that, given a formal system, and an expression A that is not an expression of that system, then provided certain conditions are satisfied, there is an expression B of the formal system that represents the “meaning” of the original non-system expression A. In effect, the assumption of representability is the assumption that there exists an algorithm (Footnote: Such an algorithm would be in a meta-language; there would be two sub-languages, one for the expression A and one for the expression B.) that can precisely translate the expressions of one mathematical language to expressions of another mathematical language.
In any incompleteness proof that I have seen that uses the notion of representability, no actual proof of this representability is presented, it is simply assumed to be correct. Why such an assumption is considered acceptable in proofs that should rely only on accepted axioms is a mystery. This is particularly so in the case of proofs that are claimed to be entirely proved by computer but are in fact reliant on the assumption of representability. In such proofs you will never see an algorithm that will translate from one mathematical language to another mathematical language - which is what the assumption of representability assumes. It is not surprising that you will never encounter such an algorithm, since all such incompleteness proofs rely on the use of a Gödel numbering function, and it can be proved that there can be no algorithm that can precisely translate an expression that includes the Gödel numbering function to an expression in a purely number-theoretic language. See The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System (PDF) for an exposition of this proof.
Gödel, in the first ever published incompleteness proof, ushered in the philosophy that when writing an incompleteness proof, one can simply throw in an unproven assumption along the way, rather than actually proving it. The result of his proof relies completely on his Proposition V, which is a proposition that makes numerous assumptions - including the assumption of representability. The result is an crucial confusion of the different levels of language involved in the proof (this confusion is proved in the paper The Fundamental Flaw in Gödel’s Proof of his Incompleteness Theorem).
The notion of representability is dealt with in more detail below; first we will deal with the substitution of a variable by a value that is defined to not belong to the variable’s domain.
In many incompleteness proofs, there is an assumption that one can always substitute a variable that has a given domain by a function provided its range of values are the same as the domain of the variable. But this assumption can conceal essential details.
Consider this expression of a purely number-theoretic language system:
n + 2 > 0
Now, given a function GN(s), whose range is natural numbers, and where s is a variable whose domain is a given set of symbol strings that are not numbers, suppose that we now substitute the n by GN(s) to give the expression: (Footnote: Since GN(s) is any function whose domain is symbol strings and whose range is natural numbers, it can be a Gödel numbering function.)
GN(s) + 2 > 0
This is a common mathematical operation, but what is actually being done is that this is being used a convenient shortcut to the more formal expression:
For all s as symbol strings, there exists a natural number n, such that n = GN(s), and n + 2 > 0.
The crucial point here is that this is an expression where its overall language is not confined to objects that are only natural numbers (i.e., it is not a number-theoretic expression), but within this overall expression n + 2 > 0 has not changed, and it remains a purely number-theoretic expression. Hence the convenient shortcut that is:
GN(s) + 2 > 0
is actually an expression that makes an illegal substitution of a variable of a purely number-theoretic expression. This is so since GN(s) is not itself a natural number, and it does not satisfy the definition of the domain of the variable s . And there is no reason to assume that simply because n + 2 > 0 has a particular property that GN(s) + 2 > 0 will also have that property.
As noted, such a substitution is an extremely common mathematical operation. But the fact that the convenient shortcut usually works without any ensuing problem does not mean that certain properties of the expression n + 2 > 0, in particular that it is a number-theoretic expression, and that n has the domain of natural numbers, can always be ignored. The convenient shortcut usually works without any problem simply because in most cases the substitution does not conceal any crucial detail. In cases that involve only numbers, the function that is being substituted is a function which itself is a number-theoretic function whose objects are natural numbers, and whose variables have the domain of natural numbers. As an example, if we use the same purely number-theoretic expression as was used above:
n + 2 > 0
and given a purely number-theoretic function f(x), where x is a variable whose domain is natural numbers, and we now substitute the n by f(x)to give the expression:
f(x) + 2 > 0
Again, this is a convenient shortcut to the more formal expression:
For all x, there exists n, such that n = f(x), and n + 2 > 0.
But here, in stark contrast to the previous case, the overall expression remains as a purely number-theoretic expression. Hence in this case, the convenient shortcut conceals no important details. And in this case, we do not need to specify the domains of n and x since every variable in the language is already specified as having the domain of natural numbers.
For more details on the substitution of variables by values outside their domain, see the addendum in the paper An Error in a Computer Verified Proof of Incompleteness by Russell O’Connor (PDF).
The above describes composite functions that are derived from two pre-existing functions. Now, if one function has the property of being purely number-theoretic, and if the second function does not, why would anyone assume that the resultant composite function is purely number-theoretic? That is an absurd assumption, yet it is assumed in many incompleteness proofs.
As a trivial example of the fallacy involved, consider a purely number-theoretic function - the identity function:
I[x] = x
Now substitute the x by a function one then asserts in the meta-language that:
I[GN(s)] = GN(s)
where GN(s) is a function where the domain of s is symbol strings, and the range of values of the function are natural numbers.
Superficially that might appear to be a valid statement, where the purely number-theoretic property of the identity function is ignored. However, simply because for the function I[x] there are also limitlessly many purely number-theoretic expressions that, given a specific value substituted for x, give the value of I[x] - it does not follow that the composite function I[GN(s)] has any corresponding expression in purely number-theoretic terms, and which evaluates the value of GN(s) given a value s. This cannot be the case, since s and its domain cannot be expressed in a purely number-theoretic system.
But does it matter?
Yes, it does matter.
The reason why it matters is because many incompleteness proofs rely on the notion of “Representability”. Informally, the principle of “Representability”, as is commonly used in many incompleteness proofs is that, instead of generating an actual expression of the formal system, an expression is generated in another language instead, and then it is claimed by the notion of “Representability” that there is an expression in the formal system that states essentially the same thing as the original expression.
To be more specific, if the original expression expresses a certain function whose only objects are natural numbers and whose variables only have the domain of natural numbers, then there is an expression in the formal system that expresses precisely that same function - provided certain other conditions are satisfied. That is, when the free variables of the expression in the formal system are substituted, the resultant value of the expression is the same numerical value as that given by the original expression when its variables are substituted by the same numerical values.
Similarly, if the original expression expresses a certain relation between natural numbers and variables whose domain is natural numbers, then (provided certain other conditions are satisfied) there is an expression in the formal system that expresses precisely that same relation between natural numbers and variables whose domain is natural numbers. (Footnote: For more details on representability see the addendum in the paper An Error in a Computer Verified Proof of Incompleteness by Russell O’Connor (PDF).)
Clearly, if that is the case, then the inverse also applies, that is, given an expression of a number-theoretic number formal system, then there is also a number-theoretic expression that can be expressed and which uses different symbols (and more symbols) than the formal system uses. Furthermore, for both expressions, it must be the case that the objects are natural numbers, and the variables have the domain only of natural numbers.
Obviously, to be able to claim Representability, the expression of the other language must have certain properties. So what are those properties? Well, obviously, there must be some relationship between those properties and the properties of expressions of the formal system. So it is instructive to first examine the properties of expressions of the formal system.
A number-theoretic formal system consists of objects that are natural numbers, and variables whose domain is the objects of the system, i.e., natural numbers (in the format of the system). Hence expressions of the system only make statements about natural numbers, and not about any other things. So, given an expression of the formal system:
Now, given such a formal system, if there is an expression C which is not an expression of the formal system, but is an expression in another language whose objects are also natural numbers, and whose variables also have the domain of natural numbers, then (providing other certain conditions are observed) we might assert that there can be an expression D of the formal system that states the same relationship between natural numbers as that expression C. This assumption is called the “representability” of the expression in the formal system.
In such a definition of “Representability”, any included assumptions must be logically reasonable and acceptable. For that to be the case, then the expression which is to be “representable” must also conform to the three rules above.
Otherwise if, for example, we produce an expression K by substituting a variable x in an existing expression L by an expression which includes a variable whose domain is not natural numbers, then that expression K does not conform to Condition 3 above, and thus there can be no logical reason to suppose that the expression K is “representable” in the formal system.
It can be noted that many type theories operate on the substitution assumption as described above in the section Substitution and Variables. Many computer based proof systems use types and generally they also incorporate the same assumption. And as noted above, many proofs that are carried out in such systems do not require a strict delineation of number-theoretic expressions and non-number-theoretic expressions, and so they operate without any problems.
However, in proofs of incompleteness that involve the use of expressions that must be purely number-theoretic, it is crucial that the property of being number-theoretic is always strictly observed. But the substitution assumption precludes there being a strict delineation of number-theoretic expressions and non-number-theoretic expressions, unless additional code is used to enforce such strict delineation. The result is almost inevitable - there is a confusion of number-theoretic expressions and non-number-theoretic expressions, and this produces an erroneous result.
I have now added an extension to my paper An Error in a Computer Verified Proof of Incompleteness by Russell O’Connor (PDF) on a computer proof by Russell O’Connor, showing that the proof, although supposedly fully checked by computer, actually relies on untenable assumptions regarding representability that are implicit in O’Connor’s definitions in his proof. This also may make you wonder how many other implicit assumptions are included in other claims of fully computer checked proofs. See also the page computer-checked proofs.
One person suggested a counter-argument to the above, and claimed that O’Connor’s proof was correct because the proof was based on a theory of types; his argument was as follows:
Using the type term “nat” for natural numbers, if natural numbers, variables whose domain is natural numbers, and functions whose range are natural numbers are all assigned the type “nat” then one can substitute a type “nat” variable by a type “nat” function.
The person asserted to me that, although the expression n + 2 > 0 is defined as a purely number-theoretic expression, it is perfectly valid to say that the variable n can be substituted by an expression such as GN(s), where s is a variable whose domain is a given set of symbol strings that are not numbers. The reason he gave was that to me that GN(s) is of type “nat”, and since n is defined in the proof as type “nat”, the substitution is correct. He also said that there are computer codes that checks that all substitution is made according to the type rules and therefore, he claimed, there could not be any substitution error.
But the reality is that, in fact, GN(s) itself isn’t a natural number. This is obvious, since it has no numerical value. If GN(s) itself had a numerical value, then that would mean that there is some symbol string, let’s call it abc, such that GN(s) = GN(abc). Now, GN(s) is any arbitrary function, so that means if it is a bijection (i.e., gives a one-to-one correspondence) that must mean that the variable s is equal to the symbol string abc, which means that they are interchangeable. But that is absurd, since s is a variable, and abc is not a variable
The above simply demonstrates that the type “nat” that is so defined does not actually represent precisely the same concept as natural number. A natural number is an entity for which the Peano axioms (Footnote: The Peano axioms were formulated by the Italian mathematician Giuseppe Peano. They constitute a formal definition of the fundamental properties of natural numbers. See for example, The Peano Axioms at Wolfram.) apply, but GN(s) itself isn’t a natural number. And a purely number-theoretic expression is an expression in which the objects of the language are natural numbers for which the Peano axioms apply.
Applying an alternative definition such as type “nat” does not change pre-existing fundamental mathematical definitions pertaining to natural numbers. A variable whose domain is natural numbers is defined as substitutable by a natural number. That is a fact that isn’t going to ever change, regardless of any playing around with alternative terminologies.
When both natural numbers and functions whose range is natural numbers are simply lumped together under a single type term “nat”, all that does is to paper over the fact that there actually is a difference between a natural number and a function whose range is natural numbers.
When I pointed this out to the person mentioned above, he changed tack, and then said that, provided the function GN(s) evaluates as a natural number, then the substitution is valid and the computer code checking is correct.
But again, I had to point out that GN(s) does not evaluate as a natural number. And then the person changed tack again, and replied that what he actually meant was that when a valid value is substituted for the variable s that there is an evaluation. So what he was in fact saying was:
For all s, GN(s) is a valid substitution for the variable n in n + 2 > 0.
which means that he is claiming that, for example, GN(abc) is a valid substitution for the variable n in n + 2 > 0, which gives GN(abc) + 2 > 0. Well, as was described earlier, this is simply a shortcut for the more formal statement:
For all s as symbol strings, there exists a natural number n, such that n = GN(s), and n + 2 > 0.
and this implies the particular instance for abc, which is:
For the symbol string abc, there exists a natural number n, such that n = GN(abc), and n + 2 > 0.
As in the analysis in the section Substitution and Variables above, this expression is an expression where its overall language is not confined to objects that are only natural numbers (i.e., it is not a number-theoretic expression), but within this overall expression, n + 2 > 0 has not changed, and it remains a purely number-theoretic expression. And the convenient shortcut that is:
GN(abc) + 2 > 0
is actually an expression that conceals the fact that there has been an illegal substitution of a variable in an expression that is defined as being purely number-theoretic. The fact that GN(abc) evaluates as a natural number does not of itself mean that it is a valid substitution for a purely number-theoretic variable.
And, as pointed out in my paper on O’Connor’s proof, this gives rise to a problem - O’Connor assumes that because one expression is “representable” on account of it being a purely number-theoretic expression, then an expression that has been derived by the sort of substitution indicated above is assumed to be also “representable”. This is of course absurd because the derived expression is not a number-theoretic expression.
Some people fail to discern the distinction between an expression of a formal number-theoretic system that corresponds to a relationship between non-numerical quantities, and an expression of a formal number-theoretic system that is claimed to actually state a relationship between non-numerical quantities.
The fact is that there can indeed be an expression of a formal number-theoretic system that corresponds to a certain relationship between non-numerical quantities (subject to certain conditions). But in order to generate that formal number-theoretic expression, some sort of coding function is needed that converts those non-numerical quantities into numerical quantities. And there can be such encoding systems, whereby the formal system together with the encoding system form a compound system that can make statements regarding non-numerical entities. In such a case, it is crucially important to recognize that the formal system alone does not make any statements regarding non-numerical entities. The information about the relationship between the non-numerical quantities is not contained within the expression of the formal system – it is only the combination of that expression and the inverse of the encoding function that allows one to retrieve that information.
Furthermore, since there are infinitely many encoding systems, for any given encoding system and a formula of the formal system that together make a proposition A about given entities, then there can also be another encoding system that, together with precisely the same formula of the formal system, that together make the negation of the very same proposition A. This demonstrates that one cannot simply select some formula of the formal system, and select some encoding system, and then claim that that formula itself is making a proposition about non-numerical entities, for then one could select that same formula, and a different encoding system, and then claim that that formula is making the negation of the very same proposition. That would be a straightforward contradiction.
This demonstrates that to select a formula of a formal system, and then claim that that formal system expression, by itself, is making a statement about non-numerical entities is clearly absurd. Of course, if a compound system is being used, it may be convenient to omit any mention of the encoding system, and simply use the statements of the formal system, but it must be remembered that that is only a convenience. In order to prevent any ambiguity, it must always be clear that a compound system is being used, and which includes one specific encoding function.
Of course, the Gödel numbering system is itself an encoding system that encodes strings of symbols as natural numbers. Common to all incompleteness proofs is the claim that there is are expressions of the formal system that actually are making statements about expressions of the formal system. But, as noted above, for any such statement of the formal system that is claimed to be making an assertion about expressions of the formal system, there will also be an encoding such that the very same expression of the formal system is making the negation of the claimed assertion about expressions of the formal system. This, of course, is absurd.
The origin of such absurd claims can always be traced back to the erroneous claim that an expression of the formal system can actually express a function that encodes that very formal system. But the coding function must have a variable that has the domain of the symbols of the non-numerical expressions. And it is clear that no purely number-theoretic expression has such a variable. It follows that the coding function is external to the number-theoretic formal system, and is defined in a language that is a meta-language to the formal system. It further follows that given a purely number-theoretic expression, it is impossible to derive any such coding function from the purely number-theoretic expression alone.
To claim that the formal system is referring to its own expressions by using some encoding function is rather like me claiming that I can understand Chinese - but when somebody makes a detailed inquiry, they discover that what I really meant is that I can’t actually understand Chinese, but that I can understand any Chinese expression if it has already been encoded into English – so that my claim that I can understand Chinese would be a complete travesty of the actual situation.
On the other hand, given a purely number-theoretic expression that states some relationship, one can express that relationship as an expression of the formal system without any encoding function, since all the objects are natural numbers, both in the original expression and in the formal expression. And given an expression of the formal system, one can present that information in different formats or languages without the need for an inverse of an encoding function. All you need is the knowledge of the formats of natural numbers in the two systems.
In many incompleteness proofs, the point of determining that a relation is a primitive recursive number-theoretic relation (i.e., an expression whose only objects are numbers) has two purposes:
These are two quite separate purposes. The crucial point is that for any claim that a function/relation is expressible in the formal system because the function/relation is primitive recursive necessarily entails that the function/relation must be purely number-theoretic.
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