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

Notation

Precedence:

• $◻$ has high precedence, so e.g. $◻C\to C$ means $(◻C)\to C$, and $◻◻L\to ◻C$ means $(◻◻L)\to (◻C)$.
• $⊢$ is a metalogical notion and has low precedence, so $\mathsf{P}\mathsf{A}⊢◻C\to C$ means $\mathsf{P}\mathsf{A}⊢(◻C\to C)$.

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}}^{\prime }:=\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}}^{\prime }$. Then we would obtain the following implication: if ${\mathsf{P}\mathsf{A}}^{\prime }⊢◻C\to C$, then ${\mathsf{P}\mathsf{A}}^{\prime }⊢C$. But clearly, ${\mathsf{P}\mathsf{A}}^{\prime }⊢◻C\to C$ since $◻C\to C$ is one of the axioms of ${\mathsf{P}\mathsf{A}}^{\prime }$. Therefore by modus ponens, we have ${\mathsf{P}\mathsf{A}}^{\prime }⊢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}}^{\prime }$ 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}}^{\prime }$), 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}}^{\prime }:=\mathsf{P}\mathsf{A}\cup \{◻C\to C\}$ to see where the error is.

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

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

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

We need the following:

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

Since ${\mathsf{P}\mathsf{A}}^{\prime }$ has more axioms than $\mathsf{P}\mathsf{A}$, we know that ${\mathsf{P}\mathsf{A}}^{\prime }$ 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}}^{\prime }⊢◻C\to C$ then ${\mathsf{P}\mathsf{A}}^{\prime }⊢◻(◻C\to C)$

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

• ${\mathsf{P}\mathsf{A}}^{\prime }⊢X\to ◻X$
• if $X$, then $\mathsf{P}\mathsf{A}⊢X$

Other questions to answer

• does $◻$ in ${\mathsf{P}\mathsf{A}}^{\prime }$ still mean provability about $\mathsf{P}\mathsf{A}$, or about itself?
• are we removing a layer or adding one?
• can't ${\mathsf{P}\mathsf{A}}^{\prime }$ prove everything $\mathsf{P}\mathsf{A}$ can? yes, but this doesn't mean we can substitute implications automatically because the consequent also gets stronger