I am going to rip off something Zach Weiner has been doing on his blog where he’s blogging his way through a few different textbooks. This sounds like an awesome way to get a better understanding out of stuff, so I am going to completely steal the idea from him, including the way he formats his titles (while giving him full credit as my inspiration) and blog my way through some of the textbooks I bought in university but never really actually bothered to crack open. Perhaps more fun for me than for you, but we’ll see how it goes.

The textbook I’m going to start off with is called An Introduction to Gödel’s Theorems written by Peter Smith. From the bits of it I’ve actually made use of, it’s a fairly detailed logic text while still being relatively accessible to anyone with a bit of background. Some of the concepts it seems to take for granted are elementary set theory, introductory logic, and basic computability theory. But most everything we’ll need seems to be covered in the text.

# 1 What Gödel’s Theorems say

## 1.1 Basic arithmetic

A lot of what is going to be covered in the text has to do with basic arithmetic, which is to say the natural numbers (0, 1, 2, etc…) and operations on them (addition, multiplication, etc…). Although this will all be flushed out formally in a few chapters, the natural numbers have a specific starting point, 0, each one has a unique successor, and every number falls into this sequence. But this will all be made formal in short order.

Our bigger concern is the notion of a formalized mathematics. In 1920 mathematician David Hilbert put forward a program to axiomatize all of mathematics into a set of finite, simple and non-controversial mathematical statements. The goal was to lift mathematics up by its bootstraps and prove the completeness and consistency of mathematics from these axioms in order to leave zero doubt as to their correctness.

The idea would be that mathematics could be axiomatized into a theory (a theory is simply a collection of axioms) that would be (*negation) complete*, which is to say that for any sentence , either or would be provable in .

Thus, in our case, we are considering how one could build a complete theory of basic arithmetic where we could prove (or disprove) conclusively the truth of any claim that could be expressed arithmetically. This is where Gödel’s Theorems come into play…

## 1.2 Incompleteness

… by basically shitting all over the idea. What mathematician Kurt Gödel was able to do in a 1931 paper was present a way to, given a theory which was sufficiently strong enough to express arithmetic, construct a sentence such that neither nor can be derived in , yet we can show that if is consistent then will be true.

Thus, basic arithmetic in its most striped-down form fails to be negation complete, which puts quite a dampener on Hilbert’s program.

The specifics of how is actually constructed is the subject of most of the text, but the gist of it is this: encodes the sentence “ is unprovable in “. Thus, is true iff can’t prove it. Suppose then that is sound (ie: cannot prove a false sentence). Then if it were to prove it would prove a falsehood, which violates soundness. Thus does not prove and so is true. Thus, is false, which means that can’t prove it either. Again, how is constructed is what we’ll be getting to, but this is the gist of Gödel’s First Theorem.

It should also be noted that there isn’t only one such sentence that renders incomplete. Suppose we decide to augment by adding to it, to create a new theory . We will then be able to construct a new Gödel sentence, which will be true but unprovable in . Since encompasses , will also be unprovable in and we get a construction of an infinite number of unprovable-in- sentences.

Thus, arithmetic is not only incomplete, but indeed *incompletable*.

## 1.3 More incompleteness

This incompletability does not just affect arithmetic. In fact it will also affect any systems which could be used to represent arithmetic. For example, set theory can define the empty set . Then, form the set containing the empty set, followed by the set containing both these sets and so on. We get a sequence of the form:

where we can define 0 as , 1 as the set containing 0, 2 as the set containing 0 and 1, and so on. The successor of is unioned with itself (ie: ), addition is defined as iterated succession, multiplication as iterated addition and all of a sudden you have a theory of arithmetic encompassed in set theory. By Gödel’s First Theorem, then, set theory is also incomplete.

## 1.4 Some implications?

This section deals with some philosophical implications of the First Theorem, but doesn’t delve into enough detail to be worth talking about.

## 1.5 The unprovability of consistency

Any worthwhile arithmetical theory will be able to prove the proposition . Thus, any decent theory that proves will be inconsistent. Furthermore, an inconsistent theory can prove any proposition, including , thus a theory of arithmetic is inconsistent iff proves . Now, we’ve already established that we can encode facts about the provability of propositions in , thus we have a way to encode the idea that can’t prove , which is to say that can express its own consistency. We’ll call the sentence that expresses this

From above, we’ve already seen that a consistent theory can’t prove . Since is itself the sentence that expresses its own unprovability, we can then express (in ) that if is consistent then is unprovable by .

Make sense?

According to the text, it turns out (although we’ve yet to see how) that this sentence turns out to be provable within theories with conditions only slightly stronger than those required for the First Theorem. However must still be unprovable within such theories, and so must also be unprovable otherwise we would be able to get by simple modus ponens.

As such, we have Gödel’s Second Incompleteness Theorem: that nice theories that can express a sufficient amount of arithmetic can’t prove their own consistency.

## 1.6 More implications?

The key point that I took from this section is that since we’ve shown that a theory of arithmetic can’t prove its own completeness or consistency, then it certainly can’t prove the same for a richer theory . This rudely defeats what remains of Hilbert’s Programme, as arithmetic isn’t capable of validating itself, let alone the rest of mathematics.

## 1.7 What’s next?

Obviously this is all pretty roughshod. In chapter 2 we go over a few basic notions that we will need to prove things in more detail. Chapter 3 discusses what is meant by an “axiomatized theory”. Chapter 4 introduces concepts specific to axiomatized theories of arithmetic. Chapters 5 and 6 give us some more direction as we head off towards formally proving… pause for dramatic music… Gödel’s First Incompleteness Theorem!