Logic and Language

Copyright   James R Meyer    2012 - 2023 https://www.jamesrmeyer.com

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

Page last updated 28 Dec 2022

Now printer friendly: this guide has now been set up for easy printing so that readers can also access the information in paper format.

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.

Gödel’s Proposition V

This is a proposition about primitive recursive relations that can have any number of free variables. 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: (Footnote: Gödel’s text as in Meltzer’s translation:
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-string 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 involved.39 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-strings 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-string r41, for which we can readily prove the validity of (3) and (4) by use of the inductive assumption. A relation-string r, assigned in this fashion to a recursive relation42 will be called recursive.
Gödel’s footnotes:
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.
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.
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.
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.
42:Which thus, as regards content, expresses the existence of this relation.
)

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

(3)
R(x) ⇒ Bew{Sb[r u/Z(x) ]}

or
(4)
¬ R(x) ⇒ Bew{Neg Sb[r u/Z(x) ]}

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-string (also called a class-string).

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-string or a class-string (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 x1 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′], where u is the number that Gödel assigns to correspond to the variable x1 of the formal system.

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.

The Z function assumption

Gödel’s Proposition V is a crucial part of his incompleteness proof, and it depends completely on his assumption that the primitive recursive function Z(x) is equal/equivalent to the Gödel numbering function φ(x) for certain values of x, that is, the argument depends on the assertion that:

Z(x) = φ(x), x a natural number

or, in other words:

“For every value of the domain of x as a natural number, 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 elsewhere 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 ffffffff 0 or 3 + 5 or 64 ÷ 23 or 9 - 1, etc, whereas on the right-hand side, we can only have φ(ffffffff 0).So, for example:

Z(8) = φ(ffffffff 0), but

Z(ffffffff 0) ≠ φ(8)

and

Z(8) = Z(3 + 5) = Z(64 ÷ 23) = Z(9 − 1) = Z(ffffffff 0) = φ(ffffffff 0), but

Z(ffffffff 0) = 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 ¬fff 0 is a perfectly valid value of the domain of x for the function φ, and gives a valid expression of the meta-language as φ(¬fff 0), the same value of x is not a value of the domain of x for the number-theoretic function Z, and Z(¬fff 0) is not a valid number-theoretic expression. i.e:

Z(¬fff 0) ≠ φ(¬fff 0).

Furthermore, a function can be a valid substitution for a free variable of a number-theoretic function. For example, if Z(x) is a standard number-theoretic function, then we may substitute the x by y + 1 to give the function Z(y + 1), which has y as its free variable. Now, Z(y + 1) has no numerical value, since it has a free variable y. But, on the other hand, if we substitute the free variable x of the Gödel numbering function φ(x) by v + f 0, where v is a free variable of the formal system, and where the formal system includes the symbol +, then the result φ(v + f 0) is a specific numerical value and it has no free variable. The variable v is only a variable of the formal system, and in the meta-language in which the Gödel numbering function φ is expressed it is an object, and hence it is not a free variable in this context. Hence again we see a clear inequality between the Z function and φ function:

Z(y + f 0) ≠ φ(y + f 0).

Similarly:

Z(ff 0 + f 0) ≠ φ(ff 0 + f 0)

since Z(ff 0 + f 0) = Z(fff 0) but φ(ff 0 + f 0) ≠ φ(fff 0) because φ(ff 0 + f 0) and φ(fff 0) evaluate as two distinct numerical values.

One way that might be attemped to try to evade these contradictions 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.

It might be thought that one can get around the problem by asserting that the Z function that is being referred to is actually the formula in the formal system that states the relationship given by the definition of the function Z(x). So if we call that formula of the formal system ZFS(n), where n is some variable of the formal system, now we can assert that the format of the values of the domain of n are all sequences of the form 0, f0, ff0, ff0, …, and that perhaps this solves the problem.

But in fact that only lands us in even deeper trouble, as we now have to assert that:

ZFS(n) = φ(n)

which obviously is an absurdity, as ZFS is in the language of the formal system (a sub-language) so its variable n cannot be a variable of the meta-language, whereas the Gödel numbering function φ(n) is a function of the meta-language, and so n must be a variable of the meta-language. Even if we ignore that, since the purported variable n must be the same on both sides of the equation, we now have the situation where the free variable of the meta-language function φ can only be in the format of variables of the formal language - which is also absurd.

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 PDF paper on Gödel’s proof, and I have added a section to the paper that gives a brief summary of the underlying illogical assumption regarding the Z function that the proof relies on, so that the reader can see in a few pages that the proof is flawed.

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.

See Gödel’s contradiction and the page Gödel’s Proposition V which shows that Gödel’s Proposition V leads to a blatant contradiction. For a more detailed analysis, see the PDF Paper on Gödel’s proof.

See also Gödel’s 1934 Undecidability lectures which actually give a simpler demonstration of the inherent conflation of language in such proofs. This is rather ironic since by then Gödel had three years to reflect on his methods of proof.

Footnotes:

Interested in supporting this site?

You can help by sharing the site with others. You can also donate at where there are full details.

As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:
Comments with excessive number of different points.
Questions about matters that do not relate to the page they post on. Such posts are not comments.
Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.

Reasons for deleting comments of certain users:
Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous user names for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it incorrectly and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.
Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.

Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.

Based on HashOver Comment System by Jacob Barkdull

Copyright   James R Meyer   2012 - 2023
https://www.jamesrmeyer.com