Godel’s Incompl-ten-ss Th–rems

Last time we talked about the Halting Problem, and we came away with the conclusion that it was undecidable.

So what’s the big deal?

Let’s consider a slightly different problem. Consider the sentence “This sentence is false”. This is a slightly different formulation of the liar’s paradox in which the sentence makes claims about its own truth value. In other words, it’s self-referential. Clearly, if “This sentence is false” is true, then the sentence is false, in which case it’s true, etcetera.

This, and similar problems, became the primary focus of Bertrand Russell and Alfred Whitehead’s Principia Mathematica. Russell saw such dilemmas as an abuse of logic. To fix the problem, he suggests that logicians simply agree that sentences may not reference their own truth values. More formally, he sets up the following framework:

Let \alpha_1 be some sentence that is either true or false. Then there exists a sentence \alpha_2 that describes \alpha_1‘s truth value. In other words, if \alpha_1 is the sentence, {The apple is red}, \alpha_2 is the sentence, {The sentence, {The apple is red}, is true}. More generally, if \alpha_i is some sentence, there exists another sentence \alpha_{i+1} that makes a claim about \alpha_i‘s truth value.

So we get the following infinite regression:

{The apple is red}
{The sentence, {The apple is red}, is true}
{The sentence, {The sentence, {The apple is red}, is true}, is true}

…And so on.

Russell and Whitehead took this hierarchical formulation as convention in order to root out self-referencing logical statements. But if you think about it, this is just another reformulation of the Halting Problem. In other words, does there exist a logical framework \gamma that can, in general, tell if any inputted sentence \alpha halts or not? Clearly \alpha_1 does not, but we only know that by inspecting the contents of \alpha_1. Without knowing the contents of a sentence, we can never know if that sentence regresses infinitely or stops at some point.

So here’s where Godel comes in. Godel’s First Incompleteness Statement is essentially a restatement of the undecidability of the Halting Problem. It states that any formal axiomatic system cannot prove its own consistency using its own axioms. (A system is consistent if it contains no contradictions.) An obvious question arises: can formal systems can be proven consistent at all? Or is the universe simply an inconsistent mess?

The answer comes from Godel’s Second Incompleteness Theorem. It states that if a logical system proves it is consistent using its own axioms, it actually turns out to be inconsistent. In other words, to prove a logical framework is consistent, you need a bigger and better framework with bigger and better axioms. That bigger theory needs an even bigger theory to prove its consistency, and so on. At first, this looks similar to Russel’s hierarchy formulation. The key difference is that we aren’t talking about truth or falsity, we’re talking about provability. This theorem turns out to have profound consequences. It means that certain things can be proven to be unprovable in certain axiomatic frameworks. Which means that instead of two possible outcomes for a theory (true or false), we have a third outcome (undecidable).

For mathematicians, this is a godsend, because we can now prove which problems we can never solve with our current axioms, and therefore which ones need new axioms! This saves us a lot of work!

Of course, it also smashes any hope of finding the ideal and universal logical system that Russell, Hilbert, and others were looking for.


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: