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, 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

1. $\mathsf{P}\mathsf{A}\text{'}⊢◻L\leftrightarrow ◻(◻L\to C)$
2. $\mathsf{P}\mathsf{A}\text{'}⊢◻C\to C$
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$
8. $\mathsf{P}\mathsf{A}\text{'}⊢◻(◻L\to C)$
9. $\mathsf{P}\mathsf{A}\text{'}⊢◻L$
10. $\mathsf{P}\mathsf{A}\text{'}⊢C$