Gödel's Incompleteness Theorems

Intuitive account

Theorems and philosophical consequences

Gödel didn't just prove a theorem or two, he invented a whole new branch of mathematics with new techniques, and so what we really care about is what of philosophical interest can be shown using those techniques.

Some definitions:

• A theory is a set of sentences that is closed under logical consequence.
• A set of sentences is a set of axioms for a theory if the theory is the set of logical consequences of those axioms.
• A set (for our purposes, a set of sentences or a set of numbers) is decidable if there is an algorithmic (that is, systematic, fully specified, capable of being implemented by a computer program) method to decide whether or not any given appropriate object (that is, sentence or number) is a member of the set.
  • The notion of a decidable set is an intuitive one that rests on the informal idea of an algorithm. Since it is informal, it is not sufficiently precise to be used in stating or proving theorems. There is a formal, precisely defined, notion, recursive, which is extensionally equivalent to decidability, as I discuss below. I shall use the terms 'decidable' and 'recursive' more or less interchangeably until that point.
• A theory is axiomatizable if there is a decidable set of axioms for it. (Note that it is not enough for there to be a set of axioms for the theory—the set of axioms must be decidable.)
• A theory (which is a set of sentences) is undecidable if it is not decidable.
• A theory is essentially undecidable if it is undecidable and every consistent theory of which it is a subset is also undecidable.
• A theory is complete if it contains, for every sentence, either that sentence or its negation.

Many of the results I wish to state will be for "sufficiently strong" theories. To define sufficiently strong, we shall fix a set of axioms %$A$% and say that a theory is sufficiently strong if contains %$A$%. The weaker the set of axioms %$A$%, the more theories will be sufficiently strong, and hence the stronger our theorems will be. As a first approximation, we may take %$A$% to be Peano's axioms. Much weaker systems will work. Here are two examples:

• All closed arithmetical truths plus all sentences of the form exemplified by the following sentence:

For every %$x$%, if %$x$% is less than 7 then %$x$% is 0 or %$x$% is 1 or %$x$% is ... or %$x$% is 6.

• The Peano axioms except for induction plus a recursive definition of < analogous to the axioms recursively defining addition or multiplication.

The second set of axioms is finite.

Technical aside. I have defined a sufficiently strong theory to be one that contains a theory %$A$%. Since the theories I have proposed to use for %$A$% all include, for example, the symbols 0 and %$S$% in their language, any sufficiently strong theory must be in a language that includes those symbols. Since standard axiomatizations of set theory, for example, do not include those symbols, they will not be, in the sense in which I defined, sufficiently strong. It is intuitively obvious what to do: though the symbols are not included in the language of set theory, for example, one could give them suitable definitions, and that would be good enough: the resulting theories would be, in the precise sense I've given, sufficiently strong, and the Gödel and related theorems for the usual theories of sets will follow from those for the theories to which we have added the requisite symbols. I outline the method in some detail in DefinitionalExtensions.

We usually fasten on two specific results:

• Gödel's first incompleteness theorem, which says that any sufficiently strong consistent theory (for example, the consequences of Peano's axioms) is essentially undecidable.
• Gödel's second incompleteness theorem which says that no sufficiently strong axiomatizable theory true can be proved to be consistent, in a suitable sense, unless it is inconsistent.

What I have called Gödel's first incompleteness theorem is actually due to Gödel and Rosser. Gödel proved a somewhat weaker result.

• Philosophical remark. Gödel's second incompleteness theorem knocks down a supporting pillar of Hilbert's program: he wanted to prove his mathematical theories (especially set theory) consistent on a finitist basis, that is, using principles simpler than those of the theories, and the second incompleteness theorem shows that that cannot be done: the theories (presuming that they are, in fact, consistent) cannot even be proved consistent within themselves, let alone within a weaker theory. In drawing that conclusion, I am making two assumptions that require a bit of discussion:

1. Finitist methods are included in the theories Hilbert wanted to justify. It is not logically impossible that there are finitist methods that are not contained in the theories being proved consistent.
   • Since set theory is generally taken to encompass models of every other part of mathematics, the idea of finitist methods that are not encompassed by set theory poses a dilemma for the Hilbertian: either set theory cannot be proved consistent using finitist methods (since it encompasses all finitist methods and cannot prove itself consistent) or it is too weak (since it doesn't include finitist methods).
   • There is, so far as I can see, no comparable argument in the case of Peano arithmetic, but all the finitist methods Hilbert actually proposed, and all the methods that have subsequently been taken to be finitist, are in fact contained within Peano arithmetic. There doesn't seem to be any plausible candidate for a finitist method that is not contained in Peano arithmetic, and so there is no prospect of giving a finitary proof of the consistency of Peano arithmetic.
2. A set of axioms is consistent if there is no sentence such that one can prove both that sentence and its negation from them. The definition of consistency therefore depends on the definition of proof. The proof of Gödel's second incompleteness theorem is dependent on the precise definition of proof that it uses. Indeed, it is easy to give a (somewhat artificial, but extensionally correct) with which it is trivial to give a finitist consistency proof of the consistency of any consistent theory. Since we shall be using it below in any case (it is Rosser's contribution to what I have been calling Gödel's first incompleteness theorem) , here it is:

   A sentence is Rosser provable if there is a proof of it (in the ordinary sense) and no shorter proof (in the ordinary sense) of its negation. (Define the length of a proof so that there are only finitely many proofs of each length.)

   Unfortunately, the Rosser definition is useless for Hilbert's purposes. There is nonetheless a loophole in the use of Gödel's second incompleteness theorem to show that Hilbert's program cannot be carried out: One would have to show that there is no modified definition of proof that evades the theorem and is still adequate for Hilbert's purposes. That has not been shown. But most philosophers don't take that loophole very seriously: the constraints on a notion of proof that would serve the purpose are quite onerous, and no one has even a suggestion of how one might be able to come up with one. Those matters are discussed in detail in Detlefsen86
   
   Hintikka recently claimed that his strong system of "independence friendly logic" enables one to carry out a version of Hilbert's program. I'm not sure I believe it, but in any case the logic is so strong that that will not convince, for example, the intuitionists whom Hilbert had hoped to convince. Hintikka agrees.

Now, back to the mathematical development.

It is not hard to prove the following:

• Lemma. A complete axiomatizable theory is decidable.

Proof sketch. more... close If the theory is inconsistent, it is easy to decide whether or not a sentence is in it: every sentence is in it. So suppose from now on that the theory is consistent.

To decide if a sentence %BEGINLATEX{inline="1" color="Cornflowerblue"}% $ \phi$ %ENDLATEX% is in a complete axiomatizable theory, systematically generate all finite sequences of sentences and check whether each sequence is a proof—one can check whether a sentence is an axiom because the set of axioms is, by hypothesis (axiomatizable) decidable, and it is easy to check whether a sentence follows from previous ones by a rule of logic. When you find a proof check whether the theorem proved (that is, the last sentence of the proof) is %BEGINLATEX{inline="1" color="Cornflowerblue"}% $\phi$ %ENDLATEX% or %BEGINLATEX{inline="1" color="Cornflowerblue"}% $\lnot\phi$ %ENDLATEX%. If it is %BEGINLATEX{inline="1" color="Cornflowerblue"}% $\phi$ %ENDLATEX%, then %BEGINLATEX{inline="1" color="Cornflowerblue"}% $\phi$ %ENDLATEX% is in the theory, and you are done. If it is %BEGINLATEX{inline="1" color="Cornflowerblue"}% $\lnot\phi$ %ENDLATEX%, then %BEGINLATEX{inline="1" color="Cornflowerblue"}% $\phi$ %ENDLATEX% is not in the theory (since the theory is consistent), and you are done. If it is neither, keep looking for more proofs. Since the theory is complete, you will eventually find either a proof of %BEGINLATEX{inline="1" color="Cornflowerblue"}% $\phi$ %ENDLATEX% or of %BEGINLATEX{inline="1" color="Cornflowerblue"}% $\lnot\phi$ %ENDLATEX%, and so the method outlined always terminates with a decision. </>

By the lemma, if an axiomatizable theory is undecidable, it is incomplete, and so it is a consequence of Gödel's first incompleteness theorem that

• Corollary to Gödel's first incompleteness theorem Any sufficiently strong consistent axiomatizable theory is incomplete.

It is that version of the theorem that explains the name. In particular, Peano arithmetic (and also any consistent axiomatizable extension of it) is incomplete.

• Philosophical remark. The corollary to Gödel's first incompleteness theorem destroys another pillar of Hilbert's program: since he intended to introduce, for example, arithmetic solely on the basis of finitistically justified axioms, the truths of arithmetic will be exactly those that follow from the axioms. He therefore supposed that the axioms would be complete: otherwise, there would be sentences about the numbers that were neither provable nor disprovable from the axioms and that are, therefore, since the axioms are the sole basis on which arithmetic is introduced, neither true nor false. But what Gödel showed is that any axiomatizable theory of arithmetic is incomplete.

Indication of the proofs

First incompleteness theorem

I shall first discuss the corollary to Gödel's first incompleteness theorem. I mention how to extend the proof outlined here to the full first incompleteness theorem below. The techniques that permit that extension also make it possible to give a simpler proof of the theorem (also discussed below), but the proof I give here is what leads to the second incompleteness theorem, and so it needs to be presented in any case.

• First, a rough version, to give the basic idea, with some details omitted and some outright mistakes.

Gödel showed that a sufficiently strong consistent axiomatizable theory is incomplete by showing how to write down a sentence that is true if and only if it is not provable in that theory. His sentence is called "the" Gödel sentence for the theory. How does it help? Is the Gödel sentence %$G$% provable in the theory or not? If %$G$% is provable, it follows that %$\lnot G$%. That can't happen, so %$G$% must not be provable. But %$G$% says that it is not provable, and so it turns out that %$G$% is true. Thus, the theory is incomplete: it can't prove %$G$% and, since %$G$% is true, it certainly can't prove %$\lnot G$%.

One of the big problems with the "proof" I just indicated is that it relies on the notion "%$G$% is true." It is not clear what that means: the theory may have more than one interpretation. True in which one? The careful statement of the proof must not rely on the notion of truth at all.

The second big problem is that I did not distinguish between what can be proved and what can be proved in the theory.

• (More) careful version.

Let %$T$% be a complete axiomatizable sufficiently strong theory. Recall that "sufficiently strong" means that %$T$% includes the theory %$A$%, and hence that anything that can be proved in %$A$% can, a fortiori be proved in %$T$%.

• Trivial but useful fact. Since %$T$% includes %$A$%, and %$A$% has 0 and %$S$%, successor, in its language, %$T$% has numerals: "0" for 0, "%$SSSSSSS0$%' for 7, and so forth. Since it would be tiresome to actually write out, say 100 %$S$%s to form the numeral for 100, we abbreviate it as follows: %$S^{100}0$%. The superscript is a notation for how many times to repeat the %$S$%.

Gödel showed (see below) how to associate a number with each sentence or sequence of sentences of the language of %$T$%, called "the" Gödel number of the sentence or sequence of sentences in such a way that there is some horribly complicated number-theoretic predicate, which we write "%$\mathrm{Pr}$%," that, in the theory %$A$%, expresses the notion "provability in %$T$%." In detail:

If %$\phi$% is a sentence in the language of %$T$% with Gödel number %$\mathfrak{n}$%, we write %$\ulcorner\phi\urcorner$% for the numeral %$S^{\mathfrak{n}}0$%, that is, for the numeral that denotes the Gödel number of %$\phi$%. We think of that numeral as a notation for %$\phi$% within arithmetic, a name for a linguistic expression, which make it somewhat analogous to the way we use quotation names in philosophical English. A proof is a sequence of sentences, and so if %$\mathcal{P}$% is a proof in the language of %$T$% with Gödel number %$\mathfrak{n}$%, we may, similarly, write %$\ulcorner\mathcal{P}\urcorner$% for the numeral %$S^{\mathfrak{n}}0$%, that is, for the numeral that denotes the Gödel number of %$\mathcal{P}$%.

Gödel showed (see below) that there is a horribly complicated number-theoretic predicate %$\mathrm{Pf}$%, the proof predicate, such that

%$\mathcal{P}$% is a proof of %$\phi$% if and only if %$\mathrm{Pf}(\ulcorner\mathcal{P}\urcorner ,\ulcorner\phi\urcorner)$% is a theorem of %$A$% if and only if %$\lnot\mathrm{Pf}(\ulcorner\mathcal{P}\urcorner ,\ulcorner\phi\urcorner)$% is not theorem of %$A$%.

There are, of course, many allied results. Here is one we shall need below: there is a number-theoretic predicate %$\mathrm{Neg}$% such that

%$\phi$% is the negation of %$\psi$% if and only if %$\mathrm{Neg}(\ulcorner\phi\urcorner ,\ulcorner\psi\urcorner)$% is a theorem of %$A$% if and only if %$\lnot\mathrm{Neg}(\ulcorner\phi\urcorner ,\ulcorner\psi\urcorner)$% is not theorem of %$A$%.

.

Now, the provability predicate %$\mathrm{Pr}$% is defined by %$\mathrm{Pr}(x)\leftrightarrow (\exists y)\mathrm{Pf}(y,x)$%—the definition is just a formalized counterpart of the metalinguistic idea that %$x$% is provable if there is a proof of %$x$%. It follows from what was said above about the proof predicate that the provability predicate is such that, for any sentence %$\phi$%, %$\phi$% is provable in %$T$% if and only if %$\mathrm{Pr}(\ulcorner\phi\urcorner )$% is provable in %$A$%.

"The" Gödel sentence for %$T$% is now a sentence %$G$% such that one can prove in %$A$% that %$G\leftrightarrow\lnot\mathrm{Pr}(\ulcorner G\urcorner )$%.

I can now prove half the corollary to Gödel's first incompleteness theorem:

• %$G$% is not provable in %$T$%. Suppose %$G$% is provable in %$T$%. Then %$\mathrm{Pr}(\ulcorner G\urcorner )$% is provable in %$A$% and hence in %$T$%. But then %$\lnot G$% is provable in %$T$%, which contradicts that %$T$% is consistent.

To complete the proof, I would now have to show that %$\lnot G$% is not provable in %$T$%. Unfortunately, that doesn't follow from our hypotheses. To show what goes wrong, here is an unsuccessful attempt at a proof:

• %$\lnot G$% is not provable in %$T$%. Suppose %$\lnot G$% is provable in %$T$%. Obviously, %$G$% is not provable in %$T$%, since if it were that would contradict the assumption that %$T$% is consistent. Thus, %$\mathrm{Pr}(\ulcorner G\urcorner )$% is not provable in %$A$%. If we could show that, in fact, %$\lnot\mathrm{Pr}(\ulcorner G\urcorner )$% is provable in %$A$% (which doesn't seem unreasonable to hope, since we just showed that no natural number is the Gödel number of a proof of %$G$%), then we would be done, since %$\lnot\mathrm{Pr}(\ulcorner G\urcorner )$% is, by the definition of %$G$%, equivalent to %$G$%, and so we would have a proof of %$G$%, contradiction.

We can patch things up by using "the" Gödel-Rosser sentence instead of the Gödel sentence: Everything is the same as above, except that one starts with the notion of a Rosser proof:

• For any %$p$% and %$n$%, %$p$% is a Rosser proof of %$n$%, %$\mathrm{Pf}_\mathrm{R}(p,n)$%, if and only if %$\mathrm{Pf}(p,n)\land (\forall q,m)(q<p\land(\mathrm{Neg}(m,n)\lor(\mathrm{Neg}(n,m))\rightarrow\lnot\mathrm{Pf}(q,m))$%.

• Rosser provability is now defined by %$\mathrm{Pr}_\mathrm{R}(x)\leftrightarrow (\exists y)\mathrm{Pf}_\mathrm{R}(y,x)$%.

That is a formalization of the notion defined above, where we have used the Gödel number of a proof as its length. It follows from what was said about the Rosser proof predicate that the Rosser provability predicate is such that, for any sentence %$\phi$%, %$\phi$% is Rosser provable in %$T$% if and only if %$\mathrm{Pr}_\mathrm{R}(\ulcorner\phi\urcorner )$% is provable in %$A$%. "The" Gödel-Rosser sentence for %$T$% is now a sentence %$G_\mathrm{R}$% such that one can prove in %$A$% that %$G_\mathrm{R}\leftrightarrow\lnot\mathrm{Pr}_\mathrm{R}(\ulcorner G_\mathrm{R}\urcorner )$%.

Now, finally, I can give a reasonably precise proof of the corollary to Gödel's first incompleteness theorem. You will be able to follow my discussion of Gödel's second incompleteness theorem, which immediately follows the proof, even if you skip the proof. Here is the

Proof.

• %$G_\mathrm{R}$% is not provable in %$T$%. Suppose %$G_\mathrm{R}$% is provable in %$T$%. Since %$T$% is consistent, there is then no proof at all of %$\lnot G_\mathrm{R}$% in %$T$%, and hence no such proof shorter than a proof of %$G_\mathrm{R}$% in %$T$%. Thus, %$G_\mathrm{R}$% is Rosser provable in %$T$%. Then %$\mathrm{Pr}_\mathrm{R}(\ulcorner G\urcorner )$% is provable in %$A$% and hence in %$T$%. But then %$\lnot G_\mathrm{R}$% is provable in %$T$%, which contradicts that %$T$% is consistent.

• %$\lnot G_\mathrm{R}$% is not provable in %$T$%. Suppose %$\lnot G_\mathrm{R}$% is provable in %$T$%. Then, for some %$n$%, it is provable by a proof of length %$n$%.We now prove %$\lnot\mathrm{Pr}_\mathrm{R}(\ulcorner G_\mathrm{R}\urcorner )$%, that is, %$\lnot (\exists y)\mathrm{Pf}_\mathrm{R}(y,\ulcorner G_\mathrm{R}\urcorner )$%, in %$A$%. Since %$\lnot G_\mathrm{R}$% is provable in %$T$% by a proof of length %$n$%, %$\mathrm{Pf}_\mathrm{R}(S^{n}0,\ulcorner\lnot G_\mathrm{R}\urcorner )$% is provable in %$A$%. Thus, it is provable in %$A$% that no %$y>n$% is a Rosser proof of %$G_\mathrm{R}$%—that is just a formalization of the following argument: since any Gödel number of any proof that is greater than %$n$% is preceded by a proof of %$\lnot G_\mathrm{R}$%, it cannot be a Rosser proof of %$G_\mathrm{R}$%. It is easy to prove in %$A$% that there is also no Rosser proof of %$G_\mathrm{R}$% of length exactly %$n$%, since the proof of length %$n$% is not even a proof of %$G_\mathrm{R}$% (since it is a proof of %$\lnot G_\mathrm{R}$%), let alone a Rosser proof of %$G_\mathrm{R}$%. Finally, we can show in %$A$% that there is no Rosser proof of %$G_\mathrm{R}$% of length less than %$n$%: We know that no such proof exists, because %$T$% is consistent, and we can verify that in %$A$% since there are only finitely many cases to check: for each %$m<n$%, %$m$% is not the Gödel number of a Rosser proof of %$G_\mathrm{R}$% and so it is a theorem of %$A$% that %$\lnot \mathrm{Pf}_\mathrm{R}(S^{m}0,\ulcorner G_\mathrm{R}\urcorner )$%. Putting the three cases together, we have shown that it is a theorem of %$A$% that %$\lnot\mathrm{Pr}_\mathrm{R}(\ulcorner G_\mathrm{R}\urcorner )$%. But then, by the definition of %$G_\mathrm{R}$%, it is a theorem of %$A$%, and hence of %$T$% that %$G_\mathrm{R}$%. Since, by hypothesis, %$\lnot G_\mathrm{R}$% is provable in %$T$%, that contradicts the consistency of %$T$%. %$\square$%

Second incompleteness theorem

For the second incompleteness theorem, we use the original Gödel sentence (no more Rosser) and consider the proof that %$G$% is not provable in %$T$%. What we showed, in effect, is that if %$G$% is provable in %$T$%, then %$T$% is inconsistent. That is,

if %$T$% is consistent, then %$G$% is not provable in %$T$%.

We can now continue as follows to give an incorrect proof that %$T$% is inconsistent: But "%$G$% is not provable in %$T$%," by the definition of %$G$% yields %$G$%, and so, from the hypothesis that %$T$% is consistent, we proved %$G$%. Since, by the first incompleteness theorem, %$G$% is not provable, we have a contradiction, and so %$T$% is not consistent.

The proof is obviously wrong: the first incompleteness theorem does not state that %$G$% is not provable, but that %$G$% is not provable in %$T$%. Our proof of %$G$% was not given in %$T$%, and so there is no contradiction. But what happens if we take the proof of %$G$% and formalize it in %$T$%? We get a proof of the second incompleteness theorem. Here it is, where I have paired the formal statements within %$T$% with the informal statements about %$T$% that led to them:

Suppose %$\mathrm{Pr}(\ulcorner G\urcorner )$%.	Suppose %$G$% is provable in %$T$%.
Then %$\mathrm{Pr}(\ulcorner\mathrm{Pr}(\ulcorner G\urcorner )\urcorner )$%	Then %$\mathrm{Pr}(\ulcorner G\urcorner )$% is provable in %$T$%.
But then %$\mathrm{Pr}(\ulcorner\lnot G\urcorner )$%.	But then %$\lnot G$% is provable in %$T$%.
So %$\lnot\mathrm{Con}$%.	So %$T$% is inconsistent.

In the final step, %$\mathrm{Con}$%may be taken to be an abbreviation for %$\lnot\mathrm{Pr}(\ulcorner G\land\lnot G\urcorner)$%. We may now argue correctly as follows: Suppose %$\mathrm{Con}$% is provable in %$T$%. Then, by the argument above, %$\lnot\mathrm{Pr}(\ulcorner G\urcorner )$% is provable in %$T$%. However, from that, by the definition of %$G$%, we obtain that %$G$% is provable in %$T$%. But that contradicts what we showed earlier, that %$G$% is not provable in %$T$% and disproves the assumption that %$\mathrm{Con}$% is provable in %$T$%. That is, finally, %$\mathrm{Con}$% is not provable in %$T$%. \square

The proof outline above, while correct, is misleading: the hard part is showing that it is possible to formalize the proof in %$T$%, and I have not said anything about that, nor do I intend to, except for this: the formalization is difficult and requires that %$T$% be quite strong. The requirement that it contain %$A$% for the weak theories %$A$% I listed above, which was good enough for the proof of the first incompleteness theorem, is not good enough for the second incompleteness theorem. However, it suffices to let %$A$% be Peano arithmetic, which is plenty good enough for the philosophical applications we envisioned.

The fixed-point theorem

The piece of the proof of the two incompleteness theorems that seems most magical is the phenomenon usually inaccurately characterized in terms of self-reference, that is, the fixed-point theorem:

Fixed-point theorem In any sufficiently strong theory, for any predicate %$P$% expressible in the language of the theory, one can show that there is a sentence %$\phi$% such that the theory proves %$\phi\leftrightarrow P(\ulcorner\phi\urcorner ).$%

The Gödel and Gödel-Rosser sentences are both obtained by applying the fixed-point theorem for suitable %$P$%. There is a proof of the fixed-point theorem for a simple theory here. The usual proofs of fixed-point theorems for more traditional theories, like the candidates for %$A$% described above, use the same technique, but they are muddied with details about how to use Gödel numbers and the like. In addition, the usual fixed-point theorems for more traditional theories can be obtained as corollaries of the fixed-point theorem stated here, by showing that the theory given here can, in a suitable sense, be interpreted in those theories.

The fixed-point theorem can also be used to prove

• Tarski's theorem. The set of true sentences of a sufficiently strong theory is not definable.

One just uses the fixed-point sentence for %$P=\text{``}x\text{ is not true''}$%.

• A version of Gödel's first incompleteness theorem. No sufficiently strong axiomatizable theory can be both complete and consistent.

If a sufficiently strong theory were both complete and consistent, the set of theorems would be decidable (by the lemma above), hence definable, and the set of theorems would be the set of true sentences, contradicting Tarski's theorem. I prove versions of those two results here.

Abstract versions of some of the results

The point of proving the abstract versions of incompleteness and related results here is to show that the usual claim that the theorems make use of self-referential sentences is greatly exaggerated. The theorems are here proved about very simple interpreted languages that cannot express the relationships that are usually taken to be evidence of self reference. In fact, the languages, in a certain sense exhibited below, have only atomic sentences.

Formal proofs

Let %$C$% be a nonempty set called the set of constants. Fix a binary relation %$E $% on %$C$%, the extension function; and a pair of functions %$s$% and %$p$%, subject and predicate, from %$C$% to %$C$% such that for every pair %$(r,c)$% of constant symbols there is an constant %$d$% such that %$p(d)=r$% and %$s(d)=c$%. We think of %$d$% as expressing the sentence %$r$% of %$c$%, where %$c$% is the subject, and %$r$% is the predicate with extension %$\{ x: E(r,x)\}$%. When thinking of a constant as a predicate, I shall usually use letters %$r,s,t$% for it; when thinking of a constant as a name, I shall usually use %$c,d,e $%. While that aids understanding, the predicates and the constants are in fact the same objects.

Definition. A predicate %$r$% is a predicate of predicates if for all predicates %$s$% and %$t$%, if %$s$% and %$t$% are coextensive (that is, if for all %$c$%, %$E(s,c)$% if and only if %$E(t,c)$%), then %$s$% is in the extension of %$r$% if and only if %$t$% is in the extension of %$r$% (that is, %$E(r,s)$% if and only if %$E(r,t)$%).

Since they are the only predicates of interest for present purposes, we shall assume that all predicates are predicates of predicates. That is, our results will concern languages: structures of the form %$(C,E,p,s)$% in which every predicate is a predicate of predicates. That is a class of structures that is defined by an axiomatizable theory, the theory of languages: the theory consists of the single first-order sentence that says that every pair of a predicate and a constant is expressed by a constant and that every predicate is a predicate of predicates.

I have used the same set of constants to serve as constants and predicates and to express sentences, and assumed that every constant is also a predicate and expresses a sentence, and that every predicate is a predicate of predicates. None of those assumptions are essential, but they simplify the statements of the claims below.

• A constant %$d$% expresses a true sentence if, by definition, the subject is in the extension of the predicate, that is %$E(p(d),s(d))$%.
• A norm of a predicate %$r$% is a constant %$d$% that expresses a sentence 'the predicate %$r$% holds of the constant %$r$%,' that is, a constant %$d$% such that %$p(d)$% is coextensive with %$r$% and %$s(d)=r$%.

A norm of a predicate %$r$% expresses a true sentence if %$r$% is autological.

• Say that the language %$(C,E,p,s)$% has appended norms if there is a function %$a $% from %$C$% to %$C$% (to be thought of as a function from predicates to predicates) such that for any constant %$d$%, %$d$% is in the extension of the predicate %$a(r)$% (that is, %$E(a(r),d) $% ) if and only if there is a norm of the predicate %$d$% in the extension of %$r$% (that is, if and only if there is %$b $% in the extension of %$r$% such that %$p(b) $% and %$d$% are coextensive and %$s(b)=d$%.)

In human language, not part of the official notation, and abusing use and mention, a language has appended norms if there is a function %$N$% from constants to their norms such that for every predicate %$P$% there is a predicate %$Q=a(P)$% such that %$(\forall x)(P(N(x))\leftrightarrow Q(x)) $%. Sloppily, %$a(P)=Q=PN$% , or %$a(P)$% is %$P$% with the norm function appended.

• Fixed point theorem. Suppose that the language %$(C,E,p,s)$% has appended norms, and let %$a $% be a function witnessing that fact. Let %$r$% be a predicate. Then a norm of %$a(r)$% is in the extension of %$r$% if and only if a norm of %$a(r)$% expresses a true sentence.

Proof. A norm of %$a(r)$% is a constant that expresses '%$a(r)$% of %$a(r)$%.' Thus, a norm of %$a(r)$% expresses a true sentence if and only if %$E(a(r),a(r))$%. By the definition of the function %$a$%, %$E(a(r),a(r))$% if and only if there is a norm of %$a(r)$% in the extension of %$r$%, which completes the proof. %$\square$%

• Useful lemma. If %$t$% and %$u$% are both norms of the same predicate %$r$%, then %$t$% expresses a true sentence if and only if %$u$% expresses a true sentence.

Proof. %$t$% expresses '%$r$% holds of %$s(t)$%' and %$u$% expresses '%$r$% holds of %$s(u)$%,' where %$s(t)$%, %$s(u),$%, and %$r$% are coextensive. Since %$r$% is a predicate of predicates, it holds of %$s(t)$% if and only if it holds of %$s(u),$%. \square

Applications

Say that a set of constants is definable in the language %$(C,E,p,s)$% if it is the extension of a predicate of %$(C,E,p,s)$%. More precisely, %$S\subseteq C$% is definable in the language %$(C,E,p,s)$% if for some %$c$% in %$C$% %$S=\{x:E(c,x)\}$%.

• "Tarski's theorem." Suppose the language %$(C,E,p,s)$% has appended norms. The set %$N=C-\{x:E(p(x),s(x))\}$% of constants that do not express true sentences is not definable in %$(C,E,p,s)$%.

Proof. Since the language %$(C,E,p,s)$% has appended norms, let %$a $% be a function witnessing that fact. If %$N$% is definable, then there is a predicate %$r$% such that %$N=\{x:E(r,x)\}$%. By the fixed point theorem, a norm of %$a(r)$% is in the extension of %$r$% if and only if a norm of %$a(r)$% expresses a true sentence. That is, a norm of %$a(r)$% is in %$N$% (does not express a true sentence) if and only if a norm of %$a(r)$% expresses a true sentence. That contradicts the useful lemma. %$\square$%

Remark. If the predicates are closed under complement (as they are in familiar applications to languages in which there is a negation sign), it follows that the set of constants that express true sentences is not definable, which is what is usually stated.

• "Gödel's first incompleteness theorem." Suppose the language %$(C,E,p,s)$% has appended norms. Let %$F$% (the "nontheorems") be a definable set of false sentences. Then either there is a false sentence not in %$F$% ("%$F$% is incomplete") or there is a true sentence in %$F$% ("%$F$% is inconsistent").

Proof. If not, that is, if every false sentence is in %$F$% and no true sentence is in %$F$%, then %$F=N$%, and so %$F$% cannot be definable by Tarski's theorem.

Remark. If %$F$% is a consistent definable set of sentences, the theorem not only applies to %$F$% but to every definable consistent set of sentences that includes %$F$%. Thus, %$F$% is essentially incomplete.

The treatment above is suggested by, but by no means the same as, Smullyan57.

Conclusions suggested by the formal results

The point of the above is that it makes clear that the sense in which "self reference" is required for the proof of the fixed point theorem and hence Tarski's and Godel's theorems is entirely metalinguistic. I have proved a fixed-point theorem for languages in which, at best, there are atomic sentences, but no others, there are no relations between sentences (other than identity or diversity) that can be derived from the theory of languages, and the "Gödel numbers" (the constants associated with each sentence and predicate) are not given by any computational method. The fixed-point theorem—even an instance of the theorem for a single predicate—cannot be proved in the theory of languages: after all, a fixed point is a constant that bears a certain relationship to a predicate, and no nontrivial such relationships follow from the theory of languages.
Here are precise versions of the claims I just made. more... close

• There is a language with domain a single constant, and, thus, with a single sentence. In that language, there are no sentences that bear nontrivial relations to each other. Since every theorem of the theory of languages must be true of that language, no such theorem can assert that two sentence are related in a nontrivial way.
• Let %BEGINLATEX{inline="1" color="Cornflowerblue"}% $(C,E,p,s)$ %ENDLATEX% be language, and let %BEGINLATEX{inline="1" color="Cornflowerblue"}% $\rho$ %ENDLATEX% be a permutation of %BEGINLATEX{inline="1" color="Cornflowerblue"}% $C$ %ENDLATEX%. Then %BEGINLATEX{inline="1" color="Cornflowerblue"}% $(C,E,p\rho ,s)$ %ENDLATEX%, %BEGINLATEX{inline="1" color="Cornflowerblue"}% $(C,E,p,s\rho )$ %ENDLATEX%, %BEGINLATEX{inline="1" color="Cornflowerblue"}% $(C,E,p\rho ,s\rho)$ %ENDLATEX%, and %BEGINLATEX{inline="1" color="Cornflowerblue"}% $(C,\{(x,y):E(\rho (x),\rho (y))\},p ,s)$ %ENDLATEX% are also languages. Thus, the "Gödel numbers" of the predicates and sentences are subject to fully general unrelated permutations, and they are therefore not given by any computational method.

</>

For self reference to be possible within a language, the language must have a definable set of constants expressing (Gödel numbering) theorems that includes a constant expressing a formalization of the fixed point theorem and includes constants expressing the instances of the following reflection scheme: %\[\phi\leftrightarrow T(\ulcorner\phi\urcorner )\]%, where %$T$% holds of the "Gödel numbers" of the theorems.

For self reference to be possible for a language user (by language, all I mean is something that fits the thin definition above---it could be a system of representations, not a language in an ordinary sense), the language user must implement the definition of %$T$% and be competent to determine that %$T$% holds of the names of the formalization of the fixed point scheme and the instances of the reflection scheme. A standard way to ensure that is to require that %$T$% be definable from axiom schemes and rule schemes in the usual way, that the language user be committed to the axioms and becomes committed to whatever follows from prior commitments in virtue of the rules whenever that is appropriately presented. That isn't actually enough: one must require in addition that the language user has (1) the capacity to prove the fixed point theorem, (2) the capacity to express an instance of the scheme for each sentence %$\phi$% she has the capacity to use, and (3) the capacity to recognize that names of the instances of the scheme she has the capacity to express are in %$T$%. Nothing so far has required that the proofs of the various instances of the reflection scheme have anything in common. Capacity (3) seems to me to only be plausible if there is a schematic proof of the reflection principle, that is, a proof scheme that has as instances proofs of every instance of the reflection scheme, and if the language user has the capacity to obtain proofs of instances of the scheme that language user has the capacity to express in virtue of the scheme.

The account of what it is for a language user to be capable of self-reference doesn't require an explicit mechanism of self reference, but it doesn't prohibit such a mechanism either. If a mechanism of self reference requires the capacity to name predicates, apply predicates to those names, to systematically introduce new predicates via simple logical definitions that take predicates and their names as inputs, and to draw systematic conclusions on the basis of such definitions, which seems to me to be true (emphasizing once again that by language, predicates, names, definitions, I mean something very thin, as shown above), then a capacity for self reference brings with it the capacities I outlined above.

A language in which a fixed-point theorem can be proved

A simple way to nearly define a language in which the fixed point theorem can be proved follows. (My definitions of functions have to be fixed up to be total and onto in pretty much any way you like. This is a notational variant of something in the Smullyan article): there is a single predicate %$P$%, a function symbol %$q$% (quotation), and a function symbol %$n$% (norm). A sentence is%$P$% followed by a term, %$q$% followed by a sentence or a term is a term, and otherwise terms are formed in the usual way. The only rule is that %$Pnt(x)$% is interdeducible with %$Pt(qt)$%, for any term %$t$% with one free variable %$x$%. It follows that

(*) %$PnqPnx$% if and only if %$PqPnqPnx$%.

Now, adopt the following semantics: %$P$% is a predicate of expressions of the language. Denotation of a term is computed as follows, where %$t$% is an arbitrary term: The denotation of %$nt(x)$% is the denotation of %$t(qt)$%. The denotation of %$qt$% is %$t$%.

The denotation of %$nqPnx$% is the denotation of %$qPnqPnx$%, which, in turn, denotes the expression %$PnqPnx$%. Thus (*) says that

%$PnqPnx$% if and only if "%$PnqPnx$%" has the property %$P$%,

the fixed point theorem. Of course, this simple language doesn't have the reflection principle.

The sentence %$PnqPnx$% is often rendered, "This sentence has property %$P$%," or the like. That isn't a bad a translation as one might at first think, if "This sentence has property %$P$%" is to be understood in terms of taking the denotation of "this" to be "This sentence has property P," so that the sentence ""This sentence has property P" has property P" is taken to be obtained from it using Leibniz's law. The construction I used is, admittedly, a bit closer to the Quinean (see Quine63 255, Smullyan57 56n)

"Yields when appended to its quotation a sentence with property %$P$%" yields when appended to its quotation a sentence with property %$P$%.

The construction didn't depend on any special properties of %$P$%, and so, if the language had more predicates (formulas with one free variable), they would have fixed points too.

-- ShaughanLavine - 31 Oct 2006 - written 23 Oct 2005

Quotation, decidability, recursiveness, representability

Use a language that is such that only finitely many symbols are used—for example, one often uses infinitely many different symbols, %$x_{0},x_{1},\ldots$% as variables, but we must use the symbols, for example, %$x$% and %$'$%, instead, and take variables to be the sequences of symbols %$x,x',x'',\ldots $%. Assign a nonzero number to every symbol of the language of a theory. (That is, for example, assign 2 to "(", 3 to ")", 4 to "0", 5 to "%$\forall$%", 6 to "%$x$%", 7 to "%$'$%", and so on.) Every formula is now a sequence of numbers. We can turn every sequence of numbers, say 12, 6, 10, 12, 13 into a number as follows: %$2^{12}3^{6}5^{10}7^{12}11^{13}$%. That is what I am going to use for "quotes," or Gödel numbers: it gives me a one-to-one correspondence between expressions (arbitrary sequences of the symbols) and some numbers. A proof is a sequence of formulas, and so I can use the same trick: a proof is a sequence of formulas, each of which is a sequence of symbols, and so a proof corresponds to the sequence of Gödel numbers for its formulas, which, in turn, corresponds to a single number for that sequence of numbers, the Gödel number of the proof.

With a little bit of ingenuity and a lot of patience, one can show that all of the following are monstrous formulas of arithmetic: "%$n$% is the Godel number of a formula," "the sequence with Godel number %$m$% has length %$n$%," "%$n$% is the Godel number of a proof of the formula with Godel number %$m$%," and so on.

The type of Gödel numbering I have proposed makes use of exponentiation, but the theories %$A$% I have been using only include + and %$\times$%. By being more careful, that is, using a better coding, one can make do with just + and %$\times$%, and so + and %$\times$% is enough. There is a straightforward way to code any sequence of numbers using only + and %$\times$%, not as a single number, but as a pair of numbers. It is annoying to use pairs of numbers instead of single numbers. One could use a special way to code pairs of numbers as single numbers, and then use those, but it is traditional, following Gödel, to use the code as pairs using just + and %$\times$% for only one purpose: defining exponentiation, and to then use a code like the one I have described thereafter. The curious may investigateDefiningExponentiationfromPlusandTimes.

So much for Godel numbering. Now, decidability. Decidability is an intuitive notion, and so its formalization requires some kind of analysis. It isn't even clear to what the notion of decidability applies. I'll just take it, somewhat arbitrarily, but most conveniently for our purposes here, to take it to apply to sets of numbers.

• Intuitive characterization. A set of numbers is decidable if there is a fully specified method for telling whether or not a number is in it.

What is a fully specified method? It is a finite axiomatization %$^{\text{footnote}}$% plus a formula: A method for making a decision whether or not a number is in a set is fully specified if and only if one can write it out in full detail, that is,

1. Give a set of axioms, %$D$%, for the terms that occur in it, and
2. Give a formula expressing that method itself, that is, a formula %$\phi (x)$% such that
   1. %$\phi (x)$% holds of a number %$n$% if and only if %$n$% is in the set, and
   2. One can always tell in a methodical way whether or not the formula applies, that is, such that
      1. %$\phi (S^{n}0)$% is a theorem of %$D$% if %$n$% is in the set, and
      2. %$\lnot\phi (S^{n}0)$% is a theorem of %$D$% if %$n$% is not in the set.

That analysis motivates the following definitions.

• Definition. A set of numbers is representable in a theory %$T$% by a formula %$\phi (x)$% if
  • The symbols 0 and %$S$% are in the language of %$T$%
  • %$\phi (S^{n}0)$% is a theorem of %$T$% if %$n$% is in the set
  • %$\lnot\phi (S^{n}0)$% is a theorem of %$T$% if %$n$% is not in the set
• Definition. A set of numbers is recursive if it is representable in a finitely axiomatized theory.

• Intuitive claim (Church's thesis). A set is decidable if and only if it is representable in some finitely axiomatized theory %$T$%.

Impressive additional evidence. People have made many (20 or 30) different intuitive attempts to characterize the notion of decidability, and they all turn out to be equivalent.

• Theorem. A set is representable if and only if it is representable in any of the theories we discussed above as candidates for %$A$%.

Sketch of proof. The direction from left to right is trivial. Suppose the set %$S$% is represented in the finitely axiomatized theory %$T$% by the formula %$\phi$%. As we have essentially discussed above, there is a formula %$\mathrm{Pr}$% in the language of %$A$% such that for any sentence %$\sigma$% in the language of %$T$%, %$\sigma$% is a theorem of %$T$% if and only if %$\mathrm{Pr}(\ulcorner\sigma\urcorner )$% is a theorem of %$A$%. Thus, the set %$S$% is represented over %$A$% by the formula %\[\mathrm{Pr}(\ulcorner\phi (S^{n}0)\urcorner )\land\lnot\mathrm{Pr}(\ulcorner\lnot\phi (S^{n}0)\urcorner ).\qquad\square]%

Finally,

• Godel's First Incompleteness Theorem. Any sufficiently strong consistent axiomatizable theory is essentially undecidable.

Sketch of proof. It is enough to show that any sufficiently strong consistent axiomatizable theory is not recursive, since it will follow that any consistent axiomatizable extension of a sufficiently strong consistent axiomatizable theory is also not recursive.

Suppose a sufficiently strong consistent axiomatizable theory %$T$% is recursive. Then it is representable in the theory %$A$% and hence in the theory %$T$% by a formula %$\phi$%. Let %$G$% be a fixed point of %$\lnot\phi$%.

• %$G$% is not provable in %$T$%. Suppose %$G$% is provable in %$T$%. Then %$\phi (\ulcorner G\urcorner )$% is provable in %$T$%. But then %$\lnot G$% is provable in %$T$%, which contradicts that %$T$% is consistent.
• %$\lnot G$% is not provable in %$T$%. Suppose %$\lnot G$% is provable in %$T$%. Obviously, %$G$% is not provable in %$T$%, since if it were that would contradict the assumption that %$T$% is consistent. Thus, %$\lnot\phi (\ulcorner G\urcorner )$% is provable in %$T$%. But %$\lnot\phi (\ulcorner G\urcorner )$%, by the definition of %$G$%, is equivalent to %$G$%, and so we have a proof of %$G$%, once again contradicting that %$T$% is consistent.

Thus, neither %$G$% nor %$\lnot G$% is provable in %$T$%, and so, by the definition of %$G$%, neither %$\lnot\phi (\ulcorner G\urcorner )$% nor %$\phi (\ulcorner G\urcorner )$% is provable in %$T$%. That contradicts the claim that %$\phi$% represents a set, and therefore shows that %$T$% is not recursive, as required. %$\square$%

• #Set DENSITY = 232