Math 2.0

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

  1. Provability logic: the logic 𝖦𝖫\mathsf{GL}, with □\square read as provability in 𝖯𝖠\mathsf{PA}.
  2. Löb's axiom in provability logic: axiom 4 follows from Löb's axiom, and the frame condition of the axiom.
  3. Kripke completeness of GL: 𝖦𝖫\mathsf{GL} is complete for finite transitive irreflexive frames, so it is decidable.
  4. Solovay's arithmetical completeness theorem: 𝖦𝖫\mathsf{GL} is exactly the provability logic of 𝖯𝖠\mathsf{PA}, and 𝖦𝖫𝖲\mathsf{GLS} is the logic of truth.
  5. De Jongh-Sambin fixed-point theorem: self-referential modal sentences have unique explicit fixed points.
  6. Grzegorczyk logic: the logic of "true and provable" and of finite partial orders.
  7. Japaridze's polymodal logic GLP: a hierarchy of provability operators with no complete Kripke semantics.
  8. Magari algebra: the algebraic models of 𝖦𝖫\mathsf{GL}.
  9. Interpretability logic: the binary operator ⊳\rhd, Veltman semantics and the logics 𝖨𝖫𝖬\mathsf{ILM} and 𝖨𝖫𝖯\mathsf{ILP}.
  10. Quantified provability logic: with quantifiers, the provability logic of 𝖯𝖠\mathsf{PA} is Π20\Pi^0_2-complete.

Prerequisites

  1. Gödel's incompleteness theorems and related limits: the provability predicate, the derivability conditions and Löb's theorem.
  2. Formal arithmetic and its fragments: Peano arithmetic and its Σ1\Sigma_1-completeness.
  3. 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
Proof of the complexity of quantified provability logic, proof, no evidence levelProof of the complexi…proofProof of the properties of Löb's axiom, proof, no evidence levelProof of the properti…proofProvability logic, definition, no evidence levelProvability logicdefinitionProvability logic, concept, no evidence levelProvability logicconceptQuantified provability logic, statement, no evidence levelQuantified provabilit…statementLöb's axiom in provability logic, statement, no evidence levelLöb's axiom in provab…statementInterpretability logic, concept, no evidence levelInterpretability logicconceptMagari algebra, concept, no evidence levelMagari algebraconceptProof of the Kripke completeness of GL, proof, no evidence levelProof of the Kripke c…proofA Veltman model where interpretability is weaker than provable implication, example, no evidence levelA Veltman model where…exampleA frame without the Veltman condition fails J5, example, no evidence levelA frame without the V…exampleHenkin's sentence in GL, example, no evidence levelHenkin's sentence in …exampleS4 is not the provability logic of PA, example, no evidence levelS4 is not the provabi…exampleThe box is definable from interpretability, example, no evidence levelThe box is definable …exampleThe formalized second incompleteness theorem in GL, example, no evidence levelThe formalized second…exampleKripke completeness of GL, statement, no evidence levelKripke completeness o…statementProof of Solovay's arithmetical completeness theorem, proof, no evidence levelProof of Solovay's ar…proofSolovay's arithmetical completeness theorem, statement, no evidence levelSolovay's arithmetica…statementProof of the de Jongh-Sambin fixed-point theorem, proof, no evidence levelProof of the de Jongh…proofJaparidze's polymodal logic GLP, concept, no evidence levelJaparidze's polymodal…conceptGrzegorczyk logic, concept, no evidence levelGrzegorczyk logicconceptA bimodal frame that is not a GLP frame, example, no evidence levelA bimodal frame that …exampleThe mixing lemma of GLP, example, no evidence levelThe mixing lemma of G…exampleDe Jongh-Sambin fixed-point theorem, statement, no evidence levelDe Jongh-Sambin fixed…statementGrz proves the reflexivity axiom, example, no evidence levelGrz proves the reflex…exampleThe two-element chain is a frame of Grz, example, no evidence levelThe two-element chain…exampleThe two-element cluster is not a frame of Grz, example, no evidence levelThe two-element clust…example1-consistency implies iterated consistency in GLP, example, no evidence level1-consistency implies…exampleMagari algebra, definition, no evidence levelMagari algebradefinitionThe Magari algebra of a finite strict partial order, example, no evidence levelThe Magari algebra of…exampleThe identity operator is not a Magari operator, example, no evidence levelThe identity operator…exampleThe two-element Magari algebra, example, no evidence levelThe two-element Magar…example
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Proof of the complexity of quantified provability logic proof member
  2. Proof of the properties of Löb's axiom proof member
  3. Provability logic definition member
  4. Provability logic concept member
  5. Quantified provability logic statement member
  6. Löb's axiom in provability logic statement member
  7. Interpretability logic concept member
  8. Magari algebra concept member
  9. Proof of the Kripke completeness of GL proof member
  10. A Veltman model where interpretability is weaker than provable implication example member
  11. A frame without the Veltman condition fails J5 example member
  12. Henkin's sentence in GL example member
  13. S4 is not the provability logic of PA example member
  14. The box is definable from interpretability example member
  15. The formalized second incompleteness theorem in GL example member
  16. Kripke completeness of GL statement member
  17. Proof of Solovay's arithmetical completeness theorem proof member
  18. Solovay's arithmetical completeness theorem statement member
  19. Proof of the de Jongh-Sambin fixed-point theorem proof member
  20. Japaridze's polymodal logic GLP concept member
  21. Grzegorczyk logic concept member
  22. A bimodal frame that is not a GLP frame example member
  23. The mixing lemma of GLP example member
  24. De Jongh-Sambin fixed-point theorem statement member
  25. Grz proves the reflexivity axiom example member
  26. The two-element chain is a frame of Grz example member
  27. The two-element cluster is not a frame of Grz example member
  28. 1-consistency implies iterated consistency in GLP example member
  29. Magari algebra definition member
  30. The Magari algebra of a finite strict partial order example member
  31. The identity operator is not a Magari operator example member
  32. The two-element Magari algebra example member
About this page
Tag3E7M66WW6Q
URIm2://3E7M66WW6Q
Kindtopic
WritingW0 stub
MSC03F45, 03B45
Part ofMathematical logic
Changed17 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.

The changes to this page, the oldest first
DateChangeFieldBy
2026-11-17addthe whole nodetamnd
2026-11-17addthe section Remarkstamnd

What links here

Nodes in this topic