Gödel’s Incompleteness Theorems

In the last couple of posts, we’ve talked about what math is (a search for what must be) and where the foundational axioms and definitions come from.

Mathematics tries to prove that statements are true or false based on these axioms and definitions, but sometimes the axioms prove insufficient. Sometimes the axioms lead to paradoxes, like Russell’s paradox, and so a new set of axioms are needed. Sometimes the axioms simply aren’t enough, and so a new axiom might be needed to prove a desired result.

But in both cases, the paradoxes and inability to prove a result are the result of picking the wrong axioms.

1

Right?

2

Unfortunately, it’s not true!

3

Gödel’s incompleteness theorems show that pretty much any logical system either has contradictions, or statements that cannot be proven!

The questions Gödel was trying to answer were, “Can I prove that math is consistent?” and, “If I have a true statement, can I prove that it’s true?”1

3

Gödel’s first step in this project was in his PhD thesis. That result seems to imply that you can prove any true statement. This is called Gödel’s completeness theorem.

For a particular set of axioms, there are different “models” implementing those axioms. A model is an example of something that satisfies those axioms.

As a non-mathematical example of a model, let’s say the axioms that define being a “car” are that you have at least 3 wheels, along with at least one engine that rotates at least one of the wheels. A standard car clearly follows those axioms, and is therefore a model for the “car axioms.” A bus would also be a model for the car axioms.

Of course, there are models that are very non-standard…

notcar

Mathematical axioms work the same way. There are axioms for the natural numbers, and their addition and multiplication, called “Peano arithmetic” (pay-AH-no). The normal natural numbers, \{1, 2, 3, \cdots\} follow these axioms, so are the standard model for them. But there are non-standard models that still follow the Peano arithmetic axioms.

Each model is a bit different. There may be some statements (theorems) that are true in some of the models, but not true in another model.

Even if a statement is true, though, you want to be able to prove it true, using only the axioms that your model satisfies.2

Gödel’s completeness theorem answers the question, “Using the axioms, is it always possible to prove true statements are true?”

His completeness theorem says you can prove a statement is true using your chosen axioms if and only if that statement is true in all possible models of those axioms.3

This result seems very promising for mathematics.

5

Unfortunately, math is not that simple.

6.png

Two years after Gödel published his completeness theorem, he published his incompleteness theorems.

These theorems relate two concepts: consistency and provability. A logical system (a set of axioms) is consistent if there aren’t any contradictions. In other words, you can’t prove a statement both true and false.

Inside of any logical system, there are lots of statements, i.e., things you can say. I could say something like “All prime numbers are smaller than a billion.” It’s a false statement, but I can say it.

20

But just because I can say a statement doesn’t mean that I can prove it true or false. Most of the time, the statement is just very difficult to prove, and so you don’t know how to do it. But it’s also possible to have statements which are impossible to prove either true or false. We’ll call these kind of statements unprovable. Any logical system (set of axioms) with unprovable statements is called incomplete.

Gödel’s first incompleteness theorem says that if you have a consistent logical system (i.e., a set of axioms with no contradictions) in which you can do a certain amount of arithmetic4, then there are statements in that system which are unprovable using just that system’s axioms.

In other words, as long as your logical system is complicated enough to include addition and multiplication, then your logical system is incomplete. There are things you can’t prove true or false!

7

Gödel’s second incompleteness theorem gives a specific example of such an unprovable statement. And the example is quite a doozy.

The theorem says that inside of a similar consistent logical system (one without contradictions), the consistency of the system itself is unprovable!5

You can’t prove that math does not have contradictions!

8

In the next post, I plan on giving an outline of the proof of these theorems, but for this post, let’s talk about their fascinating consequences.

Remember what I said I thought math is?

Math is the quest to decide what must be. But Gödel’s incompleteness theorems put fundamental limits on that quest!

David Hilbert, among others, felt that any true statement should be provable, and that math should be provably consistent.

9

In 1900, he gave a famous list of open problems in mathematics, the most important ones for the next century. His second problem was, “Prove the axioms of arithmetic are consistent.”6

Gödel’s theorems show that Hilbert’s hope was exactly… wrong.7

10

As long as your mathematics is complicated enough to include the natural numbers (which, I think we can agree, is not a particularly high bar), then it must have statements which cannot be proven true or false. They are unprovable.

Of course, to “fix” this you could try to add that statement as an axiom.8

Then, since the statement is an axiom, it is trivially provable. (The proof is: “This statement is an axiom. Thus it is true.”)

11

Yeah, it’s kind of cheating. But the problem is, you can’t even cheat enough to win!

Zazu

See, your new mathematical system, with your shiny new axiom, is still a mathematical system complicated enough to include the natural numbers. Gödel’s theorem still applies, and shows that there is some new statement that is unprovable! It’s worse than trying to kill a hydra.

trippy

Looking at the proof, the vaguest idea of an unprovable statment is “This statement is unprovable,” which seems… silly, and not worth your time. You might hope that all unprovable statements are like that: unprovable, but totally uninteresting.

13

Unfortunately, mathematicians have found statements of the kind that you might hope to prove, that are unprovable in standard mathematical systems. For instance, it is impossible to prove or disprove that the real numbers have the smallest uncountable cardinality9 inside of standard set theory. There are lists of other such important, but unprovable, statements.

So, in pretty much any mathematical system, there are things you’ll want to prove, but can’t.

14.png

And that’s just the first incompleteness theorem.

The second incompleteness theorem says that, within your mathematical system, you cannot prove that you can’t have contradictions.

If you’ve proven the statement “there are no contradictions in the system”, your system cannot be consistent because the second incompleteness theorem proved that since your system is complicated enough to include arithmetic, there must be contradictions in the system. Which means–since you’ve proven there are and are not contradictions in the system, your system is inconsistent.

Thus, if you can prove there are no contradictions, then the second theorem says that your system does have contradictions!

15.png

Now, using a more powerful system (one with more axioms), you can often prove the consistency (lack of contradictions) of a less powerful system (one with fewer axioms). For instance, Peano arithmetic, which covers essentially the natural numbers and addition and multiplication, can be proven to be consistent with standard (ZFC) set theory, a more powerful system. But Peano arithmetic can’t prove itself consistent.

This leads to a philosophical problem: How do we know standard set theory is consistent? Sure, there are even stronger systems that can prove it’s consistent, but then we have to ask about their consistency. If we keep on adding axioms to prove consistency, have we really proven consistency? We may have inadvertently added contradictions as well!

16

One last weird thing.

Gödel’s completeness theorem implies that a statement is provable using a set of axioms if and only if that statement is true, for every model of the set of axioms. That means that for any unprovable statement, there has to be a model of those axioms for which the statement is false.

17

But, if the consistency of the set of axioms is unprovable, that means there has to be a model of your axioms where the consistency statement is false.

Which hurts my head to think about.

18

Anyway, next time I’ll explain the basic idea of the proofs of these results. It should be fun!

19


  1.  Man, these sound kind of weird, even to me. I mean, the statement is true, right? So isn’t it obvious? 
  2. A statement can be true, even if you can’t prove it as such. (Usually it just means you’re not clever enough.) 
  3.  This formulation is not Gödel’s original formulation, but it is very closely related. More technically, the axioms should form a “first-order theory” with a “well-orderable language,” but there’s not need to go into details here. We’ll leave these for you to explore on your own
  4.  In particular, it needs to include Peano arithmetic, which includes addition and multiplication of the natural (counting) numbers. 
  5.  Technically, there is a particular statement of the consistency of the system that is unprovable. There can be several inequivalent such statements. 
  6.  His first problem was the continuum hypothesis (“Are the real numbers the smallest uncountable infinity?”) which has always confused me. Shouldn’t the consistency of mathematics go first? Kinda fundamental, right? Bah. 
  7.  To be fair, there are mathematical logicians that disagree with me, but I think most mathematicians agree with me. 
  8.  You should worry that the logical system is still consistent with that statement as an axiom. However, since you can’t prove it true or false, it has to be consistent if you add the unprovable statement. 
  9.  We talked about uncountable sets and cardinality in earlier posts. 
Advertisements

1 thought on “Gödel’s Incompleteness Theorems”

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