The limits of formal proof › When a Proof Has a Number

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 › When a Proof Has a Number
Reading section 1 of 8 · When a Proof Has a Number · 2 minSection 1 of 8 · 2 min

Section 1 of 8 · 2 min read

The limits of formal proof › When a Proof Has a NumberSection view · Sections in this chapter1 / 8 ↓

Imagine two people reading the same purported proof. The first sees a list of formulas and checks whether each line is an axiom or follows from earlier lines. The second has a numerical code for the same list. Given that code, the second reader can perform essentially the same checks through arithmetic on the numbers. Once the encoding has been fixed, “this list is a proof” and “this number satisfies a certain arithmetical relation” can express the same test.

Kurt Gödel's 1931 paper on undecidable propositions turns that observation against a formal system's claim to completeness. If arithmetic can express a test for proof, a sufficiently strong theory of arithmetic can formulate claims about its own proofs. Gödel shows how to construct a sentence that speaks about its own status under that test. He also uses the relationship between proof and arithmetic to examine whether the same theory can prove that its rules never yield a contradiction.

These are two different results. The first concerns the existence of sentences left undecided by a theory. The second concerns a particular statement expressing the theory's consistency. Both are conditional theorems about formal systems. Keeping the conditions in view helps us see why the proofs work.

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