Areas Mathematical logic Topic
Provability and interpretability logics
Summary
This topic is a part of mathematical logic. It covers the modal logics that describe provability and interpretability in arithmetic, their arithmetical completeness theorems and their algebraic semantics.
Remarks
Reading order
- Provability logic: the logic , with read as provability in .
- Löb's axiom in provability logic: axiom 4 follows from Löb's axiom, and the frame condition of the axiom.
- Kripke completeness of GL: is complete for finite transitive irreflexive frames, so it is decidable.
- Solovay's arithmetical completeness theorem: is exactly the provability logic of , and is the logic of truth.
- De Jongh-Sambin fixed-point theorem: self-referential modal sentences have unique explicit fixed points.
- Grzegorczyk logic: the logic of "true and provable" and of finite partial orders.
- Japaridze's polymodal logic GLP: a hierarchy of provability operators with no complete Kripke semantics.
- Magari algebra: the algebraic models of .
- Interpretability logic: the binary operator , Veltman semantics and the logics and .
- Quantified provability logic: with quantifiers, the provability logic of is -complete.
Prerequisites
- Gödel's incompleteness theorems and related limits: the provability predicate, the derivability conditions and Löb's theorem.
- Formal arithmetic and its fragments: Peano arithmetic and its -completeness.
- Syntax, Kripke semantics and completeness of modal logic: modal logic and Kripke semantics.
Everything in this topic
The members of this topic and each page that they need, 32 pages in all.
Show the path as a graph
- no evidence level
- Proof of the complexity of quantified provability logic proof member
- Proof of the properties of Löb's axiom proof member
- Provability logic definition member
- Provability logic concept member
- Quantified provability logic statement member
- Löb's axiom in provability logic statement member
- Interpretability logic concept member
- Magari algebra concept member
- Proof of the Kripke completeness of GL proof member
- A Veltman model where interpretability is weaker than provable implication example member
- A frame without the Veltman condition fails J5 example member
- Henkin's sentence in GL example member
- S4 is not the provability logic of PA example member
- The box is definable from interpretability example member
- The formalized second incompleteness theorem in GL example member
- Kripke completeness of GL statement member
- Proof of Solovay's arithmetical completeness theorem proof member
- Solovay's arithmetical completeness theorem statement member
- Proof of the de Jongh-Sambin fixed-point theorem proof member
- Japaridze's polymodal logic GLP concept member
- Grzegorczyk logic concept member
- A bimodal frame that is not a GLP frame example member
- The mixing lemma of GLP example member
- De Jongh-Sambin fixed-point theorem statement member
- Grz proves the reflexivity axiom example member
- The two-element chain is a frame of Grz example member
- The two-element cluster is not a frame of Grz example member
- 1-consistency implies iterated consistency in GLP example member
- Magari algebra definition member
- The Magari algebra of a finite strict partial order example member
- The identity operator is not a Magari operator example member
- The two-element Magari algebra example member
About this page
| Tag | 3E7M66WW6Q |
|---|---|
| URI | m2://3E7M66WW6Q |
| Kind | topic |
| Writing | W0 stub |
| MSC | 03F45, 03B45 |
| Part of | Mathematical logic |
| Changed | 17 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a same_as or a source (0 of 1)
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
History
Each change to this page, from its provenance log. A change by an agent names its run.
| Date | Change | Field | By |
|---|---|---|---|
| 2026-11-17 | add | the whole node | tamnd |
| 2026-11-17 | add | the section Remarks | tamnd |
What links here
Nodes in this topic
- Proof of the properties of Löb's axiom
- Kripke completeness of GL
- Solovay's arithmetical completeness theorem
- Grzegorczyk logic
- A Veltman model where interpretability is weaker than provable implication
- Japaridze's polymodal logic GLP
- The formalized second incompleteness theorem in GL
- Quantified provability logic
- Provability logic
- 1-consistency implies iterated consistency in GLP
- Proof of the de Jongh-Sambin fixed-point theorem
- A frame without the Veltman condition fails J5
- The mixing lemma of GLP
- The box is definable from interpretability
- S4 is not the provability logic of PA
- The two-element Magari algebra
- Interpretability logic
- The two-element chain is a frame of Grz
- The identity operator is not a Magari operator
- The two-element cluster is not a frame of Grz
- Henkin's sentence in GL
- Proof of the Kripke completeness of GL
- A bimodal frame that is not a GLP frame
- Proof of the complexity of quantified provability logic
- Magari algebra
- Proof of Solovay's arithmetical completeness theorem
- Löb's axiom in provability logic
- The Magari algebra of a finite strict partial order
- De Jongh-Sambin fixed-point theorem
- Grz proves the reflexivity axiom
- Provability logic
- Magari algebra