A Proof of Löb's Theorem using Computability Theory

post by jessicata (jessica.liu.taylor) · 2023-08-16T18:57:41.048Z · LW · GW · 0 comments

This is a link post for https://unstableontology.com/2023/08/16/a-proof-of-lobs-theorem-using-computability-theory/

Contents

  Translating Löb's theorem to be more like Gödel's second incompleteness theorem
  Proving Gödel's second incompleteness theorem using computability theory
  Wrapping up
None
No comments

Löb’s Theorem states that, if $PA⊢{\square }_{PA}\left(P\right)\to P$, then $PA⊢P$. To explain the symbols here:

• PA is Peano arithmetic, a first-order logic system that can state things about the natural numbers.
• $PA⊢A$ means there is a proof of the statement $A$ in Peano arithmetic.
• ${\square }_{PA}\left(P\right)$ is a Peano arithmetic statement saying that $P$ is provable in Peano arithmetic.

I'm not going to discuss the significance of Löb's theorem, since it has been discussed elsewhere; rather, I will prove it in a way that I find simpler and more intuitive than other available proofs.

Translating Löb's theorem to be more like Gödel's second incompleteness theorem

First, let's compare Löb's theorem to Gödel's second incompleteness theorem. This theorem states that, if $PA⊢\neg {\square }_{PA}\left(\perp \right)$, then $PA⊢\perp$, where $\perp$ is a PA statement that is trivially false (such as $A\wedge \neg A$), and from which anything can be proven. A system is called inconsistent if it proves $\perp$; this theorem can be re-stated as saying that if PA proves its own consistency, it is inconsistent.

We can re-write Löb's theorem to look like Gödel's second incompleteness theorem as: if $PA+\neg P⊢\neg {\square }_{PA+\neg P}\left(\perp \right)$, then $PA+\neg P⊢\perp$. Here, $PA+\neg P$ is PA with an additional axiom that $\neg P$, and ${\square }_{PA+\neg P}$ expresses provability in this system. First I'll argue that this re-statement is equivalent to the original Löb's theorem statement.

Observe that $PA⊢P$ if and only if $PA+\neg P⊢\perp$; to go from the first to the second, we derive a contradiction from $P$ and $\neg P$, and to go from the second to the first, we use the law of excluded middle in PA to derive $P\vee \neg P$, and observe that, since a contradiction follows from $\neg P$ in PA, PA can prove $P$. Since all this reasoning can be done in PA, we have that ${\square }_{PA}\left(P\right)$ and ${\square }_{PA+\neg P}\left(\perp \right)$ are equivalent PA statements. We immediately have that the conclusion of the modified statement equals the conclusion of the original statement.

Now we can rewrite the pre-condition of Löb's theorem from $PA⊢{\square }_{PA}\left(P\right)\to P$ to $PA⊢{\square }_{PA+\neg P}\left(\perp \right)\to P$. This is then equivalent to $PA+\neg P⊢\neg {\square }_{PA+\neg P}\left(\perp \right)$. In the forward direction, we simply derive $\perp$ from $P$ and $\neg P$. In the backward direction, we use the law of excluded middle in PA to derive $P\vee \neg P$, observe the statement is trivial in the $P$ branch, and in the $\neg P$ branch, we derive $\neg {\square }_{PA+\neg P}\left(\perp \right)$, which is stronger than ${\square }_{PA+\neg P}\left(\perp \right)\to P$.

So we have validly re-stated Löb's theorem, and the new statement is basically a statement that Gödel's second incompleteness theorem holds for $PA+\neg P$.

Proving Gödel's second incompleteness theorem using computability theory

The following proof of a general version of Gödel's second incompleteness theorem is essentially the same as Sebastian Oberhoff's in "Incompleteness Ex Machina". See also Scott Aaronson's proof of Gödel's first incompleteness theorem.

Let L be some first-order system that is at least as strong as PA (for example, $PA+\neg P$). Since L is at least as strong as PA, it can express statements about Turing machines. Let $Halts\left(M\right)$ be the PA statement that Turing machine M (represented by a number) halts. If this statement is true, then PA (and therefore L) can prove it; PA can expand out M's execution trace until its halting step. However, we have no guarantee that if the statement is false, then L can prove it false. In fact, L can't simultaneously prove this for all non-halting machines M while being consistent, or we could solve the halting problem by searching for proofs of $Halts\left(M\right)$ and $\neg Halts\left(M\right)$ in parallel.

That isn't enough for us, though; we're trying to show that L can't simultaneously be consistent and prove its own consistency, not that it isn't simultaneously complete and sound on halting statements.

Let's consider a machine Z(A) that searches over all L-proofs of $\neg Halts(‘‘┌A┐(┌A┐)")$ (where $‘‘┌A┐(┌A┐)"$ is an encoding of a Turing machine that runs A on its own source code), and halts only when finding such a proof. Define a statement G to be $\neg Halts(‘‘┌Z┐(┌Z┐)")$, i.e. Z(Z) doesn't halt. If Z(Z) halts, then that means that L proves that Z(Z) doesn't halt; but, L can prove Z(Z) halts (since it in fact halts), so this would show L to be inconsistent.

Assuming L is consistent, G is therefore true. If L proves its own consistency, all this reasoning can be done in L, so $L⊢G$. But that means $L⊢\neg Halts(‘‘┌Z┐(┌Z┐)")$, so Z(Z) finds a proof and halts. L therefore proves $\neg G$, but L also proves G, making it inconsistent. This is enough to show that, if L proves its own consistency, it is inconsistent.

Wrapping up

Let’s now prove Löb’s theorem. We showed that Löb’s theorem can be re-written as, if $PA+\neg P⊢\neg {\square }_{PA+\neg P}\left(\perp \right)$, then $PA+\neg P⊢\perp$. This states that, if $PA+\neg P$ proves its own consistency, it is inconsistent. Since $PA+\neg P$ is at least as strong as PA, we can set $L=PA+\neg P$ in the proof of Gödel’s second incompleteness theorem, and therefore prove this statement which we have shown to be equivalent to Löb’s theorem.

I consider this proof more intuitive than the usual proof of Löb’s theorem. By re-framing Lob's theorem as a variant of Gödel's second incompleteness theorem, and proving Gödel's second incompleteness theorem using computability theory, the proof is easy to understand without shuffling around a lot of math symbols (especially provability boxes).

0 comments

Comments sorted by top scores.