Löb's theorem

Löb's theorem

In mathematical logic, Löb's theorem states that in a theory with Peano arithmetic, for any formula P, if it is provable that "if "P" is provable then "P", then "P" is provable. I.e.

:if PA vdash Bew(# P) ightarrow P, then PA vdash P

where Bew(#P) means that the formula P with Gödel number #P is provable.

Löb's theorem is named for Martin Hugo Löb.

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 phi in the given system in the language of modal logic, by means of the modality Box phi.

Then we can formalize Löb's theorem by the axiom

:Box(Box P ightarrow P) ightarrow Box P,

known as axiom GL, for Gödel-Löb. This is sometimes formalised by means of an inference rule that infers

:Box P

from

:Box P ightarrow P.

The provability logic GL that results from taking the modal logic "K4" and adding the above axiom GL is the most intensely investigated system in provability logic.

External links

[http://planetmath.org/?op=getobj&from=objects&id=9381 Löb's theorem at PlanetMath]

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Martin Löb — Martin Hugo Löb (31 March 1921, Berlin 21 August 2006, Annen) was a German mathematician. He settled in the United Kingdom after the Second World War and specialised in mathematical logic. He moved to the Netherlands in the 1970s, where he… …   Wikipedia

  • Theoreme de Lob — Théorème de Löb En logique mathématique, le théorème de Löb, démontré par Martin Hugo Löb (31 mars 1921 21 août 2006), est une variante du second théorème d incomplétude de Gödel. Il dit que dans toute théorie T satisfaisant… …   Wikipédia en Français

  • Théorème de Löb — En logique mathématique, le théorème de Löb, démontré par Martin Hugo Löb (31 mars 1921 21 août 2006), est une variante du second théorème d incomplétude de Gödel. Il dit que dans toute théorie T satisfaisant les conditions de …   Wikipédia en Français

  • Doxastic logic — is a modal logic concerned with reasoning about beliefs. The term doxastic derives from the ancient Greek δόξα, doxa, which means belief. Typically, a doxastic logic uses Bx to mean It is believed that x is the case, and the set denotes a set of… …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • Gödel's incompleteness theorems — In mathematical logic, Gödel s incompleteness theorems, proved by Kurt Gödel in 1931, are two theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest. The theorems are of… …   Wikipedia

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

  • Loeb — Loeb(or Löb) may refer to:* Loeb (supermarket), a Canadian chain of supermarket/grocery stores * Loeb s (department store), a fine specialty department store * Loeb Classical Library, a series of books containing the works of Greek and Latin… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”