Past exam of the model theory and Gödel's incompleteness theorems course of the University of Oxford / 2010 / A / 1

Write $\square A$ for the arithmetical provability predicate applied to the Gödel number of $A$. Use the Hilbert-Bernays-Löb derivability conditions that belong to the course meaning of a provability predicate: external necessitation rule, internal modus ponens rule, and positive introspection. No incompleteness theorem is needed here.

If $S⊢G$, necessitation rule gives $S⊢\square G$. The displayed Gödel sentence equivalence also gives $S⊢\neg \square G$. These two theorems contradict the assumption that $S$ is a consistent first-order theory. ThereforeFor this part alone, the external necessitation rule condition suffices; the stronger internal conditions are used in the next part.

Again abbreviate provability by $\square$. The Gödel sentence equivalence gives $S⊢G\to \neg \square G$. Internalizing this implication using the first two Hilbert-Bernays-Löb derivability conditions givesPositive introspection also gives $S⊢\square G\to \square \square G$. Internal modus ponens rule combines proofs of a sentence and its negation into a proof of a contradiction; a contradiction implies any sentence. ConsequentlyThese are syntactic manipulations of provability, not an appeal to soundness. If $S⊢\neg \square \neg G$, taking the contrapositive of the last implication gives $S⊢\neg \square G$, and the diagonal equivalence gives $S⊢G$. Part (a) rules that out for a consistent theory. Hence

An arithmetic theory is one-consistent if there is no bounded arithmetic formula $\delta (x)$ for which it proves $\exists x\delta (x)$ and also proves $\neg \delta (\overline{n})$ for every standard natural number $n$. A finite tuple of existential witnesses can be coded by one natural number. The associated Sigma-1 soundness property says that every ${\Sigma }_1$ sentence it proves is true in the standard natural numbers.

Suppose first that the theory is one-consistent, but proves a false ${\Sigma }_1$ sentence $\exists x\delta (x)$. For every standard $n$, $\neg \delta (\overline{n})$ is then a true bounded sentence. Bounded completeness makes each such sentence a theorem, violating one-consistency.

Conversely suppose the theory is ${\Sigma }_1$-sound. If it proved both the existential sentence and every negated standard instance, soundness would supply an actual witness $n$. Its positive instance $\delta (\overline{n})$ is a true bounded sentence and hence provable. Together with the assumed negative instance this would make the theory inconsistent; an inconsistent theory proves a false ${\Sigma }_1$ sentence, contrary to soundness. Thusunder the stated bounded-completeness assumption. In particular either condition implies that the theory is a consistent first-order theory.

By part (c), one-consistency gives Sigma-1 soundness and hence ordinary consistency. First, $S$ cannot prove $\neg G$: if it did, the diagonal equivalence would give $S⊢\square G$. This is a ${\Sigma }_1$ sentence, so soundness would make it true. The stipulated standard interpretation of the arithmetical provability predicate would then supply an actual proof of $G$, contradicting consistency.

Now suppose $S⊢\square \neg G$. This too is a ${\Sigma }_1$ theorem. Soundness and the standard correctness of the predicate would imply that there is an actual $S$-proof of $\neg G$, which was just excluded. ThereforeThe two applications of soundness concern the provability assertions, not the truth of arbitrary arithmetic sentences.