Presburger arithmetic (natural numbers with addition only) is decidable. Adding multiplication to obtain full Peano arithmetic makes it undecidable. What is the key reason multiplication crosses this boundary?
AMultiplication produces larger numbers that overflow the decision procedure's memory
BMultiplication allows the theory to encode arbitrary computations, enabling diagonalization arguments that show no algorithm can decide all sentences
CMultiplication is simply too slow to compute within a bounded time for arbitrary sentences
DAdding multiplication violates the quantifier-elimination property that Presburger arithmetic satisfies
Multiplication enables the theory to express arbitrarily complex computational processes — including the very computations that Gödel and Turing used to prove incompleteness and undecidability. Once a theory can encode the natural numbers with multiplication, you can represent Turing machine computations inside the theory, and then diagonalization arguments show that no algorithm can decide all sentences. Presburger arithmetic avoids this by being restricted to linear arithmetic, which cannot define notions like 'x is prime' or simulate arbitrary computations.
Question 2 Multiple Choice
A logician claims she has a decision procedure for a new first-order theory T. What must her procedure guarantee?
AFor every sentence φ, the procedure eventually proves φ or finds a counterexample, but may run forever on some inputs
BFor every sentence φ in T's language, the procedure always halts and correctly outputs whether T entails φ
CThe procedure can decide any sentence provable from T in fewer than one million proof steps
DThe procedure works for all quantifier-free sentences but may loop on quantified formulas
A decision procedure for a theory T is an algorithm that, given any sentence φ in T's language, always halts and outputs 'yes' (T entails φ) or 'no' (T does not entail φ). The key requirements are: (1) it must handle ALL sentences in the language, not just some; (2) it must always halt — it cannot run forever on any input. A procedure that sometimes loops or only handles a fragment of the language does not qualify. This is what separates decidable theories from merely consistent or complete ones.
Question 3 True / False
Tarski proved that the theory of real closed fields (first-order geometry and real algebra with + , ×, <) is decidable — meaning questions like 'does this system of polynomial inequalities have a real solution?' are algorithmically answerable.
TTrue
FFalse
Answer: True
Tarski's decidability result for real closed fields is remarkable: despite involving both addition and multiplication (which makes integer arithmetic undecidable), the theory of the real numbers is decidable. The key is that real multiplication does not enable the same diagonalization tricks as integer multiplication. Tarski proved this via quantifier elimination: every first-order statement about the reals is equivalent to a quantifier-free statement. This implies all of Euclidean geometry is decidable, since geometric statements can be encoded in real algebra.
Question 4 True / False
An undecidable theory has no provable theorems — no individual sentence in the theory can be proved.
TTrue
FFalse
Answer: False
This is a critical misconception. Undecidability means no single algorithm can decide ALL sentences — but many individual sentences are easily proved (or disproved). Peano arithmetic is undecidable, yet mathematicians prove theorems about arithmetic constantly. Undecidability means the algorithmic decision problem has no solution as a whole: there is no uniform procedure that works for every sentence. Individual proofs can still be found; we just cannot automate proof discovery for the entire theory.
Question 5 Short Answer
Why does multiplication create undecidability in arithmetic when addition alone (Presburger arithmetic) does not, and what technique is used to prove decidability for fragments like Presburger?
Think about your answer, then reveal below.
Model answer: Multiplication enables a theory to encode arbitrary computations: Gödel numbering and the representation of Turing machine executions inside arithmetic both rely on multiplication's power to express exponential growth and primality. Once you can simulate computations, undecidability follows by diagonalization — any algorithm claiming to decide all sentences can be given a sentence that asks whether that very algorithm halts, producing a contradiction. Presburger arithmetic lacks this expressive power: it can only express linear constraints and cannot define primality or divisibility in full generality. Decidability of Presburger arithmetic is proved by quantifier elimination: every formula is shown equivalent to a quantifier-free formula, reducing decision to finite checking of linear inequalities and congruences.
The contrast between Presburger and Peano arithmetic illustrates a general principle: decidability is exquisitely sensitive to expressive power. Adding a single operation (multiplication) crosses from decidable to undecidable. Quantifier elimination is the main constructive technique for proving decidability — it shows not just that a decision procedure exists but gives one, even if the resulting algorithm may be extremely slow (doubly exponential for Presburger). Understanding where the decidability boundary lies for a theory is one of the central problems of mathematical logic.