Results 1 to 2 of 2

Thread: Enderton 3.7 Problem 1

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Enderton 3.7 Problem 1

    Quote Originally Posted by logics View Post
    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 View Post
    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 View Post
    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$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enderton Problem 3.5
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jan 5th 2012, 11:49 AM
  2. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 19th 2011, 07:34 AM
  3. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 19th 2011, 05:46 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Dec 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum