Enderton 3.7 Problem 1

**logics** · January 14th 2012, 07:10 AM

Let $\sigma$ be a sentence such that

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

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

Does $\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 $\tau$ is any sentence for which $T \vdash (\text{Prb}_T \tau \rightarrow \tau)$ , then $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, $\textbook{PA} \vdash (\text{Prb}_\TEXT{PA} \sigma \leftrightarrow \sigma)$ .

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

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

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

Could you check the above?

Thanks.

**emakarov** · January 14th 2012, 09:55 AM

Originally Posted by logics

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

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

I agree.

Originally Posted by logics

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

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

Originally Posted by logics

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

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

Thread: Enderton 3.7 Problem 1

LinkBack

Thread Tools

Display

Enderton 3.7 Problem 1

Re: Enderton 3.7 Problem 1

Similar Math Help Forum Discussions

Enderton Problem 3.5

Enderton 3.3 Problem 5

Enderton 3.3 Problem 8

Enderton 3.1 problem 1 (p.193)

Enderton 3.1 Problem 6 (p. 193)

Search Tags