The limits of formal proof › Arithmetizing Formulas and 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 › Arithmetizing Formulas and Proofs
Reading section 3 of 8 · Arithmetizing Formulas and Proofs · 2 minSection 3 of 8 · 2 min

Section 3 of 8 · 2 min read

The limits of formal proof › Arithmetizing Formulas and ProofsSection view · Sections in this chapter3 / 8 ↓

Gödel assigns numbers to primitive signs and codes sequences using powers of successive primes. As a small illustration, assign the fictional signs A and B the codes 1 and 2. Using the same general style of encoding, the sequence A, B, A could receive the number 2¹ × 3² × 5¹. The unique factorization of the number lets us recover the sequence. Gödel's actual coding maps a richer formal language and, in further steps, whole sequences of formulas. The principle is that a structural test on a written expression can become a test on natural numbers.

One relation concerns substitution. Given the code of a formula with a free variable and the code needed to identify that variable, we can compute the code of the formula obtained by putting a numeral in its place. Another relation concerns proofs. It holds of two numbers p and q when p codes a correct proof whose last formula has code q. Gödel analyzes the requisite computations in §2, before Proposition VI. This detail matters because a suggestive resemblance to arithmetic would be too weak. The needed operations have to be available in sufficiently definite arithmetical form.

A proof checker handles a proposed code p and a proposed conclusion q. To say that q has a proof is then to say that some p passes the test. Arithmetic can express this existential assertion without providing a procedure to settle it in all cases. Trying candidate proof codes in an enumeration will eventually find a proof if there is one. It will run indefinitely if there is none. This difference between verifying evidence and deciding whether evidence exists helps explain why the encoding does not by itself make the theory complete.

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