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.

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

A Step by Step Guide to Gödel’s Incompleteness Proof:
8: Gödel’s Proposition V


 

 


 

Note that (provided you have JavaScript enabled) clicking on (hideshow) will reveal further details, while clicking again will hide it. Also, clicking on (hideshow Gödel’s) will reveal relevant parts of Gödel’s text (shown in green), while clicking again will hide it. Please note that older browsers may not display some symbols correctly.

 

(like this)

 

(like this)

 

This guide is intended to assist in attaining a full understanding of Gödel’s proof. If there is any difficulty in following any part of the proof, please contact me and I will try to help. And if you have any suggestions as to how this guide might be improved, please contact me. This guide is intended to be read alongside the English translation of Gödel’s original proof which can be viewed online at English translation of Gödel’s original proof or as a PDF file at English translation of Gödel’s original proof, PDF file.

 

Gödel’s Proposition V

 

This is a proposition about primitive recursive relations that can have any number of free variables. The formulation of the proposition as Gödel presented it is given below. For our purposes It is easier to follow the argument if we first consider the proposition as applied to a relation with only one free variable. One can then extend the argument to relations with any number of free variables. The proposition for relations with only one free variable is:

 

For every primitive recursive relation R with one free variable x there corresponds a number r and a number u such that for all x, either

 

The proposition asserts that, without having to consider any ‘meaning’ of the formulas of the system P, we may assert the following:

  1. for every primitive recursive relation R(x) there is a corresponding Gödel number r, and
  2. if the relation R(x) holds for some value of x, then the relation Bew{Sb[r u | Z(x)]} holds, and
  3. if the relation ~R(x) holds for some value of x, then the relation Bew{Neg Sb[r u | Z(x)]} holds

Unfortunately, Gödel declined to actually furnish a proof of the proposition, giving only an outline proof and claiming that it “offers no difficulties of principle”. From the outline that Gödel sketched the arguments that support the three main assertions above are as follows:

 

Assertion (I): The argument supporting the assertion (I) is as follows:

 

A primitive recursive number-theoretic relation may be defined in terms of one or more previously defined primitive recursive number-theoretic relations or functions until the simplest such relations and functions are obtained. Such relations/functions are simple expressions that can be expressed using

  1. the symbols 0, f , ∨, , ~, (, ), and/or
  2. the symbols =, , <, >, , , ε, +, /, , &, , , [, ], {, }, ~, and/or
  3. exponentiation (raising to the power of, e.g., xy), and/or
  4. various symbols for variables.

The symbols of (a) are the symbols of the formal system P.

It can be shown that expressions using the symbols of (b) can be formulated using the basic symbols (a) of the system P. Similarly, exponentiation (c) can also be formulated using the basic symbols (a) of the system P.

 

The variables used can be replaced by symbols for variables in the formal system P. From the above, given any primitive recursive number-theoretic relation, it can be seen that it can be formulated using the symbols of that formal system P. This is a purely mechanical procedure, since it only requires that a set of rules for such formulation is followed, and no meaning is required to be given to the symbols.

 

That means that, given any primitive recursive number-theoretic relation with one free variable R(x), a corresponding formula F(x1) of the system P with one free variable can be formulated from that relation. In Gödel’s terminology, this formula is a 1-place relation-sign (also called a class-sign).

 

The Gödel numbering function φ can then be applied to that formula F(x1), which will give a number r that corresponds to the relation R(x) (the Gödel number of the formula, i.e., r = φ[F(x1)]). Gödel calls this number a 1-place relation-sign or a class-sign (note the distinction between the word in plain text and in italics).

 

Assertions (II) and (III). The argument supporting these assertions is as follows:

If the relation R(x) holds for some value of x, then, since the relation is primitive recursive, then it is possible to calculate, according to the axioms of the system P whether the relation holds or not, and so there will be a proof-schema in the system P that proves the formula that results from the substitution of the variable x1 in F(x1) by that value of x.

 

If F′ is the formula obtained when the free variable u of the formula F is substituted by the value x, i.e., F′ = Subst F(x1/x) then Sb[r u | Z(x)] is the Gödel number of that formula F′, i.e., φ[F′].

 

And since the relation Bew corresponds to the notion of “Provable in the system P”, then Bew{Sb[r u | Z(x)]} corresponds to the fact that the formula F′ is provable in the system P. Similarly Bew{Neg Sb[r u | Z(x)]} corresponds to the fact that the negation of the formula F′ is provable in the system P.

 

So, at first sight it appears that Gödel’s Proposition V is proved. But this result is a lesson in how the apparently obvious can conceal the not so obvious.

 

 

However…

The argument crucially depends on the assumption that the primitive recursive function Z(x) is equal/equivalent to the Gödel numbering function φ(x), that is, the argument depends on the assertion that:

 

Z(x) = φ(x)

 

or, in other words:

“For every value of the domain of x, the value of the primitive recursive number-theoretic function Z(x) is identical to the value of the meta-language function φ(x).”

 

But, as noted previously for the Z function, on the left-hand side the variable x has the domain of natural numbers in any valid format of whatever number system is being used for number-theoretic relations, whereas on the right-hand side the variable x has the domain of symbol strings of the formal system. On the left-hand side of the equation, we can have, for example, for the value of x, 8 or ffffffff0 or 3 + 5 or 64 ÷ 23 or 9 - 1, etc, whereas on the right-hand side, we can only have φ(ffffffff0).So, for example:

 

Z(8) = φ(ffffffff0), but

Z(ffffffff0) ≠ φ(8)

 

and

 

Z(8) = Z(3 + 5) = Z(64 ÷ 23) = Z(9-1) = Z(ffffffff0) = φ(ffffffff0), but

Z(ffffffff0) = Z(9-1) = Z(64 ÷ 23) = Z(3 + 5) = Z(8) ≠ φ(8).

 

In fact the expression φ(8) is not a valid expression at all,since 8 is not a value of the domain of φ.

 

And while the value ~fff0 is a perfectly valid value of the domain of x for the function φ, and gives a valid expression of the meta-language as φ(~fff0), the same value of x is not a value of the domain of x for the number-theoretic function Z, and Z(~fff0) is not a valid number-theoretic expression. i.e.:

 

Z(~fff0) ≠ φ(~fff0).

 

The only way to avoid this contradiction is to assert that the domain of the x on both sides be defined as being restricted to symbols strings of the form 0, f0, ff0, ff0, … . But while that might superficially appear to be a fix, this ad hoc restriction of the domains should be setting off alarm bells, and warning us that we should be analyzing what is going on in a very careful manner. The entire proof is purportedly a proof that is stated in a meta-language where the statements of the meta-language are statements about a sub-language (Footnote: Note that a sub-language may also be referred to as an object-language.) and for this reason we need to be very careful that the distinctions between different levels of language are always maintained. But, amazingly, at this point, many logicians proceed by completely ignoring this crucial detail.

 

Consider the first part of Gödel’s proposition, “For every primitive recursive relation R”. Here R is a variable of the meta-language and which has the domain of number-theoretic primitive recursive relations - which means that every member of that domain is an object in the meta-language. And that means that number-theoretic primitive recursive relations are objects of the meta-language - in precisely the same way as formulas of the formal system P are objects in the meta-language.

 

And in the same way that variables of the formal system P are simply objects in the meta-language, the variables of primitive recursive relations are necessarily also objects of the meta-language, and they cannot be variables of the meta-language.

 

Otherwise we would have a nonsensical situation where variables of a sub-language would be at the same time variables of the meta-language. This is nonsensical because it is contradictory. Any variable of a sub-language can always be a member of the domain of a variable of the meta-language - since the meta-language can always refer to entities of the sub-language either in specific or in general terms. So that if a variable of the sub-language could be at the same time a variable of the meta-language, it would at the same time be both a variable of the meta-language and a specific object of the meta-language, i.e., not a variable of the meta-language - and that is a contradiction. This is covered in more detail in the paper on Gödel’s proof.

 

Bearing this in mind, if we now look again at Gödel’s Proposition V, we see that Gödel assumes on the one hand that x is a variable of the meta-language, but on the other hand, by referring to primitive recursive relations as objects of the meta-language, and by referring to variables of primitive recursive relations as objects of the meta-language, he defines x as a variable of a sub-language of number-theoretic relations, and so it cannot be a variable of the meta-language.

 

Of course, there are many cases where statements that are ostensibly similar to Gödel’s Proposition are used in mathematics and no problems arise - but that is because in the vast majority of such cases the sub-language (usually number-theoretic relations) is the only matter under consideration and there is no introduction of the meta-language into the sub-language, and no confusion of meta-language and sub-language. But simply because a method does not give rise to logical anomalies in some situations, one cannot extrapolate from that to assume that the method can never give rise to logical anomalies. It is a universally accepted principle of mathematics that one can never assume the general case from a finite number of instances; one must prove the general case by other means.

 

And in the case of Gödel’s Proposition V, the confusion of meta-language and sub-language does become of overriding importance, since the prior assumption of the equality/equivalence of the primitive recursive function Z(x) and the Gödel numbering function φ(x) is logically impossible in conjunction with Gödel’s Proposition V. This is so since the Gödel numbering function φ(x) is a function of the meta-language, whereas the primitive recursive function Z(x) is necessarily a function of the sub-language of primitive recursive relations - from the statement of Proposition V it must be in a sub-language. The quantifier that is applied to primitive recursive relations by that proposition means that primitive recursive relations and the variables of primitive recursive relations are simply objects in the meta-language. This means that in the context of Proposition V, an assertion such as:

 

Z(x) = φ(x)

 

is logically absurd, since the x on the left-hand side must be an object of the meta-language and not a variable of the meta-language, whereas the x on the right-hand side must be a variable of the meta-language.

 

Why logicians studiously look the other way and turn a blind eye to this anomaly, which is patently obvious once it is pointed out, is a mystery.

 

When correctly analyzed, Gödel’s Proposition V is seen to be a confusion of meta-language and sub-language, and that it is only by use of this confusion that the proof can appear to proceed. For this reason no further analysis of the remainder of Gödel’s proof will be given here, as such further analysis is utterly pointless when it is seen that the proof contains a fundamental flaw in Proposition V. For a more detailed analysis, see the paper on Gödel’s proof.

 

 

Footnotes:

 

 

 

Gödel’s statement of Proposition V

Return to text

The following proposition is an exact expression of a fact which can be vaguely formulated in this way: every recursive relation is definable in the system P (interpreted as to content), regardless of what interpretation is given to the formulae of P:

 

Proposition V

To every recursive relation R(x1 … xn) there corresponds an n-place relation-sign r (with the free variables u1,u2, …un)38 such that for every n-tuple of numbers (x1 … xn) the following hold:

 

R(x1 … xn)   ⇒ Bew{Sb[r (u1 … un) |(Z(x1) … Z(xn)]}  (3)

~R(x1 … xn) ⇒ Bew{Neg Sb[r (u1 … un) |(Z(x1) … Z(xn)]} (4)

 

We content ourselves here with indicating the proof of this proposition in outline, since it offers no difficulties of principle and is somewhat involved39. We prove the proposition for all relations R(x1 … xn) of the form: x1 = φ(x2 … xn)40 (where φ is a recursive function) and apply mathematical induction on the degree of φ. For functions of the first degree (i.e. constants and the function x+1) the proposition is trivial. Let φ then be of degree m. It derives from functions of lower degree φ1 … φk by the operations of substitution or recursive definition. Since, by the inductive assumption, everything is already proved for φ1 … φk, there exist corresponding relation-signs r1 … rk such that (3) and (4) hold. The processes of definition whereby φ is derived from φ1 … φk (substitution and recursive definition) can all be formally mapped in the system P. If this is done, we obtain from r1 … rk a new relation-sign r41, for which we can readily prove the validity of (3) and (4) by use of the inductive assumption. A relation-sign r, assigned in this fashion to a recursive relation42 will be called recursive.

 

Gödel’s footnote 38: The variables u1 … un could be arbitrarily allotted. There is always, e.g., an r with the free variables 17, 19, 23 etc., for which (3) and (4) hold.

Gödel’s footnote 39: Proposition V naturally is based on the fact that for any recursive relation R, it is decidable, for every n-tuple of numbers, from the axioms of the system P, whether the relation R holds or not.

Gödel’s footnote 40: From this there follows immediately its validity for every recursive relation, since any such relation is equivalent to 0 = φ(x1 … xn), where φ is recursive.

Gödel’s footnote 41: In the precise development of this proof, r is naturally defined, not by the roundabout route of indicating its content, but by its purely formal constitution

Gödel’s footnote 42: Which thus, as regards content, expresses the existence of this relation.

 


 

 


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 …  

 

The Lighter Side

 

NEWS

Peter Smith’s ‘Proof’

It has come to my notice that, when asked about the demonstration of the flaw in his proof (see A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF), Smith refuses to engage in any logical discussion, and instead attempts to deflect attention away from any such discussion. If any other reader has tried to engage with Smith regarding my demonstration of the flaw, I would be interested to know what the outcome was.

 

 

There’s something about Gödel by Francesco Berto

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.

 

 

Easy Footnotes

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).

 

 

O’Connor’s “computer checked” proof

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.

 

 

New page on Chaitin’s Constant

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.

 

Previous Blog Posts  

 

16th Mar 2015 Bishops Dancing with Pixies?

 

23rd Feb 2015 Artificial Intelligence

 

31 Mar 2015 Cranks and Crackpots

 

30 Apr 2015 The Chinese Room

 

Links  

 

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:

Gödel Links

 

– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines

 

Printer Friendly

 

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

 

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 - 2017  
www.jamesrmeyer.com