Gödel! #1 An Introduction to Gödel’s Theorems 1.0

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 T (a theory is simply a collection of axioms) that would be (negation) complete, which is to say that for any sentence \phi, either \phi or \neg\phi would be provable in T.

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 T which was sufficiently strong enough to express arithmetic, construct a sentence \textbf G_T such that neither \textbf G_T nor \neg\textbf G_T can be derived in T, yet we can show that if T is consistent then \textbf G_T 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 \textbf G_T is actually constructed is the subject of most of the text, but the gist of it is this: \textbf G_T encodes the sentence “\textbf G_T is unprovable in T“. Thus, \textbf G_T is true iff T can’t prove it. Suppose then that T is sound (ie: cannot prove a false sentence). Then if it were to prove \textbf G_T it would prove a falsehood, which violates soundness. Thus T does not prove \textbf G_T and so \textbf G_T is true. Thus, \neg\textbf G_T is false, which means that T can’t prove it either. Again, how \textbf G_T 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 T incomplete. Suppose we decide to augment T by adding \textbf G_T to it, to create a new theory U=T+\textbf G_T. We will then be able to construct a new Gödel sentence, \textbf G_U which will be true but unprovable in U. Since U encompasses T, \textbf G_U will also be unprovable in T and we get a construction of an infinite number of unprovable-in-T 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 \emptyset. Then, form the set \{\emptyset\} containing the empty set, followed by the set containing both these sets \{\emptyset,\{\emptyset\}\} and so on. We get a sequence of the form:

\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\},\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}

where we can define 0 as \emptyset, 1 as the set containing 0, 2 as the set containing 0 and 1, and so on. The successor of n is n unioned with itself (ie: n\cup\{n\}), 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 0\neq1. Thus, any decent theory that proves 0=1 will be inconsistent. Furthermore, an inconsistent theory can prove any proposition, including 0=1, thus a theory of arithmetic T is inconsistent iff T proves 0=1. Now, we’ve already established that we can encode facts about the provability of propositions in T, thus we have a way to encode the idea that T can’t prove 0=1, which is to say that T can express its own consistency. We’ll call the sentence that expresses this \textbf{Con}_T

From above, we’ve already seen that a consistent theory T can’t prove \textbf G_T. Since \textbf G_T is itself the sentence that expresses its own unprovability, we can then express (in T) that if T is consistent then \textbf G_T is unprovable by \textbf{Con}_T\rightarrow\textbf G_T.

Make sense?

According to the text, it turns out (although we’ve yet to see how) that this sentence \textbf{Con}_T\rightarrow\textbf G_T turns out to be provable within theories with conditions only slightly stronger than those required for the First Theorem. However \textbf G_T must still be unprovable within such theories, and so \textbf{Con}_T must also be unprovable otherwise we would be able to get \textbf G_T 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 T can’t prove its own completeness or consistency, then it certainly can’t prove the same for a richer theory T^+. 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!

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: