Löb's theorem is named for Martin Hugo Löb, who formulated it in 1955.
Löb's theorem in provability logic
Provability logic abstracts away from the details of encodings used in Gödel's incompleteness theorems by expressing the provability of in the given system in the language of modal logic, by means of the modality .
Then we can formalize Löb's theorem by the axiom
known as axiom GL, for Gödel-Löb. This is sometimes formalised by means of an inference rule that infers
The provability logic GL that results from taking the modal logic K4 (or K, since the axiom schema 4, , then becomes redundant) and adding the above axiom GL is the most intensely investigated system in provability logic.
Modal Proof of Löb's theorem
Löb's theorem can be proved within modal logic using only some basic rules about the provability operator (the K4 system) plus the existence of modal fixed points.
We will assume the following grammar for formulas:
- If is a propositional variable, then is a formula.
- If is a propositional constant, then is a formula.
- If is a formula, then is a formula.
- If and are formulas, then so are , , , , and
A modal sentence is a modal formula that contains no propositional variables. We use to mean is a theorem.
Modal Fixed Points
If is a modal formula with only one propositional variable , then a modal fixed point of is a sentence such that
We will assume the existence of such fixed points for every modal formula with one free variable. This is of course not an obvious thing to assume, but if we interpret as provability in Peano Arithmetic, then the existence of modal fixed points is in fact true.
Modal Rules of Inference
In addition to the existence of modal fixed points, we assume the following rules of inference for the provability operator :
- From conclude : Informally, this says that if A is a theorem, then it is provable.
- : If A is provable, then it is provable that it is provable.
- : This rule allows you to do modus ponens inside the provability operator. If it is provable that A implies B, and A is provable, then B is provable.
Proof of Löb's theorem
- Assume that there is a modal sentence such that .
Roughly speaking, it is a theorem that if is provable, then it is, in fact true.
This is a claim of soundness.
- From the existence of modal fixed points for every formula (in particular, the formula ) it follows there exists a sentence such that .
- From 2, it follows that .
- From rule of inference 1, it follows that .
- From 4 and rule of inference 3, it follows that .
- Substituting and in rule of inference 3 gives us .
- From 5 and 6, it follows that .
- From rule of inference 2, it follows that .
- From 7 and 8, it follows that .
- From 1 and 9, it follows that .
- From 2, it follows that .
- From 10 and 11, it follows that
- From 12 and rule of inference 1, it follows that .
- From 13 and 10, it follows that .
More on the existence of modal fixed points
Not only does the existence of modal fixed points imply Löb's theorem, but the converse is valid, too. When Löb's theorem is given as an axiom (schema), the existence of a fixed point (up to provable equivalence) for any formula A(p) modalized in p can be derived. Thus in normal modal logic, Löb's axiom is equivalent to the conjunction of the axiom schema 4, and the existence of modal fixed points.
- Per Lindström (June 2006). "Note on Some Fixed Point Constructions in Provability Logic" 35 (3). pp. 225–230.
- Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-56881-262-0.
- Boolos, George S. (1995). The Logic of Provability. Cambridge University Press. ISBN 0-521-48325-5.
- Löb's theorem at PlanetMath
- The Cartoon Guide to Löb’s Theorem, by Eliezer Yudkowsky
- Generalized Löb's Theorem.Jaykov Foukzon
-  Spring Western Sectional Meeting
University of Colorado Boulder, Boulder,CO April 13–14, 2013 (Saturday-Sunday) Meeting #1089