 Solution

ID: past-exam-of-the-model-theory-and-godel-s-incompleteness-theorems-course-of-the-university-of-oxford/2010/a/3/b/solution

⊥

, implication, and the unary operator

□

; the other logical connectives are abbreviations. Its axioms are all classical tautologies, the distribution scheme

□ (A \to B) \to (□ A \to □ B)

, and the Löb scheme

□ (□ A \to A) \to □ A

. Its rules are modus ponens rule, necessitation rule of theorems, and uniform substitution.

For a single boxed equation

p \leftrightarrow □ C (p)

F = □ C (⊤)

. The identity supplied in the source gives directly

G L ⊢ F \leftrightarrow □ C (F)

. If

p

does not occur, take

F = □ C

instead.

Proceed by induction for a system of

m

p_{1}, \dots, p_{m - 1}

as parameters in the last equation and put

D (p_{1}, \dots, p_{m - 1}) = □ C_{m} (p_{1}, \dots, p_{m - 1}, ⊤) .

The one-variable result proves

D \leftrightarrow □ C_{m} (p_{1}, \dots, p_{m - 1}, D)

. Substitute this

D

for

p_{m}

in the first

m - 1

equations. They are still boxed equations, so induction supplies solutions

F_{1}, \dots, F_{m - 1}

F_{m} = D (F_{1}, \dots, F_{m - 1})

By construction, the first

m - 1

equations hold after this substitution; substituting into the theorem for

D

proves the last. Hence

G L ⊢ F_{i} \leftrightarrow □ C_{i} (F_{1}, \dots, F_{m}) (1 \leq i \leq m) .

The elimination introduces no new parameter letters and removes every unknown letter. This gives a constructive simultaneous boxed fixed-point elimination in GL.

 New to topics? Read the docs here!