provability logic

Uses your system voice; voice and rate in settings.

Q260168Snapshot

≈ 3 min read

Names in other languages

  • Françaislogique de la prouvabilité
  • Magyarbizonyíthatósági logika
  • eologiko de pruvebleco
  • DeutschBeweisbarkeitslogik
  • EspañolLógica demostrativa
  • ItalianoLogica dimostrativa
  • Englishprovability logic
  • 日本語証明可能性論理

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Provability logic is a branch of proof theory and a modal logic, in which the box (or "necessity") operator is interpreted as 'it is provable that'. The point is to capture the notion of a proof predicate of a reasonably rich formal theory, such as Peano arithmetic.

Provability logic is a branch of proof theory and a modal logic, in which the box (or "necessity") operator is interpreted as 'it is provable that'. The point is to capture the notion of a proof predicate of a reasonably rich formal theory, such as Peano arithmetic.

Examples

There are a number of provability logics, some of which are covered in the literature mentioned in . The basic system is generally referred to as GL (for Gödel–Löb) or L or K4W (W stands for well-foundedness). It can be obtained by adding the modal version of Löb's theorem to the logic K (or K4). Namely, the axioms of GL are all tautologies of classical propositional logic plus all formulas of one of the following forms: Distribution axiom: Löb's axiom: And the rules of inference are: Modus ponens: From p → q and p conclude q; Necessitation: From \vdash p conclude \vdash .

History

Kurt Gödel wrote the first paper on provability logic in 1933. In this paper, he introduced translations from intuitionistic propositional logic into modal logic and briefly mentioned that provability could be viewed as a modal operator. The GL model was pioneered by Robert M. Solovay in 1976. Since then, until his death in 1996, the prime inspirer of the field was George Boolos. Significant contributions to the field have been made by Sergei N. Artemov, Lev Beklemishev, Giorgi Japaridze, Dick de Jongh, Franco Montagna, Giovanni Sambin, Vladimir Shavrukov, Albert Visser and others.

Generalizations

Interpretability logics and Japaridze's polymodal logic present natural extensions of provability logic.

See also

Hilbert–Bernays provability conditions Interpretability logic Kripke semantics Japaridze's polymodal logic Löb's theorem Doxastic logic

References

George Boolos, The Logic of Provability. Cambridge University Press, 1993. Giorgi Japaridze and Dick de Jongh, The logic of provability. In: Handbook of Proof Theory, S. Buss, ed. Elsevier, 1998, pp. 475–546. Sergei N. Artemov and Lev Beklemishev, Provability logic. In: Handbook of Philosophical Logic, D. Gabbay and F. Guenthner, eds., vol. 13, 2nd ed., pp. 189–360. Springer, 2005. Per Lindström, Provability logic—a short introduction. Theoria 62 (1996), pp. 19–61. Craig Smoryński, Self-reference and modal logic. Springer, Berlin, 1985. Robert M. Solovay, "Provability Interpretations of Modal Logic", Israel Journal of Mathematics, Vol. 25 (1976): 287–304. Rineke Verbrugge, Provability logic, from the Stanford Encyclopedia of Philosophy.

External links

Text derived from https://en.wikipedia.org/w/index.php?oldid=1345898026 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot provability-logic-030468-1e4f9ff369237d38 · hash 1e4f9ff369237d389a8b7378cbe55d252ab86bdf81b0700097b49aac401063d1 · captured 1774728978.0 · version history

Cite this page as: encyclopegia.org, “provability logic”, snapshot provability-logic-030468-1e4f9ff369237d38. https://encyclopegia.org/a/provability-logic

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.