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.

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$