Löb's theorem
The set of Lob is a result of mathematical logic, which was proved by Martin Loeb in 1955. He says that in a theory that satisfies certain simple properties and represent the provability in T can, for any formula P, the statement " if P is provable, then P" is only provable if P is provable. Formal:
Which means that the formula P is provable in T. (# P is the Gödel number of P associated Term ) The conditions of the theorem are fulfilled in all sufficiently powerful mathematical theories such as Peano arithmetic and the Zermelo -Fraenkel set theory. The set plays an important role in the Beweisbarkeitslogik.
Evidence
Requirements
Instead of provability in a particular theory to consider, the set of Loeb leaves from a few abstract properties of provability show. A predicate B is called Beweisbarkeitsprädikat for a theory T if it satisfies the following three conditions for all formulas:
It can be shown that a standard representation of provability in a theory like Peano arithmetic or set theory meets these three requirements and is thus a Beweisbarkeitsprädikat.
Now let T be a theory, which has the following properties:
- T has a Beweisbarkeitsprädikat B.
- Diagonalization: In T, every formula with free variable a fixed point in the following sense: If a formula with free variable x, then there is a formula, so that:, that is, has the intuitive meaning "I have the property. "
Evidence
With the given conditions can be the set of Loeb prove as follows:
Applications
- A Henkinsatz is a sentence expressing its own provability. The set of Loeb shows that each Henkinsatz is provable. For if a Henkinsatz is true, so by the theorem of Loeb.
- P is a truth predicate, if for all formulas. It is easy to show that P is also a Beweisbarkeitsprädikat for T. After the set of Loeb then for all formulas and T is inconsistent. So has no consistent theory of a truth predicate.
- The second Gödel's incompleteness theorem states that a sufficiently strong and consistent formal system can not prove its own consistency. This can be deduced from the set of Loeb as follows. Suppose proves its own consistency, that is,. This is to be equivalent. After the set of Loeb and thus is inconsistent.