godel part 4 - they blow up into funny shapes?

Godel links: Part 1 | Part 2 | Part 3 | Part 4 | Part 5 | Part 6 | Part 7

We're going to move slowly now. Things start to get weird quickly. Let's quickly recap. Formal systems were developed to create mathematics (ways to create proofs) and to get around the wobbly starting points of axiomatic statements. We are trying to create a stable foundation to build mathematics without conjuring up statements out of thin air and assuming they must be true. Once we know we can create a formal system for, say arithmetic, we need to show it is complete (can create proofs of any arithmetic we want to prove or disprove) and it is non contradictory. Once that is done we have a system to answer all questions about arithmetic.

Godel's theorem shows that you cannot do both of these things - only one. You can make it consistent but not complete. Or you can make it complete but it will have contradictions. This is a big blow to formal systems. Hilbert felt sure this could be done. Everyone else did too. But it can't. Formal systems have a significant and deadly flaw. It seemingly puts all of mathematics on shaky footing. It's something we'll address later because the implications are greatly misunderstood.

For now...how did Godel show you can't do this with formal systems? Let's talk about his strategy first. Let's start at the end and look at his theorem.

We will call his theorem G. What does G say? Here is G using the English language. And I'm going to put "G:" in front of it to again denote it is the name of what follows.

G: "G is unprovable in the formal system"

Notice G here is clearly talking about itself. Now let's look at the 'negation' of G (call it G'). Here is G' using the English language.

G': "G is provable in the formal system"

Assume G is provable. By definition G' must be true (read aloud what G' says above). If G' is true then G must be false. Because if a negation is true/false then the non-negation must be false/true. So if we start with our assumption again we've shown,

Assume G is provable → the statement G, above, is false

Now think about what we've done.

1. Above we just showed that if G is provable, it is false.
   
2. Clearly, if something is provable, it is true by definition.

Something is terribly, terribly amiss - if G is provable, it is both true and false. What in God's name is going on? We have a contradiction on our hands. What a mess. Not really. Godel uses this contradiction as a means to his end. Okay here comes the meat of what Godel showed. Ready? Go slowly.

1. Assume our formal system which we used to create G is non-contradictory (consistent). This is a fixed assumption. We won't let go of that truth in this example. I'll say it again - The formal system is consistent.
   
2. If we assume G is provable we can create a contradition (we just showed this above)
3. Therefore we cannot assume G is provable in a non-contradictory formal system (clearly, if the formal system is not contradictory our assumption (that G is provable) must be incorrect.
4. Restated: G is unprovable in the consistent formal system
   
5. Therefore G must be true (if 4 is true then G must be true; go read 'G' again)
   

Look at 4 and 5 again together. G is true but it is not provable in our non-contradictory formal system. This is exactly what our make-believe mathematician said couldn't be true in my previous post. You can use the same type of argument to show the opposite. Namely G is provable but the system is contradictory. Again let's summarize.

• If the system is consistent, it is not complete (we can't prove G but it is a true statement)
• If the system is complete, it is not consistent (we can prove G but it creates a contradiction)
  

This is an astounding result. How Godel was able to think this through is mind boggling. But to actually develop G within the formal system is even beyond that. That's where we're heading next...