Provability logic - LessWrong

The Gödel -Löb system of provability logic, or for short, is a normal system of provability logic which captures important notions about provability predicates. It can be regarded as a formalism which allows to decide whether certain sentences in which a provability predicate appears are in fact theorems of Peano Arithmetic.

$G L$ has two rules of inference:

Modus ponens allows to infer $B$ from $A \to B$ and $A$ .

Necessitation says that if $G L ⊢ A$ then $G L ⊢ □ A$ .

The axioms of $G L$ are as follows:

$G L ⊢ □ (A \to B) \to (□ A \to □ B)$ (Distibutive axioms)

$G L ⊢ □ (□ A \to A) \to □ A$ (Gödel-Löb axioms)

Propositional tautologies are axioms of $G L$ .

Exercise: Show using the rules of $G L$ that $□ ⊥ \leftrightarrow □ ⋄ p$ . ^[1]

Show solution

Those problems are best solved by working backwards.

We want to show that $G L ⊢ □ ⊥ \leftrightarrow □ ⋄ p$ .

What can lead us to that? Well, we know that because of normality, this can be deduced from $G L ⊢ □ (⊥ \leftrightarrow ⋄ p)$ .

Similarly, that can be derived from necessitation of $G L ⊢ ⊥ \leftrightarrow ⋄ p$ .

The propositional calculus shows that $G L ⊢ ⊥ \to ⋄ p$ is a tautology, so we can prove by following the steps backward that $G L ⊢ □ ⊥ \to □ ⋄ p$ .

Now we have to prove that $G L ⊢ □ ⋄ p \to □ ⊥$ and we are done.

For that we are going to go forward from the tautology $G L ⊢ ⊥ \to \neg p$ .

By normality, $G L ⊢ □ ⊥ \to □ \neg p$ .

Contraposing, $G l ⊢ \neg □ \neg p \to \neg □ ⊥$ . By necessitation and normality, $G l ⊢ □ \neg □ \neg p \to □ \neg □ ⊥$ .

But $□ \neg □ ⊥$ is equivalent to $□ [□ ⊥ \to ⊥]$ , and it is an axiom that $G L ⊢ □ [□ ⊥ \to ⊥] \to □ ⊥$ , so by modus ponens, $G l ⊢ □ \neg □ \neg p \to □ ⊥$ , and since $⋄ p = \neg □ \neg p$ we are done.

It is fairly easy to see that GL is consistent. If we interpret $□$ as the verum operator which is always true, we realize that every theorem of $G L$ is assigned a value of true according to this interpretation and the usual rules of propositional calculus ^[2]. However, there are well formed modal sentences such as $\neg □ ⊥$ such that the assigned value is false, and thus they cannot be theorems of $G L$ .

Semantics

However simple the deduction procedures of $G L$ are, they are bothersome to use in order to find proofs. Thankfully, an alternative interpretation in terms of Kripke models has been developed that allows to decide far more conveniently whether a modal sentence is a theorem of $G L$ .

$G L$ is adequate for finite, transitive and irreflexive Kripke models. That is, a sentence $A$ is a theorem of $G L$ if and only if $A$ is valid in every finite, transitive and irreflexive model%^[3]%. Check out the page on Kripke models if you do not know how to construct Kripke models or decide if a sentence is valid in it.

An important notion in this kind of models is that of rank. The rank $ρ$ of a world $w$ from which no world is visible is $ρ (w) = 0$ . The rank of any other world is defined as the maximum among the ranks of its successors, plus one. In other words, the rank of a world is the length of the greatest "chain of worlds" in the model such that $w$ can view the first slate of the chain.

Since models are irreflexive and finite, the rank is a well-defined notion: no infinite chain of worlds is ever possible.

Exercise: Show that the Gödel-Löb axioms are valid in every finite, transitive and irreflexive Kripke model.

Show solution

Suppose there is a finite, transitive and irreflexive Kripke model in which an sentence of the form $□ [□ A \to A] \to □ A$ is not valid.

Let $w$ be the lowest rank world in the model such that $w ⊭ □ [□ A \to A] \to □ A$ . Then we have that $w ⊨ □ [□ A \to A]$ but $w ⊭ □ A$ .

Therefore, there exists $x$ such that $w R x$ , also $x ⊨ \neg A$ and $x ⊨ □ A \to A$ . But then $x ⊨ \neg □ A$ .

Since $x$ has lower rank than $w$ , we also have that $x ⊨ □ [□ A \to A] \to □ A$ . Combining those two last facts we get that $x ⊭ □ [□ A \to A]$ , so there is $y$ such that $x R y$ and $y ⊭ □ A \to A$ .

But by transitivity $w R y$ , contradicting that $w ⊨ □ [□ A \to A]$ . So the supposition was false, and the proof is done.

The Kripke model formulation specially simplifies reasoning in cases in which no sentence letters appear. A polynomial time algorithm can be written for deciding theoremhood this case.

Furthermore, $G L$ is decidable. However, it is $P S P A C E$ -complete ^[4].

Arithmetical adequacy

You can translate sentences of modal logic to sentences of arithmetic using realizations.

A realization $*$ is a function such that $A \to B * = A * \to B *$ , $(□ A) * = □_{P A} (A *)$ , and $p * = S_{p}$ for every sentence letter $p$ , where each $S_{p}$ is an arbitrary well formed closed sentence of arithmetic.

Solovay's adequacy theorem for GL states that a modal sentence $A$ is a theorem of $G L$ iff $P A$ proves $A *$ for every realization $*$ .

Thus we can use $G L$ to reason about arithmetic and viceversa.

Notice that $G L$ is decidable while arithmetic is not. This is explained by the fact that $G L$ only deals with a specific subset of logical sentences, in which quantification plays a restricted role. In fact, quantified provability logic is undecidable.

Another remark is that while knowing that $G L ⊬ A$ implies that there is a realization such that $P A ⊬ A *$ , we do not know whether a specific realization of A is a theorem or not. A related result, the uniform completeness theorem for $G L$ , proves that there exists a specific realization $#$ such that $P A ⊬ A^{#}$ if $G L ⊬ A$ , which works for every $A$ .

Fixed points

One of the most important results in $G L$ is the existence of fixed points of sentences of the form $p \leftrightarrow ϕ (p)$ . Concretely, the fixed point theorem says that for every sentence $ϕ (p)$ modalized in $p$ ^[5] there exists $H$ in which $p$ does not appear such that $G L ⊢ □ [p \leftrightarrow ϕ (p)] \leftrightarrow □ (p \leftrightarrow h)$ . Furthermore, there are constructive proofs which allow to build such an $H$ .

In arithmetic, there are plenty of interesting self referential sentences such as the Gödel sentence for which the fixed point theorem is applicable and gives us insights about their meaning.

For example, the modalization of the Gödel sentence is something of the form $p \leftrightarrow \neg □ p$ . The procedure for finding fixed points tells us that $G L ⊢ □ (p \leftrightarrow \neg □ p) \to □ (p \leftrightarrow \neg □ ⊥$ . Thus by arithmetical adequacy, and since everything $P A$ proves is true we can conclude that the Gödel sentence is equivalent to the consistency of arithmetic.

^{^︎}
~D\diamond p~D is short for $\neg □ \neg p$ .
^{^︎}
proof
^{^︎}
proof
^{^︎}
proof
^{^︎}
that is, every $p$ occurs within the scope of a $□$