Completeness and incompleteness · Definition

Gödel’s incompleteness

logicfoundations

Before you start you need to know

Gödel's incompleteness theorems set limits on what a consistent formal system can prove about arithmetic.

Definition

A consistent system \(\mathcal{S}\) that represents enough arithmetic is incomplete: there is a formula \(\varphi\) that it can neither prove nor refute.

\[\\exists\\varphi\\,(\\mathcal{S}\\nvdash\\varphi\\land\\mathcal{S}\\nvdash\\neg\\varphi)\]

Gödel's incompleteness theorems show that certain consistent formal systems that are expressive enough to represent arithmetic contain statements that the system itself can neither prove nor refute.

The result does not say that all mathematics is useless or that every statement is undecidable. It points to an internal limit: a rich formal system can speak indirectly about its own proofs and find questions it does not settle.

The second incompleteness theorem deepens the phenomenon by relating it to the impossibility, under suitable hypotheses, of proving the system's own consistency within the system.

Think about it

Which condition prevents applying the theorem to any tiny system?

The system must be expressive enough to represent an adequate part of arithmetic.

Exercises 10

  1. Gödel's incompleteness refers to systems that are...
  2. A result of Gödel is that certain systems contain propositions...
  3. Gödel's coding relates formulas to...
  4. To apply the idea of incompleteness, the system must be able to express at least...
  5. Gödel's incompleteness does not claim that...
  6. The incompleteness theorems require systems that can express...
  7. An undecidable sentence is one that...
  8. The first incompleteness theorem states that there is a formula the system cannot...
  9. Select the feature associated with Gödel's result.
  10. The second incompleteness theorem is especially related to...

References

  • Frederic P. Schuller, Lectures on the Geometrical Anatomy of Theoretical Physics · Lecture 1, Introduction / Logic of Propositions and Predicates, YouTube, 2015.