Past exam of the Gödel's incompleteness theorems course of the University of Oxford / 2011 / 3

The Gödel-Löb logic $\mathrm{GL}$ uses propositional variables, $\perp$, implication, and a unary modal operator $\square$. Other Boolean connectives are abbreviations; for example $\neg A$ means $A\to \perp$ and $\top$ means $\perp \to \perp$.

Its axioms are all classical propositional tautologies and the two schemesIts rules are the modus ponens rule and the necessitation rule, $\mathrm{GL}⊢A\Rightarrow \mathrm{GL}⊢\square A$. Uniform propositional substitution is allowed, or equivalently built into the axiom schemes. necessitation rule applies to theorems; a temporary assumption cannot simply be boxed. In provability logic, $\square A$ is read as the formal assertion that $A$ is provable.

Induct on a derivation in Gödel-Löb logic. Propositional axiom instances translate to theorems of Peano arithmetic. The image of $\perp$ is a refutable sentence, so it behaves as falsity in those translated propositional arguments.

The translation of axiom $\mathrm{K}$ is the distribution clause of the Hilbert-Bernays-Löb derivability conditions. The translation of axiom $\mathrm{L}$ isthe Internal form of Löb's theorem, whose derivation was given above and applies to the stipulated arithmetical provability predicate for Peano arithmetic. Thus every axiom has a provable translation.

The modus ponens rule is preserved because the interpretation commutes with implication. The necessitation rule is preserved by the first derivability condition: if $\mathrm{PA}⊢{\mathcal{I}}_i(A)$, thenHere the equality denotes the definition of the translated formula, not an arithmetic equality of truth values. A propositional substitution merely changes the arithmetic sentences assigned to the variables. The induction proves the Arithmetical soundness of GL:

Take $Y(p)=p\to q$ and put $\top =(\perp \to \perp )$, $H=Y(\top )$ and $F_0=Y(\square H)=\square H\to q$. The first supplied substitution identity readsUse the supplied replacement of equivalents in the context $D(p)=p\to q$. It givesBut $H=(\top \to q)$ is equivalent to $q$. Replacement under a box gives $\square H\leftrightarrow \square q$, so $F_0$ is equivalent toReplacing equivalents once more transfers the fixed-point equation to $F$, proving $\mathrm{GL}⊢F\leftrightarrow (\square F\to q)$.

A direct check of this GL fixed point for a provability implication is useful: the Löb axiom gives $\square F\to \square q$, and necessitating the tautology $q\to F$ gives $\square q\to \square F$ by $\mathrm{K}$. Thus $\square F\leftrightarrow \square q$, and replacing the antecedent in $\square F\to q$ recovers $F$.

Use the preceding fixed point with $q=\perp$. If the chosen arithmetic interpretation sends $\perp$ to a PA-refutable sentence $Z$, it gives the arithmetic sentenceThis follows from Arithmetical soundness of GL. Since Peano arithmetic proves $\neg Z$, the two implications are equivalent to negated provability:Thus $C$ expresses the formal consistency statement for Peano arithmetic and is also a negative provability fixed point, like its Gödel sentence $G$.

Apply the supplied modal uniqueness formula to the context with a modalized occurrence $X(p)=(\square p\to \perp )$, with two fresh variables interpreted as $G$ and $C$. A modalized occurrence means that each indicated variable occurrence lies inside a box. Peano arithmetic proves both arithmetic fixed-point equations. The first derivability condition boxes those equations, so the translated uniqueness formula givesOne must not infer $G\leftrightarrow C$ by reflection. Instead, distribution and the provability of the two propositional projections give $\mathrm{PA}⊢BG\leftrightarrow BC$. Negating and using the two fixed-point equations now yieldsThis proves the Equivalence of a Gödel sentence and a consistency statement using the required modal soundness, fixed point and uniqueness results.