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.

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

**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.- If we assume G is provable we can create a contradition (we just showed this above)
- 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.
- Restated: G is unprovable in the consistent formal system
- Therefore G must be true (if 4 is true then G must be true; go read 'G' again)

- 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)

## No comments:

Post a Comment