Logic and Language

Logic and Language

Copyright © James R Meyer 2012 - 2016 www.jamesrmeyer.com

This page is keyboard accessible:

• Use**Tab**, **Shift + Tab **keys to traverse the main menu. To enter a sub-menu use the **Right Arrow** key. To leave a sub-menu use the **Left Arrow** or the **Escape** key.

• The**Enter** or the **Space** key opens the active menu item.

• To skip the menu and move to the main content, press**Tab** after the page loads to reveal a skip button.

• To get back to the top of the page anytime, press the**Home** key.

• For more information, click here: Accessibility Close this tip.

• Use

• The

• To skip the menu and move to the main content, press

• To get back to the top of the page anytime, press the

• For more information, click here: Accessibility Close this tip.

Note: Full functionality of this web page requires JavaScript to be enabled in your browser.

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

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

*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

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

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[

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:

- Natural numbers in the format of the formal system (e.g., symbol strings of the format
**0**,**f****0**,**ff****0**,**fff****0, …**) may be substituted for a variable in such an expression of the formal system.

And depending on the rules of the particular system, it is also the case that: - A valid expression of the system can also be produced by replacing a variable
*x*in the expression by a different variable*y*of the system, providing certain conditions are observed (such as the new variable name not conflicting with variables already in the expression). This is basically just a name change. - A valid expression of the formal system can also be produced by replacing a variable
*x*in an existing expressionof the system by another existing expression**A**of the system, providing certain conditions are observed (such as there may not be variables in the substituted expression**B**that conflict with variables already in the expression**B**). For example, if the free variable of a number-theoretic expression is substituted by a number-theoretic function, the resultant expression is also a number-theoretic expression.**A**

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

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

See also Some preliminary observations and The most common errors in incompleteness proofs on the page Errors in Incompleteness Proofs which also deal with the notion of erroneous substitution.

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,

*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

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

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

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:

- the relation can be expressed in the formal system, because the formal system can express number-theoretic relations, and
- since the relation is primitive recursive, then that means that there is always a finite means of determining whether the relation applies or does not apply for any specific values that are substituted for its free variables.

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.

Footnotes:

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.

Flawed proofs of the Diagonal Lemma by Panu Raatikainen and Vann McGee have been added to the Diagonal Lemma web page.

16th Mar 2015 Bishops Dancing with Pixies?

23rd Feb 2015 Artificial Intelligence

31 Mar 2015 Cranks and Crackpots

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.

Note: for some browsers JavaScript must be enabled for this to operate correctly.

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

www.jamesrmeyer.com