Enderton 3.7 Problem 1

• Jan 14th 2012, 07:10 AM
logics
Enderton 3.7 Problem 1
Let $\displaystyle \sigma$ be a sentence such that

$\displaystyle \text{PA} \vdash (\sigma \leftrightarrow \text{Prb}_{PA}\sigma).$

(Thus $\displaystyle \sigma$ says "I am provable," in contrast to the sentence "I am unprovable" that has been found to have such interesting proberties.)

Does $\displaystyle \text{PA} \vdash \sigma$?

(Notation) PA stands for "Peano arithmetic", and Prb (textbook page 266) abbreviates "Provable".

================================================== ===

Löb's Theorem: Assume that T is sufficiently strong recursively axiomatizable theory. If $\displaystyle \tau$ is any sentence for which $\displaystyle T \vdash (\text{Prb}_T \tau \rightarrow \tau)$, then $\displaystyle T \vdash \tau$.

Textbook says that PA is sufficiently strong theory (page 269), so I think I can apply
Löb's Theorem directly.

By hypothesis, $\displaystyle \textbook{PA} \vdash (\text{Prb}_\TEXT{PA} \sigma \leftrightarrow \sigma)$.

We see that if $\displaystyle \textbook{PA} \vdash (\text{Prb}_\TEXT{PA} \sigma \rightarrow \sigma)$, then, $\displaystyle \text{PA} \vdash \sigma$ by Löb's Theorem.

Further, if $\displaystyle \textbook{PA} \vdash (\sigma \rightarrow \text{Prb}_\TEXT{PA} \sigma)}$, then we claim that $\displaystyle \text{PA} \vdash \sigma$. Suppose to the contrary that $\displaystyle \text{PA} \not\vdash \sigma$. Then $\displaystyle \textbook{PA} \not\vdash \text{Prb}_\text{PA} \sigma}$ by the choice of $\displaystyle \sigma$, which follows that $\displaystyle \textbook{PA} \not\vdash (\sigma \rightarrow \text{Prb}_\TEXT{PA} \sigma)}$.

Thus $\displaystyle \text{PA} \vdash \sigma$.

Could you check the above?

Thanks.
• Jan 14th 2012, 09:55 AM
emakarov
Re: Enderton 3.7 Problem 1
Quote:

Originally Posted by logics
By hypothesis, $\displaystyle \textbook{PA} \vdash (\text{Prb}_\TEXT{PA} \sigma \leftrightarrow \sigma)$.

We see that if $\displaystyle \textbook{PA} \vdash (\text{Prb}_\TEXT{PA} \sigma \rightarrow \sigma)$, then, $\displaystyle \text{PA} \vdash \sigma$ by Löb's Theorem.

I agree.

Quote:

Originally Posted by logics
Further, if $\displaystyle \textbook{PA} \vdash (\sigma \rightarrow \text{Prb}_\TEXT{PA} \sigma)}$, then we claim that $\displaystyle \text{PA} \vdash \sigma$. Suppose to the contrary that $\displaystyle \text{PA} \not\vdash \sigma$. Then $\displaystyle \textbook{PA} \not\vdash \text{Prb}_\text{PA} \sigma}$ by the choice of $\displaystyle \sigma$

To conclude this, you need $\displaystyle \textbook{PA} \vdash (\text{Prb}_\TEXT{PA} \sigma \rightarrow \sigma)$.

Quote:

Originally Posted by logics
which follows that $\displaystyle \textbook{PA} \not\vdash (\sigma \rightarrow \text{Prb}_\TEXT{PA} \sigma)}$.

It is important that $\displaystyle T\not\vdash B$ does not imply $\displaystyle T\not\vdash A\to B$. For example, if $\displaystyle T$ is consistent, then $\displaystyle T\not\vdash\bot$, but $\displaystyle T\vdash\bot\to\bot$.