Gödel’s Incompleteness

In 1900, David Hilbert challenged the world to find a complete and consistent set of axioms for all of mathematics. He wanted a “Master Algorithm” that could prove or disprove any statement. In 1931, Kurt Gödel proved this dream was impossible.

1. The First Theorem: Truth vs. Provability

Gödel showed that in any system capable of arithmetic, there are statements that are True but Unprovable.

He did this by creating a “Gödel Sentence” ($G$), which states:

“This statement cannot be proved within this axiomatic system.”

Let’s look at the logical trap:

• If the system can prove $G$, then $G$ is false (because $G$ says it can’t be proved). This means the system proves something false—it is Inconsistent.
• If the system cannot prove $G$, then $G$ is true (because it correctly says it can’t be proved). This means there is a truth the system can’t reach—it is Incomplete.

We prefer Consistency over Completeness. Thus, math is incomplete.

2. A Coding Analogy: The Halting Problem

The Halting Problem in computer science is the direct descendant of Gödel’s work. It proves that you cannot write a program will_halt(code) that correctly predicts if any given piece of code will eventually stop or run forever.

# A simplified demonstration of the 'Turing Trap'
def will_halt(func):
  # Imagine this is a perfect predictor...
  pass

def paradox():
  if will_halt(paradox):
      while True: # If it says I halt, I run forever
          pass
  else:
      return # If it says I run forever, I halt

# The logic of the predictor must fail here.

3. The Second Theorem: Trusting the Foundation

Gödel’s second theorem is even more startling: A system cannot prove its own consistency.

If you use a system (like ZFC) to prove that ZFC has no contradictions, you are essentially “grading your own homework.” To prove ZFC is consistent, you need a stronger system with more axioms. But that stronger system then needs an even stronger one to prove its consistency, and so on, forever.

4. Summary of the Course

We have climbed the ladder of abstraction:

1. Propositional Logic: Computing with Bits.
2. Predicate Logic: Quantifying the World.
3. Boolean Algebra: Designing Circuits.
4. Axioms: The Rules of the Game.
5. Incompleteness: The limits of the Game.

Exercises