A mathematician claims that by choosing a richer, more carefully axiomatized version of Peano arithmetic, we could make it decidable. What is the fundamental flaw in this claim?
APA is already decidable — the issue is only incompleteness, not decidability
BAdding axioms would make PA inconsistent before it could become decidable
CPA's undecidability follows from the fact that it is expressive enough to encode the halting problem — any consistent extension that still captures basic arithmetic inherits this encoding
DThe claim is correct for certain axiom systems but not for PA specifically
Undecidability of PA is proved by reduction: if PA were decidable, we could translate any halting problem instance into a PA sentence and decide it, solving the halting problem — which is impossible. This reduction works because PA can encode Turing machine computation within its language of addition and multiplication over the natural numbers. Adding axioms does not remove this expressive power as long as the system remains consistent and arithmetically adequate. More axioms might prove more sentences, but they cannot remove the encoding that makes the halting problem translatable.
Question 2 Multiple Choice
A first-order theory T is both complete (for every sentence σ, either T ⊢ σ or T ⊢ ¬σ) and recursively axiomatizable. What follows?
AT is necessarily undecidable, since completeness requires non-standard models
BT is necessarily decidable — we can enumerate all proofs and eventually verify any sentence or its negation
CT cannot be consistent, by Gödel's second incompleteness theorem
DT must be an extension of Peano arithmetic
A complete, recursively axiomatizable theory is decidable: to decide whether T ⊢ σ, enumerate all proofs of T in order. Since T is complete, either σ or ¬σ has a proof, and the enumeration will find it in finite time. This is why undecidable theories are necessarily incomplete — they cannot be both complete and recursive. PA is undecidable precisely because it is incomplete: there exist sentences that PA neither proves nor refutes, corresponding to sentences true in the standard model but unprovable.
Question 3 True / False
Gödel's incompleteness theorems apply only to sufficiently expressive formal systems — for instance, they do not apply to a complete theory like the first-order theory of real closed fields.
TTrue
FFalse
Answer: True
This is correct. Gödel's theorems require that the system be able to encode basic arithmetic (Peano arithmetic or Robinson arithmetic Q is enough). The first-order theory of real closed fields (Tarski's result) is complete and decidable, so incompleteness theorems do not apply to it. The key is expressiveness: real closed fields cannot define the natural numbers within them, so they escape the encoding that drives Gödel's proof. Incompleteness is not a universal fate of all formal systems — only those expressive enough to do arithmetic.
Question 4 True / False
A theory is undecidable if and only if it contains sentences that are true but unprovable from its axioms.
TTrue
FFalse
Answer: False
Undecidability and incompleteness are related but distinct. Undecidability means no algorithm can determine, for every sentence σ, whether T ⊢ σ. Incompleteness means there exist sentences that are true (in the standard/intended model) but unprovable. A theory can be undecidable without having a clear 'standard model' against which truth is measured, and incompleteness describes a gap between provability and truth, not between provability and algorithmic decidability. Gödel's incompleteness theorems do help explain why PA is undecidable, but the concepts themselves are distinct.
Question 5 Short Answer
Why does the expressive power of Peano arithmetic — specifically, its ability to talk about addition and multiplication over natural numbers — imply that PA is undecidable?
Think about your answer, then reveal below.
Model answer: Because within PA's language, you can encode any Turing machine computation as an arithmetic statement. The question 'does this program halt on this input?' translates into a PA sentence about natural numbers. If PA were decidable — if there were an algorithm that, given any sentence, determined whether PA proves it — that algorithm could solve the halting problem. Since the halting problem is provably unsolvable, PA cannot be decidable. PA's undecidability is not a weakness but a consequence of its strength: it is powerful enough to simulate computation, and that power imports the undecidability of the halting problem.