A graph theory lemma, called Kőnig’s lemma, strengthens the weakest of the “Big Five” subsystems of this theory, whose proof-theoretic strengths are studied in reverse mathematics. For 10 points each:
[10h] Name this theory of the natural numbers whose standard axiomatization, Z2, contains the axioms of Peano arithmetic, but adds an axiom schema of comprehension and has a single axiom of induction rather than an axiom schema.
ANSWER: second-order arithmetic
[10e] The base theory in reverse mathematics, RCA0, restricts second-order arithmetic to sets with this property. Sets have this property if a Turing machine can conclusively determine whether a number does or does not belong to it.
ANSWER: computable [or decidable or recursive]
[10m] RCA0 with Kőnig’s lemma is strong enough to prove this theorem of mathematical logic, which states that any statement that is true in all models of a first-order theory is also provable.
ANSWER: Gödel’s completeness theorem [prompt on Gödel’s theorem; reject “Gödel’s incompleteness theorem”]
<VD, Other Science>