Musing
I’ve always found the concept of Gödel’s (first) incompleteness theorem fascinating. However, I was never able to understand the proofs I saw (e.g. the ones on YouTube). They just always seemed to leave some important details out that I just couldn’t bring myself to accept on faith. So I read Leary’s book and finally every step of the proof made sense. To prove incompleteness, you have to code your formulae of first order logic into an arithmetic system of the natural numbers. This arithmetic system needs to be strong enough to make this coding scheme (called Gödel numbering) provably work. In simpler terms, you have to give your formulae names.
This is a companion page to first-order-logic. There are notations from that page that will be important here.
The proof of Gödel’s theorem is very beautiful. At its heart, it relies on the self-reference lemma which is basically a fixed-point and diagonalization related result. Two seemingly unrelated results come to mind when thinking about such fixed points and diagonalizations. The existence of Nash equilibria for zero-sum games is based on (Brouwer’s or Kakutani’s) fixed point theorem. Cantor’s theorem, which says the real numbers are uncountable, is based on a diagonalization argument. Ultimately, it all goes back to the Liar’s Paradox “this sentence is false”. Once you are able to talk about yourself, in some rigorous sense, you will find that real contradictions could arise.
For pretty much all of this page, we will talk specifically in the language of number theory for which the standard model is and all the symbols are the ones you are used to from basic arithmetic. So if you see talk about “a formula” you can assume it means a formula in unless stated otherwise.
The Minimal Arithmetic
The axioms of minimal arithmetic for the purposes of this page are called . The axioms are1:
Formulae
A key concept in setting up Gödel’s incompleteness theorems is that of representability. We’ll give a better definition later, but, roughly speaking, incompleteness is saying that there are true sentences that can’t be proved. So one might get the following devious idea: what if we just made every true sentence in a given model, i.e. every sentence in , an axiom? Then every proof is exactly one step and every true sentence can be proved. The problem with this is if I hand you a random sentence in the language you may not be able to tell me if that sentence is an axiom or not. We’ve taken out a loan that we can’t repay.
First a few definitions:
A subset is called representable if there is a k-ary formula that represents the set such that:
If we are not able to have but only the weaker condition then the set is weakly representable. Note that any finite set is representable. Once we are able to give Gödel numbers to formulae, it will become important what sets of Gödel numbers are representable or not. To spoil the ending a little, is not representable. In fact, it is not even definable (see the Tarski Undefinability theorem later).
A formula defines a subset in if:
Now we can define 3 different kinds of formulae, .
A collection of -formulae is the smallest set of formulae which contains:
- Every atomic formula, e.g. .
- Every negation of an atomic formula.
- Every formula of the form and for both formulae.
- Every bounded quantified -formula.
- Every existentially quantified -formula.
The definition is recursive, starting from the atomic formulae. Some comments on points 4 and 5 are in order. A bounded quantifier is one of the four strings: . Each is just a short hand notation since strictly speaking should not be used inside a quantifier like this. For example, is an abbreviation for , but I think the meaning of the symbols are clear. Point 4 means then that if is a -formula and does not appear in then each of the four bounded quantifiers on are in the collection, e.g., is a -formula. Point 5 just says is in the collection when is in the collection.
A collection of -formulae has the same 1-4 above except point 5 replaces the existential quantifier with the universal one, i.e. . This change is actually quite important. Finally, a -formula sits at the intersection and the collection only has formulae from points 1-4 above (i.e. bounded quantifiers only). The negation of a formula is logically equivalent to another formula since everything is bounded. For example, “there does not exist an x smaller than t such that is true” translates logically to “for every x smaller than t is true”. The negation of formulae may not have this nice property. could be taken to (a logically equivalent formula in) and vice versa under negation.
The key facts we want to retain here are:
- If a set is defined by a -formula then it is representable.
- If a set is defined by a -formula then it is weakly representable.
A representable set is decidable, meaning there is some algorithm which we can run that on every input will halt and return “yes” if the input is in the set and “no” if the input is not in the set. A weakly representable set is only computably enumerable, meaning for every input which is in the set the algorithm will halt and return “yes” but it might never halt on inputs that are not in the set. A lot of machinery is built to show that Gödel numbering is not only well defined (injective encoding and decoding), but that every function needed to encode and decode Gödel numbers are representable functions. By function here, we mean what we usually mean by a function in math, something that looks like , and not the specific n-ary function symbols in . Such a function is really just a subset of , i.e. a set of tuples of length : . Representability of a function will simply mean representability of the set. This will mean that the function’s outputs are provably so in which allows us to say the deductive steps needed to prove Gödel’s incompleteness theorems will not break during steps needed to encode and decode formulae. Nor would they ever run into a “the algorithm never halts” situation during those steps.
Gödel Numbering
Eventually, we need a way for formulae to talk about themselves. To do that, we use Gödel numbering where we give each string in the language a natural number code. Whatever coding scheme we use, we need to ensure that we can, in principle, encode and decode any formula, and furthermore, that we can prove that the encoding and decoding we do is right. To be able to do that, the coding scheme must be injective, meaning it must be 1-to-1. For if we coded two different formulae to one code, we wouldn’t be able to unambiguously decode that code.
The scheme for Gödel numbering is actually quite simple and at its heart relies on one truth about arithmetic: the fundamental theorem of arithmetic. This truth will guarantee that our coding scheme is injective. Further, in Gödel’s incompleteness theorem, it will be required that the axiom set we analyze “extends the minimal arithmetic”. We need the axioms to be strong enough so that we can prove each instance of Gödel numbering works. Without both the truth of the fundamental theorem of arithmetic and the fact that our axioms can at least prove individual instances of the coding scheme, we can’t form a self referencing sentence.
The fundamental theorem of arithmetic tells us that any number greater than 1 can be uniquely factorized, up to ordering, into the product of prime numbers (a single prime also counts). For example and this is the only way to factorize . This general theorem, which can be proved in Peano Arithmetic, guarantees our coding scheme is injective, looking at it “from the outside”.
There are different ways one could come up with Gödel numbering. We will give only an intuitive look at a simple one here.
First, give each symbol of the language a unique natural number. For example, we could assign the number , the number , the number , the number and so on (Leary’s assignments are in Table 5.1). We can give each variable symbol the number and this will not clash if we give all other symbols odd numbers only. Then, any string in our language becomes a sequence of natural numbers. For example, the string (going back to Polish notation) would become the ordered sequence where we used the subscript to emphasize the sequence nature. We can take that ordered sequence and produce the Gödel number of the sentence like so:
Here we’re just using to denote turning the sequence into a single number while is the prime number. There is a bounded mechanical procedure for producing the -th prime number, for example, we could just do the naive thing and check each number 1 by 1 and create a list. It doesn’t matter that doing so would take a very long time or would require a vast amount of compute once the primes got big enough. Everything we care about here is in principle we can always do this so the encoding is feasible. We use in the exponent so that we may, if we want, encode the number in a sequence without running into trouble. Finally, by the fundamental theorem of arithmetic, if I gave you some number, you can always uniquely factorize it and just check does that factorization conform to the above form or not. Specifically, once factorized, a Gödel number will always be products of primes in order, never skipping primes. For example, you know the number is not a Gödel number because skips past .
For notational convenience, and to be able to talk about arbitrary formulae without writing them out, we will use the symbol to denote the Gödel number of . To get you simply take the exact string of and perform the procedure described above.
The final point we make here is that although our scheme up to now is intuitive, it’s a bit unwieldy to work with when actually proving out all of the necessary machinery. For example, we can encode easily arbitrary strings but there’s not an obvious way for us to tell apart a syntactically garbage string from a syntactically good string once we have just the Gödel numbers (we could do it, it’s just hard). An easier to work with encoding scheme is given by Leary in definition 5.7.1. That encoding scheme is recursive and takes into account the structure of valid formulae rather than simply encoding every string symbol by symbol. The numbers that come out of that encoding scheme are much larger because you will have power towers (things that look like ) but that will not be a problem in principle. Leary’s encoding scheme makes it much easier to prove the results that we’ll discuss in the next section.
The Bridge
The end goal here is to be able to precisely talk about the set of all theorems of some axiom set . This set we denote and it is the set of all Gödel numbers of theorems of A. A theorem is simply any sentence that can be deduced from the axioms (it includes the axioms themselves). As it turns out, this set is only weakly representable.
A large bulk of the machinery of the proof of Gödel’s incompleteness theorems rests on proving that every set, formula, and function that we use to build up to are representable/decidable. But first, a few more comments.
One of the confusing things about working on this proof is distinguishing different views of the same thing. Or, if you don’t like monistic language, distinguishing different things that point to the same idea. The machinery uses sets, functions and formulae and we need to keep all of this straight. It’s very easy to mush them all together into a single concept. To help us distinguish things we’ll follow Leary’s lead and use typeface. This will be much clearer with a few examples.
Consider the set of even numbers, which we will call (notice the typeface). Now, the formula which is is true if and only if is even so it defines the set . In fact, because is a -formula, it represents .
Another example is the set of prime numbers. A simple formula that defines this set is:
Note that the strict signs prevent the trivial factorization. is again representable (the set is) because the formula which defines it is a -formula. Because the set is representable you can always prove when a number is prime and when it isn’t a prime.
Now an example of a function. Let’s look at the sequence which gets coded to such that is the formula which got broken down and symbol-by-symbol encoded into the sequence . We would like to be able to create a function that takes and a position number and gives which would help us to decode Gödel numbers. To define the function, we look for a formula such that if we plugged in (order is important!) the formula would be true and the formula would be false if we plugged in bad values. In fact, such a formula can be constructed, though we will not show all the steps to do so. The formula looks like:
The formula is true if and only if is a valid Gödel number, the formula is true if and only if is the -th prime, and the formula is true if and only if evenly divides . Again, this is a -formula (to verify, you’d have to show , and are all -formulae) so the function is representable. The general theme of this work is to build a useful function from more basic functions, ensure that all the quantifiers are bounded, and so come up with a -formula which represent the that function. There’s a lot of details being omitted here because building all of these functions and tying them together feels akin to building a compiler. It’s a lot of work.
We simply highlight and discuss (but not construct) 2 very important functions, , and 2 very important sets: , .
Out of Notation
I’m running out of good notation to denote and and the difference between the function, formula, and set. You will have to use arguments in the expression as well as type face to tell them apart. Functions take just the input arguments. Formulas that represent functions will need an additional argument since (the graph of) a function is a subset in .
The function takes a number and returns the Gödel number of the numeral , i.e. . The function takes the Gödel number of a formula , (the Gödel numbers of) a variable and term and returns the Gödel number of the formula after substituting every free instance of the variable with the term . Both and are representable, by formulae and where the is the “return value” of the functions.
So imagine you are given a formula of a single free variable and you want to put the Gödel number of some other formula, say , into where used to be. We need to do this to do the Self Reference Lemma in the next section and this operation is exactly what and allow us to do. takes a number (say, ) and gives us the Gödel number of its numeral. takes a Gödel number of a formula (say, ), variable (say, ), and a term (say, ) and returns the Gödel number of the formula . These two functions legitimizes us starting from the Gödel number of and ending up with the Gödel number of with every step in “how we did it” provable from .
The set is a set represented by the formula for which it can be proven from that is the Gödel number of a formula that is the last step in a valid sequence of deductions coded by the Gödel number . To code a sequence of deductions, just recurse on our , i.e. do the operation . It can be proven that, because deductions take finitely many steps, is a representable set by such a formula.
Finally, we construct now the -sentence weakly representing :
It is only in this final step that we have the unbounded quantifier and it is here that we go outside of representability. The fact that can not prove that a given formula isn’t a theorem is the gap where the incompleteness theorem lives.
The Self Reference Lemma
Self Reference: for any formula with exactly one free variable, there exists a sentence for which
Proof: (omitted)
The lemma is short, but the implications are deep. We omit the proof because it is rather technical. The self reference lemma tells us that, roughly speaking, formulas can talk about themselves (hence the name). The formula says that its own Gödel number makes true if and only if itself is true. More simply, says ” is true about me”. The way that says the word “me” is via Gödel numbering. Leary quotes Shakespeare on this point, and it helped me to understand.
Juliet, Romeo and Juliet
What’s in a name? That which we call a rose
By any other name would smell as sweet;
As long as our naming scheme is injective and representable we can use the self-reference lemma to prove Gödel’s incompleteness theorems. Strictly speaking, we don’t need the full self-reference lemma to prove Gödel’s incompleteness. We will only need to prove that the fixed point exists for a certain formula. But it will be convenient to know that some fixed point exists for every formula with exactly one free variable. It will also allow us to easily switch sentences for Rosser’s strengthening of Gödel’s theorem.
Gödel’s First Incompleteness Theorem
A set of axioms is said to be incomplete if, from those axioms, we can not, for every sentence , deduce either or . In other words, there exists at least one sentence such that neither nor . In this case, is said to be independent of the axioms. Gödel originally proved his theorem using something called consistency, but we will discuss 4 different “versions” of his theorem here. We will start with an easy statement first which doesn’t quite prove incompleteness but is almost all of the way there. Then we will discuss Gödel’s original -consistency based proof. We’ll give a version based on soundness of the axioms and finally finish with Rosser’s strengthened form of Gödel’s first incompleteness theorem, where the -consistency condition was avoided by a clever tweak to the self-referencing formula. We will not give full proofs, but mostly focus on discussion. All 4 of the proofs rely on the self reference lemma.
All four versions require that the axioms be “recursive”. Let’s define the set . Then is recursive if and only if is representable. In other words, we want the set of axioms to be decidable. There is an algorithm we can build which will always halt and tell us exactly when a formula is in our axiom set and when it’s not. Note that the minimal arithmetic has exactly 11 axioms. 11 is not infinity so its axioms are recursive. Peano Arithmetic has an infinite number of axioms when expressed in first order logic since the inductive axiom is technically an axiom schema applying to every formula. Even so, the axiom set of PA is recursive.
Another requirement in all of the version is that the axioms be consistent. By this we mean simply that we can not prove a contradiction from our axioms.
Finally, “extends the minimal arithmetic” is used for 3 of the version. This just means that the axiom set proves at least everything that proves. One could show this, for example, by showing that each of the axioms of are provable from .
A set of axioms which is consistent and recursive can not prove every true sentence in .
Proof: Our first observation here is we do not need to specify “extends the minimal arithmetic”. This is because . The theorems of , by soundness, are then all satisfied by . Therefore, if doesn’t prove every axiom and indeed every theorem of minimal arithmetic, then the unproven axiom or theorem of minimal arithmetic is the true statement which can not be proved.
Now we only need to prove the case when proves everything proves. We first look at the formula which is a formula with exactly 1 free variable. This meets the requirements of the Self Reference Lemma and so we know that there is a sentence such that . Stare at that statement for a moment and appreciate it. It says can prove that says “I am not provable from “. If doubt is still felt about the “I” in that sentence, refer back to the Shakespeare quote. Every step needed to “say I” is proven.
By soundness, we know that which means is true if and only if . By definition this means . So the only possibilities are:
- is true and
- is false and
Make the hypothesis that is false and (you might already see that this is impossible, but we will still complete the argument). Then which means since is a -formula and so the set (notice the typeface) is weakly representable. One more time, we look at and conclude . Since proves everything proves (in this branch of the hypotheticals, read back to “Now we only need…” if you are confused), we arrive at which, combined with your (most recent) hypothesis that includes contradicts the assumption that is consistent.
Therefore, is true but does not prove .
It moves quick, so it might be worthwhile to point out once again the importance that is a -sentence. We established everything to get to the point in the above proof where we were considering the case that and to move past that step we needed the weak representability of .
Note however, that this version of the theorem hasn’t, strictly speaking, proved incompleteness as we defined it. We have proved that is true and . But what if ?. The following versions actually prove incompleteness as we strictly defined it.
A set of axioms which is recursive, extends the minimal arithmetic, and true in is incomplete.
Proof: By the proof of theorem 1, using the exact same , we know and . Now, since if it were so that then by soundness we would get and we hit an immediate contradiction with what we just said. Therefore .
It turns out is a stronger requirement than we actually need. It is much stronger than simply saying is consistent (does not prove ). Indeed, Gödel’s original proof used something called -consistency, a requirement that is “in between” the strength of consistent and . In other words, if is true in then it is -consistent and if is -consistent then it is consistent. But the converses don’t necessarily hold. -consistency means that there is no formula of a single free variable for which and yet for each natural number . Notice the lack of bound on the quantifier over .
A set of axioms which is -consistent, recursive and extends the minimal arithmetic, is incomplete.
Proof: Again, take the same and everything we learned about it from Theorem 1: is true and . We can do this because -consistency is a stronger condition than the bare consistency condition we used in Theorem 1.
Again, assume , then . This is saying that there is a deduction from from A to so:
This looks a lot like our -consistency condition with serving as since it has only one free variable left. We know (by Theorem 1) and by definition of (notice the typeface change), we know that for each natural number , (read: there is no such that is the Gödel number of a deduction of ). Since represents its set (in ), we know that for each natural number , . Since extends , we know and we have hit a clean contradiction with our -consistency condition. I.e. we showed that even though says there exists an such that is the Gödel number of a deduction of , every natural number is not the Gödel number of of a deduction of , violating -consistency. Hence, it must be that
Theorem 3 is Gödel’s original first incompleteness theorem. That version was actually strengthened by Rosser later who realized that by a clever choice of , we could remove the need for -consistency and make do with plain consistency. It is the final version that is quoted today (with credit still often going to Gödel).
A set of axioms which is consistent, recursive, and extends the minimal arithmetic, is incomplete.
Proof: (omitted)
We won’t provide a full proof here. For those curious, see Leary theorem 6.4.5. But we will make a few remarks.
The clever idea, roughly speaking, is to replace the sentence which says “I can not be proven” with a sentence which says something like “if I can be proven in n-steps, there’s a proof of the negation of me in fewer than n steps”. The “fewer than n-steps” is the part that side-steps the need for -consistency. Since the Self Reference Lemma works for arbitrary formulae with a single free variable, we can apply it to construct just like we did for . After you have in hand, you again use proof by contradiction to show that and .
Tarski’s Undefinability of Truth
The set of Gödel numbers of true formulas in is not definable in .
The set that we care about here is the set . As a set of numbers, this set exists, but the reason I put the ”?” above the equals sign is to ask if there is a (first order) formula that exists to make that formula work. This theorem says there’s not.
Proof: Remember the definition of what it means for a formula to define a set. Next, remember our devious idea, let’s just use as our axiom set. Such an axiom set is not recursive but it’s trivially complete. This means that will define a set in if and only if it represents that set in .
Finally, notice that the set of natural numbers is precisely the same set of natural numbers which is the set of all Gödel numbers of formulae provable from . But we know that itself is not representable and hence is not definable.
Gödel’s Second Incompleteness Theorem
Peano Arithmetic is an axiomatic foundation for arithmetic. It is the set of axioms with the addition of an axiom schema:
Which is true for every formula with exactly one free variable. This is an axiom schema because it is actually an infinite number of axioms, one axiom for each formula. It basically says that proof by induction works. This set of axioms, although infinite, is still recursive (though, even Leary didn’t bother to prove it). By applying much the same techniques as in the first incompleteness theorem, though with enough new details that reproducing the proof would still take some care and time so we omitted it, we arrive at Gödel’s second incompleteness theorem.
If Peano Arithmetic is consistent then Peano Arithmetic can not prove its own consistency
Proof: (omitted)
We know already that is recursive and extends so the only condition left is the consistency condition. Basically, we find that the sentence is actually the Gödel sentence, i.e.
is such that
So, if PA is consistent, we will never actually prove its own consistency. What we could do is embed inside and prove ‘s consistency from since is a strictly stronger set of axioms. However, then the question simply gets punted up one level in that we can’t prove the consistency of from within . Gentzen provided a proof of the consistency of using a method of transfinite induction, but that requires extra assumptions as well.
Perhaps we will end this page with a fun little anecdote. In September 1930, in Königsberg, Germany, there was a conference attended by both David Hilbert and Kurt Gödel. During that conference, Hilbert famously stated the quote below. Hilbert was one of the most preeminent mathematicians of his day and in 1900 proposed 23 famous problems, one of which was a general proof of the consistency of arithmetic. When Hilbert gave his famous quote, Gödel had already announced his first incompleteness theorem at a small conference a day earlier. Hilbert probably wasn’t in attendance. At that earlier conference, von Neumann was interested in the incompleteness theorem that Gödel had proved and engaged with Gödel about it. Being the genius that he was, von Neumann, within a few months, proved the second incompleteness theorem himself and excitedly told Gödel about it. Gödel informed Von Neumann that he had already proved the second incompleteness theorem and had already submitted it for publication.
David Hilbert
Wir müssen wissen. Wir werden wissen. (We must know. We will know.)
Footnotes
-
Leary, C. C., and Kristiansen, L. A Friendly Introduction to Mathematical Logic. 2nd ed., Milne Library, SUNY Geneseo, 2015. ISBN 978-1-942341-07-9. ↩︎