Gödel’s Incompleteness Theorem

First Incompleteness Theorem: Given any system of logic that is consistent (can’t prove a contradiction)  and computable (the application of the rules is just mechanical), there are going to be true statements about integers that can’t be proved or disproved within that system.

It doesn’t mean these statements are unprovable, but if you want to prove them, you need a more powerful system, and then there will be statements within that system that can’t be proved, and so on.

Second Incompleteness Theorem: No consistent, computable system of logic can prove its own consistency.

Gödel’s original proof only worked for a subset of consistent and computable systems of logic, including those that are sound and computable. Here ‘sound’ means ‘unable to prove a falsehood’.  Rosser extended Gödel ‘s theorem to all consistent and computable systems, including those that are no sound.

Gödel started out with the paradox of the liar: “This sentence is not true.” It can’t be either true or false!

But how to define ‘true’ mathematically!?

Gödel ‘s solution was to replace “This sentence is not true” with a subtly different sentence: “This sentence is not provable”.

Advertisements

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