User:IssaRice/Computability and logic/Eliezer Yudkowsky's Löb's theorem puzzle

original link: https://web.archive.org/web/20160319050228/http://lesswrong.com/lw/t6/the_cartoon_guide_to_l%C3%B6bs_theorem/

current LW link: https://www.lesswrong.com/posts/ALCnqX6Xx8bpFMZq3/the-cartoon-guide-to-loeb-s-theorem

Translating the puzzle using logic notation

Löb's theorem shows that if $\mathsf{P}\mathsf{A}⊢◻C\to C$, then $\mathsf{P}\mathsf{A}⊢C$.

The deduction theorem says that if $\mathsf{P}\mathsf{A}\cup \{H\}⊢F$, then $\mathsf{P}\mathsf{A}⊢H\to F$.

Applying the deduction theorem to Löb's theorem gives us $\mathsf{P}\mathsf{A}⊢(◻C\to C)\to C$.

When translating to logic notation, it becomes obvious that the application of the deduction theorem is illegitimate, because we don't actually have $\mathsf{P}\mathsf{A}\cup \{◻C\to C\}⊢C$. This is the initial answer that Larry D'Anna gives in comments.

But now, suppose we define $\mathsf{P}\mathsf{A}\text{'}:=\mathsf{P}\mathsf{A}\cup \{◻C\to C\}$, and walk through the proof of Löb's theorem for this new theory $\mathsf{P}\mathsf{A}\text{'}$. Then we would obtain the following implication: if $\mathsf{P}\mathsf{A}\text{'}⊢◻C\to C$, then $\mathsf{P}\mathsf{A}\text{'}⊢C$. But clearly, $\mathsf{P}\mathsf{A}\text{'}⊢◻C\to C$ since $◻C\to C$ is one of the axioms of $\mathsf{P}\mathsf{A}\text{'}$. Therefore by modus ponens, we have $\mathsf{P}\mathsf{A}\text{'}⊢C$, i.e. $\mathsf{P}\mathsf{A}\cup \{◻C\to C\}⊢C$. Now we can apply the deduction theorem to obtain $\mathsf{P}\mathsf{A}⊢(◻C\to C)\to C$. This means that our "Löb's theorem" for $\mathsf{P}\mathsf{A}\text{'}$ must be incorrect (note: the proof is correct for $\mathsf{P}\mathsf{A}$, which is why Löb's theorem is a theorem; it's just incorrect for $\mathsf{P}\mathsf{A}\text{'}$), and somewhere in the ten-step proof is an error.

Translating the Löb's theorem back to logic

http://yudkowsky.net/assets/44/LobsTheorem.pdf

Since the solution to the puzzle refers back to the proof of Löb's theorem, we first translate the proof from the cartoon version back to logic:

1. $\mathsf{P}\mathsf{A}⊢◻L\leftrightarrow ◻(◻L\to C)$
2. $\mathsf{P}\mathsf{A}⊢◻C\to C$
3. $\mathsf{P}\mathsf{A}⊢◻(◻L\to C)\to (◻◻L\to ◻C)$
4. $\mathsf{P}\mathsf{A}⊢◻L\to (◻◻L\to ◻C)$
5. $\mathsf{P}\mathsf{A}⊢◻L\to ◻◻L$
6. $\mathsf{P}\mathsf{A}⊢◻L\to ◻C$
7. $\mathsf{P}\mathsf{A}⊢◻L\to C$
8. $\mathsf{P}\mathsf{A}⊢◻(◻L\to C)$
9. $\mathsf{P}\mathsf{A}⊢◻L$
10. $\mathsf{P}\mathsf{A}⊢C$

Repeating the proof of Löb's theorem for modified theory

We now repeat the proof of Löb's theorem for $\mathsf{P}\mathsf{A}\text{'}:=\mathsf{P}\mathsf{A}\cup \{◻C\to C\}$ to see where the error is.

1. $\mathsf{P}\mathsf{A}\text{'}⊢◻L\leftrightarrow ◻(◻L\to C)$ by definition of $L$
2. $\mathsf{P}\mathsf{A}\text{'}⊢◻C\to C$ because $◻C\to C$ is one of the axioms of $\mathsf{P}\mathsf{A}\text{'}$
3. $\mathsf{P}\mathsf{A}\text{'}⊢◻(◻L\to C)\to (◻◻L\to ◻C)$
4. $\mathsf{P}\mathsf{A}\text{'}⊢◻L\to (◻◻L\to ◻C)$
5. $\mathsf{P}\mathsf{A}\text{'}⊢◻L\to ◻◻L$
6. $\mathsf{P}\mathsf{A}\text{'}⊢◻L\to ◻C$
7. $\mathsf{P}\mathsf{A}\text{'}⊢◻L\to C$

So far, everything is fine. But can we assert $\mathsf{P}\mathsf{A}\text{'}⊢◻(◻L\to C)$? For $\mathsf{P}\mathsf{A}$, we had the following:

A1: For each $X$, if $\mathsf{P}\mathsf{A}⊢X$ then $\mathsf{P}\mathsf{A}⊢◻X$

We need the following:

A1′: For each $X$, if $\mathsf{P}\mathsf{A}\text{'}⊢X$ then $\mathsf{P}\mathsf{A}\text{'}⊢◻X$

Since $\mathsf{P}\mathsf{A}\text{'}$ has more axioms than $\mathsf{P}\mathsf{A}$, we know that $\mathsf{P}\mathsf{A}\text{'}$ can prove everything that $\mathsf{P}\mathsf{A}$ can. Thus, compared to A1, both the antecedent and consequent of A1′ are stronger, so A1′ does not necessarily follow from A1.

Suppose we take $X$ in A1′ to be $◻C\to C$. Then we obtain

If $\mathsf{P}\mathsf{A}\text{'}⊢◻C\to C$ then $\mathsf{P}\mathsf{A}\text{'}⊢◻(◻C\to C)$

Other ways we might try to get step 8 to work:

• $\mathsf{P}\mathsf{A}\text{'}⊢X\to ◻X$
• if $X$, then $\mathsf{P}\mathsf{A}⊢X$