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”.

Leave a comment