A primer on provability logic

[Benya_Fallenstein]

MIRI’s paper on robust cooperation in the one-shot prisoner’s dilemma (by Patrick LaVictoire and others) models agents which know their opponents’ source code through Gödel-Löb provability logic, a modal logic for reasoning about provability in Peano Arithmetic. This framework of “modal agents” has turned out to be a really useful way of reasoning about these agents. Vladimir Slepnev recently proposed reformulating UDT with a halting oracle in terms of provability logic as well, and I agree that this is the right tool for the job. This post is a primer on provability logic and the results about it that we’ve been using in our work.

The language

Gödel-Löb provability logic (“GL”) is propositional logic plus a modal operator, $\square$, which we interpret as “provable”. Formulas may contain variables which denote propositions; for example $p\to \square (q\to q)$ is a formula saying that if the proposition $p$ is true, then it’s provable that the proposition $q$ implies itself. We usually write $\top$ for the proposition “true” and $\perp$ for the proposition “false”.

Some conventions that we’ve been using: Use small letters (e.g. $p$, $q$) to refer to propostional variables; use capital letters (e.g. $A$, $B$) to refer to particular formulas; use $\phi$, $\psi$ as metavariables ranging over formulas. (The line between “concrete formula” and “metavariable standing in for a formula” isn’t hard-and-fast.) When a formula contains propositional variables, list them in parantheses when talking about the formula: e.g., $\phi (p_1,\dots ,p_n)$.

The meaning of a closed formula (i.e., a formula without propositional variables) is given by a recursive translation to a sentence of Peano arithmetic: If the modal formula $\phi$ is translated to the arithmetic formula $\tilde{\phi }$, then $\square \phi$ is translated to the arithmetic formula stating “the formula $┌\tilde{\phi }┐$ is provable in PA”. (Propositional connectives are translated in the obvious way, e.g.$\neg \phi$ is translated to $\neg \tilde{\phi }$.)

In practice, instead of making this translation explicit, we just abbreviate ”$┌\phi ┐$ is provable in PA” as $\square \phi$ in formulas of arithmetic, and leave it to the context to disambiguate whether we’re talking about a modal or an arithmetic formula. Because of this, we may sometimes write $\square ┌\phi ┐$ instead of $\square \phi$ to emphasize the Gödel quotations in the arithmetic version of the formula.

Soundness and completeness

The axioms and inference rules of GL can be stated in the usual style of a modal logic, but in practice, two basic results about GL provide a much more convenient way to reason about it:

• The soundness theorem states that if a formula $\phi (p_1,\dots ,p_n)$ is provable in GL, then for any closed formulas ${\psi }_1,\dots ,{\psi }_n$ in the language of arithmetic, $\phi ({\psi }_1,\dots ,{\psi }_n)$ is provable in PA.

• The completeness theorem is the exact converse: It states that if $\phi (p_1,\dots ,p_n)$ is a formula of provability logic, and if for any closed formulas ${\psi }_1,\dots ,{\psi }_n$ in the language of arithmetic, $\phi ({\psi }_1,\dots ,{\psi }_n)$ is provable in PA, then $\phi (p_1,\dots ,p_n)$ is provable in GL.

In summary: $$GL⊢\phi (p_1,\dots ,p_n)⟺\forall {\psi }_1,\dots ,{\psi }_n.PA⊢\phi ({\psi }_1,\dots ,{\psi }_n).$$

This means that we can argue that something is provable in GL by arguing that the analogous thing is provable in PA. For example, Löb’s theorem states that if $PA⊢\square \phi \to \phi$, then $PA⊢\phi$. This implies that the analogous statement holds in GL: Suppose that $GL⊢\square \phi (p_1,\dots ,p_n)\to \phi (p_1,\dots ,p_n)$. Then by soundness, $PA⊢\square \phi ({\psi }_1,\dots ,{\psi }_n)\to \phi ({\psi }_1,\dots ,{\psi }_n)$ for all ${\psi }_1,\dots ,{\psi }_n$, and hence by Löb, $PA⊢\phi ({\psi }_1,\dots ,{\psi }_n)$. But by completess, this implies $GL⊢\phi (p_1,\dots ,p_n)$.

Similarly, $GL⊢\phi (p_1,\dots ,p_n)$ implies $GL⊢\square \phi (p_1,\dots ,p_n)$, again because the analogous statement holds about PA.

As a matter of fact, both of these happen to be an inference rules of GL. But the point is that you don’t need to memorize the axioms and inference rules of GL in order to use it; it’s sufficient to know about its soundness and completeness.

Substitution of equivalent formulas

Despite the above, there is one important result about GL that is not obvious from soundness and completeness: If GL proves two formulas $\phi (p_1,\dots ,p_n)$ and ${\phi }^{\prime }(p_1,\dots ,p_n)$ equivalent, then you can substitute ${\phi }^{\prime }$ for $\phi$ in any other formula, even inside boxes; in other words, in this case, GL will prove that $\psi (p_1,\dots ,p_n,\phi (p_1,\dots ,p_n\left)\right)$ is equivalent to $\psi (p_1,\dots ,p_n,{\phi }^{\prime }(p_1,\dots ,p_n\left)\right)$, for every formula $\psi (p_1,\dots ,p_n,q)$.

Fixed points

The other really important results about GL are the existence and uniqueness of fixed points.

We say that a formula $\phi (p,q_1,\dots ,q_n)$ is modalized in $p$ if all occurrences of $p$ in $\phi (p,q_1,\dots ,q_n)$ are inside boxes. We say that $\phi (p_1,\dots ,p_n)$ is fully modalized if it is modalized in each $p_i$. (We don’t need the latter notion in the rest of this post, but it’s frequently used in applications.)

Suppose that $F(p,q)$ is modalized in $p$. Then there is a formula $A\left(q\right)$ which is a fixed point of $F(p,q)$ in the sense that $$GL⊢A\left(q\right)\leftrightarrow F\left(A\right(q),q).$$ Moreover, there’s a computer program that computes $A\left(q\right)$ given $F(p,q)$; and if $q$ is modalized in $F(p,q)$, then it is modalized in $A\left(q\right)$ as well.

More generally, this holds for multiple parameters $q_1,\dots ,q_n$ and multiple formulas $F_i(p_1,\dots ,p_m,q_1,\dots ,q_n)$, $i=1,\dots ,m$. In that case, we can find formulas $A_i(q_1,\dots ,q_n)$ such that for every $i$, GL proves that $A_i(q_1,\dots ,q_n)$ is equivalent to $F_i\left(A_1\right(q_1,\dots ,q_n),\dots ,A_m(q_1,\dots ,q_n),q_1,\dots ,q_n).$

Moreover, it can be shown that these fixed points are unique—not in the sense that there is only one set of formulas $A_1,\dots ,A_m$ satisfying the above condition, of course (if $A_i$ works, so does $A_i\wedge \top$: see the rule about substitution of equivalent formulas), but in the sense that if $A_1,\dots ,A_m$ is a solution and $B_1,\dots ,B_m$ is also a solution, then $GL⊢A_i(q_1,\dots ,q_n)\leftrightarrow B_i(q_1,\dots ,q_n)$, $i=1,\dots ,m$.

This is true not only about solutions that can be written in the language of provability logic, but for any solution in the language of arithmetic: Suppose that ${\phi }_1,\dots ,{\phi }_m$, ${\phi }_1,\dots ,{\phi }_m$, and ${\psi }_1,\dots ,{\psi }_n$ are all closed formulas of arithmetic, such that for $i=1,\dots ,m$, PA proves ${\phi }_i\leftrightarrow F_i({\phi }_1,\dots ,{\phi }_m,{\psi }_1,\dots ,{\psi }_n)$ and ${\phi }_i^{\prime }\leftrightarrow F_i({\phi }_1^{\prime },\dots ,{\phi }_m^{\prime },{\psi }_1,\dots ,{\psi }_n)$. Then $PA⊢{\phi }_i\leftrightarrow {\phi }_i^{\prime }$, for $i=1,\dots ,m$.

Decidability

Provability in GL turns out to be decidable, though it’s PSPACE-complete, which sounds pretty bad, but perhaps the formulas we’re interested in are mostly so short that it doesn’t matter—I don’t know. In the case of modal agents, Mihaly and Marcello wrote program which computes what two such agents do against each other, and it was efficient enough that we were able to use it to verify the examples in the paper. I don’t know whether the techniques would generalize to the application to UDT.

Further reading

If you want to go dig deeper, you may want to consult the Stanford Encyclopedia of Philosophy entry on provability logic or Per Lindström’s excellent article “Provability logic—a short introduction” (Theoria, 62(1-2):19--61, 1996). Gated copy.

Some of the results claimed here aren’t in Lindström, though they follow straight-forwardly from what is there; I’ll later add the proofs in comments. In the meantime, some of the additional stuff can be found in the modal agents paper.

[Benya_Fallenstein]

Thread for proofs of results claimed above (not limited to stuff not found in Lindström); contributions appreciated. Stuff not in Lindström includes the uniqueness of arithmetic fixed points in PA (found in the modal agents paper), and I think the version of the fixed point theorem with more than one $F_i$ (the latter should be provable by iterated application of the fixed point theorem for a single $F$).

[Jaime Sevilla Molina]

Generalized fixed point theorem:

Suppose that $A_i(p_1,...,p_n)$ are $n$ modal sentences such that $A_i$ is modalized in $p_n$ (possibly containing sentence letters other than $p_{j}s$).

Then there exists $H_1,...,H_n$ in which no $p_j$ appears such that $GL⊢{\wedge }_{i\le n}\{⊡(p_i\leftrightarrow A_i(p_1,...,p_n)\}\leftrightarrow {\wedge }_{i\le n}\{⊡(p_i\leftrightarrow H_i)\}$.

---

We will prove it by induction.

For the base step, we know by the fixed point theorem that there is $H$ such that $GL⊢⊡(p_1\leftrightarrow A_i(p_1,...,p_n\left)\right)\leftrightarrow ⊡(p_1\leftrightarrow H(p_2,...,p_n\left)\right)$

Now suppose that for $j$ we have $H_1,...,H_j$ such that $GL⊢{\wedge }_{i\le j}\{⊡(p_i\leftrightarrow A_i(p_1,...,p_n)\}\leftrightarrow {\wedge }_{i\le j}\{⊡(p_i\leftrightarrow H_i(p_{j+1},...,p_n\left)\right)\}$.

By the second substitution theorem, $GL⊢⊡(A\leftrightarrow B)\to \left[F\right(A)\leftrightarrow F(B\left)\right]$. Therefore we have that $GL⊢⊡(p_i\leftrightarrow H_i(p_{j+1},...,p_n)\to [⊡(p_{j+1}\leftrightarrow A_{j+1}(p_1,...,p_n\left)\right)\leftrightarrow ⊡(p_{j+1}\leftrightarrow A_{j+1}(p_1,...,p_{i-1},H_i(p_{j+1},...,p_n),p_{i+1},...,p_n\left)\right)]$.

If we iterate the replacements, we finally end up with $GL⊢{\wedge }_{i\le j}\{⊡(p_i\leftrightarrow A_i(p_1,...,p_n)\}\to ⊡(p_{j+1}\leftrightarrow A_{j+1}(H_1,...,H_j,p_{j+1},...,p_n))$.

Again by the fixed point theorem, there is $H_{j+1}^{\prime }$ such that $GL⊢⊡(p_{j+1}\leftrightarrow A_{j+1}(H_1,...,H_j,p_{j+1},...,p_n\left)\right)\leftrightarrow ⊡[p_{j+1}\leftrightarrow H_{j+1}^{\prime }(p_{j+2},...,p_n\left)\right]$.

But as before, by the second substitution theorem, $GL⊢⊡[p_{j+1}\leftrightarrow H_{j+1}^{\prime }(p_{j+2},...,p_n\left)\right]\to [⊡(p_i\leftrightarrow H_i(p_{j+1},...,p_n))\leftrightarrow ⊡(p_i\leftrightarrow H_i(H_{j+1}^{\prime },...,p_n))$.

Let $H_i^{\prime }$ stand for $H_i(H_{j+1}^{\prime },...,p_n)$, and by combining the previous lines we find that $GL⊢{\wedge }_{i\le j+1}\{⊡(p_i\leftrightarrow A_i(p_1,...,p_n)\}\to {\wedge }_{i\le j+1}\{⊡(p_i\leftrightarrow H_i^{\prime }(p_{j+2},...,p_n\left)\right)\}$.

By Goldfarb’s lemma, we do not need to check the other direction, so $GL⊢{\wedge }_{i\le j+1}\{⊡(p_i\leftrightarrow A_i(p_1,...,p_n)\}\leftrightarrow {\wedge }_{i\le j+1}\{⊡(p_i\leftrightarrow H_i^{\prime }(p_{j+2},...,p_n\left)\right)\}$ and the proof is finished $\square$

---

An immediate consequence of the theorem is that for those fixed points $H_i$ and every $A_i$, $GL⊢H_i\leftrightarrow A_i(H_1,...,H_n)$.

Indeed, since $GL$ is closed under substitution, we can make the change $p_i$ for $H_i$ in the theorem to get that $GL⊢{\wedge }_{i\le n}\{⊡(H_i\leftrightarrow A_i(H_1,...,H_n)\}\leftrightarrow {\wedge }_{i\le n}\{⊡(H_i\leftrightarrow H_i)\}$.

Since the righthand side is trivially a theorem of $GL$, we get the desired result.

---

One remark: the proof is wholly constructive. You can iterate the construction of fixed point following the procedure implied by the construction of the $H_i^{\prime }$ to compute fixed points.

[Jaime Sevilla Molina]

Uniqueness of arithmetic fixed points:

Notation: $⊡A=\square A\wedge A$

Let $H$ be a fixed point on $p$ of $\varphi \left(p\right)$; that is, $GL⊢⊡(p\leftrightarrow \varphi (p\left)\right)\leftrightarrow (p\leftrightarrow H)$.

Suppose $I$ is such that $GL⊢H\leftrightarrow I$. Then by the first substitution theorem, $GL⊢F\left(I\right)\leftrightarrow F\left(H\right)$ for every formula $F\left(q\right)$. If $F\left(q\right)=⊡(p\leftrightarrow q)$, then $GL⊢⊡(p\leftrightarrow H)\leftrightarrow ⊡(p\leftrightarrow I)$, from which it follows that $GL⊢⊡(p\leftrightarrow \varphi (p\left)\right)\leftrightarrow (p\leftrightarrow I)$.

Conversely, if $H$ and $I$ are fixed points, then $GL⊢⊡(p\leftrightarrow H)\leftrightarrow ⊡(p\leftrightarrow I)$, so since $GL$ is closed under substitution, $GL⊢⊡(H\leftrightarrow H)\leftrightarrow ⊡(H\leftrightarrow I)$. Since $GL⊢⊡(H\leftrightarrow H)$, it follows that $GL⊢(H\leftrightarrow I)$.

(Taken from The Logic of Provability, by G. Boolos.)