The limits of formal proof › When a Proof Has a Number
PhilosophyAll chapters Reading tools Notes & comments
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!