The limits of formal proof › The System and Its Proofs

Michael BrenndoerferUpdated May 25, 20262 min read
PhilosophyAll chapters
Reading tools Notes & comments
Notes & comments
Part 8 of 12Logic, Language, and Interpretation
Chapter 96The limits of formal proof › The System and Its Proofs
Reading section 2 of 8 · The System and Its Proofs · 2 minSection 2 of 8 · 2 min

Section 2 of 8 · 2 min read

The limits of formal proof › The System and Its ProofsSection view · Sections in this chapter2 / 8 ↓

A formal theory specifies a language, axioms, and rules of inference. A proof consists of finitely many steps certified by those rules. One can distinguish this from mathematical truth by considering an ordinary example. A theory might let us express a conjecture about primes without providing a proof or a refutation. The conjecture still has a truth condition in the natural numbers. The relation “has a proof in this theory” asks what follows from a specified collection of axioms by the allowed steps.

For Gödel's construction, the axioms and proof rules must be available through effective procedures. This does not require a computer program that decides whether an arbitrary statement has a proof. It requires a mechanical way to check a proposed derivation, with enough information included in its code to verify why each step is licensed. For example, if the axioms are given by an effective enumeration, the proof can include a record of where any axiom it uses appears in that enumeration. A correct record can be checked even when there is no general procedure for recognizing that a formula will never appear.

Two further conditions matter. The theory has to be strong enough to carry out the arithmetical reasoning used in the construction. Its axioms also need to meet a consistency assumption appropriate to the theorem. The familiar modern examples include effectively axiomatized consistent extensions of Peano arithmetic. Gödel gives his original results for a specified system P and classes of additional axioms, as set out in §2 of the original paper. This is why his title names Principia Mathematica and related systems without making the argument depend on the printed pages of Principia.

Consistency and Completeness

A theory is consistent if it does not prove a contradiction. In the classical theories under discussion, this means it cannot prove both a sentence and its negation. It is complete in the sense at issue if, for each sentence in its language, it proves that sentence or proves its negation. The same distinction explains how a consistent theory can fail to decide a sentence.

Comments

Add to the conversation

A question, a correction, or an example from your own work.

No comments yet. Be the first to share your thoughts!

Newsletter

Stay up to date

Get new articles, book updates, and notes on AI and technology.

Unsubscribe at any time. Privacy policy