Which of the following best describes what it means for a function f to be 'representable' in Peano Arithmetic?
Af is computable by a Turing machine
BThere is a formula φ(x,y) such that PA proves φ(n, f(n)) for each n and PA proves f(n) is the unique value satisfying φ(n,y)
Cf can be expressed using only the symbols +, ×, 0, and S
Df is provably total in PA
Representability requires two things: PA must prove each specific instance φ(n, f(n)) (the formula is satisfied by the correct value), and PA must prove uniqueness — that f(n) is the *only* value satisfying φ(n, y). The uniqueness condition is critical; without it, the formula wouldn't pin down f as a function. Mere Turing computability or syntactic expressibility is not sufficient for representability.
Question 2 True / False
The induction axiom of Peano Arithmetic is a single axiom.
TTrue
FFalse
Answer: False
The induction 'axiom' is actually an axiom *schema* — an infinite family of axioms, one for each formula φ in the language of arithmetic. For each formula φ(n), PA includes: (φ(0) ∧ ∀n(φ(n) → φ(n+1))) → ∀n φ(n). Because there are infinitely many formulas, there are infinitely many induction axioms. This is why PA cannot be finitely axiomatized.
Question 3 Short Answer
Why did Gödel need to develop Gödel numbering, and what does it accomplish?
Think about your answer, then reveal below.
Model answer: Gödel numbering assigns a unique natural number to every formula and proof in PA's language, translating syntactic properties of proofs into arithmetic properties of numbers. This allows PA to express statements about its own provability as arithmetic formulas.
The incompleteness proof requires constructing a sentence that says 'I am not provable in PA.' For PA to 'talk about' provability, statements about proofs — a syntactic notion — must become arithmetic statements. Gödel numbering provides this translation. Once proofs are numbers, 'x is a proof of formula y' becomes a primitive recursive relation, which is representable in PA by the representability theorem.