The intuition behind the proof of Löb's theorem invokes the formalization of the following argument:

Let stand for the sentence "If $S$ is provable, then I am Santa Claus".

As it is standard, when trying to prove a If...then theorem we can start by supposing the antecedent and checking that the consequent follows. But if $S$ is provable, then we can chain its proof to an application of modus ponens of $S$ to itself in order to get a proof of the consequent "I am Santa Claus". If we suppose that showing the existence of a proof of a sentence implies that the sentence is true, then "I am Santa Claus" is true.

Thus we have supposed that $S$ is provably true then it follows that "I am Santa Claus", which is a proof of what $S$ states! Therefore, $S$ is provably true, and we can apply the same reasoning again (this time without supposing a counterfactual) to get that it is true that "I am Santa Claus".

Holy Gödel! Have we broken logic? If this argument worked, then we could prove any nonsensical thing we wanted. So where does it fail?

One suspicious point is our implicit assumption that $S$ can be constructed in the first place as a first order sentence. But we know that there exists a provability predicate encoding the meaning we need, and then we can apply the diagonal lemma to the formula $P r v (x) ⟹$ "I am Santa Claus" to get our desired $S$ .

(We will ignore the fact that expressing "I am Santa Claus" in the language of first order logic is rather difficult, since we could easily replace it with something simple like $0 = 1$ .)

It turns out that the culprit of this paradox is the apparently innocent supposition that when "I am Santa Claus" is provable, then it is true.

How can this be false?, you may ask. Well, the standard provability predicate $P r v$ is something of the form $\exists y P r o o f (x, y)$ , where $P r o o f (x, y)$ is true iff $y$ encodes a valid proof of $x$ . But $y$ might be a nonstandard number encoding a nonstandard proof of infinitely many steps. If the only proofs of $x$ are nonstandard then certainly you will never be able to prove $x$ from the axioms of the system using standard methods.

We can restate this result as Löb's theorem: If $P r v (A) ⟹ A$ is provable, then $A$ is provable.

Now we go for the formal proof.

Let $T$ be an axiomatizable extension of minimal arithmetic, and $P$ a one-place predicate satisfying the Bernais-Hilbert derivability conditions, which are:

If $T ⊢ A$ , then $T ⊢ P (A)$ .

$T ⊢ P (A ⟹ B) ⟹ (P (A) ⟹ P (B))$

$T ⊢ P (A) ⟹ P (P (A))$ .

For example, $P A$ and the standard provability predicate satisfy those conditions.

Let us suppose that $A$ is such that $T ⊢ P (A) ⟹ A$ .

As $T$ extends minimal arithmetic, the diagonal lemma is applicable, and thus there exists $S$ such that $T ⊢ S ⟺ (P (S) ⟹ A)$ .

By condition 1, $T ⊢ P (S ⟹ (P (S) ⟹ A))$ .

By condition 2, $T ⊢ P (S) ⟹ P (P (S) ⟹ A)$ .

Also by condition 2, $T ⊢ P (P (S) ⟹ A) ⟹ (P (P (S)) ⟹ P (A))$ .

Combining these, $T ⊢ P (S) ⟹ (P (P (S)) ⟹ P (A))$ .

By condition 3, $T ⊢ P (S) ⟹ P (P (S))$ and thus $T ⊢ P (S) ⟹ P (A)$ .

By our initial assumption, this means that $T ⊢ P (S) ⟹ A$ .

But by the construction of $S$ , then $T ⊢ S$ !

By condition 1 again, then $T ⊢ P (S)$ , and since we already had shown that $T ⊢ P (S) ⟹ A$ , we have that $T ⊢ A$ , which completes the proof.

We remark that $P$ can be any predicate satisfying the conditions, such as the verum predicate $x = x$ .

Posts

Wikitag Contributions

Comments