Results 1 to 9 of 9

Thread: Enderton 3.5 Problem 2

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Enderton 3.5 Problem 2

    Let $\displaystyle A$ be a recursive set of sentences in a recursively numbered language with $\displaystyle \bold{0}$ and $\displaystyle \bold{S}$. Assume that every recursive relation is representable in the theory $\displaystyle \text{Cn }A$. Further assume that $\displaystyle A$ is $\displaystyle \omega$-consistent; i.e., there is no formula $\displaystyle \phi$ such that $\displaystyle A \vdash \exists x \phi(x)$ and for all $\displaystyle a \in \mathbb{N}$, $\displaystyle A \vdash \neg \phi(\bold{S}^a\bold{0})$. Construct a sentence $\displaystyle \sigma$ indirectly asserting that it is not a theorem of $\displaystyle A$, and show that neither $\displaystyle A \vdash \sigma$ nor $\displaystyle A \vdash \neg \sigma$.

    =====================
    (Suggestion: See Section 3.0.)
    Remark: This is a version of the incompleteness theorem that is closer to Gödel's original 1931 argument. Note that there is no requirement that the axioms $\displaystyle A$ be $\displaystyle true$ in $\displaystyle N=(\mathbb{N}; 0, S, <, +, \cdot, E)$. Nor is it required that $\displaystyle A$ include $\displaystyle A_E$; the fixed point argument can still be applied.
    ======================

    If $\displaystyle \sigma$ says that it is not a theorem of $\displaystyle A$, then it is clear that $\displaystyle A \not\vdash \sigma$. How do I also show $\displaystyle A \not\vdash \neg\sigma$?

    Another question is why $\displaystyle \omega$-consistent is considered here?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.5 Problem 2

    Could you check if my following attempt is O.K ?

    Since every recursive relation is representable in the theory $\displaystyle \text{Cn }A$ by assumption, there is a formula $\displaystyle \rho$ represents $\displaystyle R$ corresponding to $\displaystyle A$ in the theory $\displaystyle \text{Cn }A$ (Enderton 2nd edition, pp 185).

    Let $\displaystyle q$ be the Gödel number of $\displaystyle \forall \neg \rho(v_1, v_1, v_3)$.
    Let $\displaystyle \sigma$ be $\displaystyle \forall v_3 \neg \rho(S^q0}, S^q0, v_3)$.

    Then, $\displaystyle \sigma$ says that no number is the value of $\displaystyle g$ (Enderton 2nd edition, pp 185) at a deduction of $\displaystyle \sigma$.

    If $\displaystyle A \vdash \sigma$, there is a contradiction explained in the textbook (Enderton 2nd edition, pp 185).

    Therefore, we have $\displaystyle A \not \vdash \sigma$.

    Now, we need to show that $\displaystyle A \not \vdash \neg \sigma$.
    Suppose to the contrary that $\displaystyle A \vdash \neg \sigma$.
    Then, $\displaystyle A \vdash \exists v_3 \rho(S^q0}, S^q0, v_3)$.

    By $\displaystyle \omega$-consistency, it cannot be $\displaystyle A \vdash \neg \rho(S^q0}, S^q0, S^a0)$ for all $\displaystyle a \in \mathbb{N}$. It follows that it cannot be $\displaystyle <q, q, k> \notin R$ for every $\displaystyle k$. Now, $\displaystyle \not\models_N \forall v_3 \neg \rho (S^q0, S^q0, v_3)$. It means $\displaystyle \sigma$ is false in $\displaystyle N$, contradicting that $\displaystyle \sigma$ is true in $\displaystyle N$ (Enderton 2nd edition, pp 185).

    Thus $\displaystyle A \not \vdash \neg \sigma$.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Enderton 3.5 Problem 2

    Quote Originally Posted by logics View Post
    Since every recursive relation is representable in the theory $\displaystyle \text{Cn }A$ by assumption, there is a formula $\displaystyle \rho$ represents $\displaystyle R$ corresponding to $\displaystyle A$ in the theory $\displaystyle \text{Cn }A$ (Enderton 2nd edition, pp 185).
    Without the book, it is unclear what exactly the relation "$\displaystyle R$ corresponding to $\displaystyle A$ in the theory $\displaystyle \text{Cn }A$" is. (Fortunately, I was able to get the book.)

    Quote Originally Posted by logics View Post
    Now, $\displaystyle \not\models_N \forall v_3 \neg \rho (S^q0, S^q0, v_3)$. It means $\displaystyle \sigma$ is false in $\displaystyle N$, contradicting that $\displaystyle \sigma$ is true in $\displaystyle N$ (Enderton 2nd edition, pp 185).
    Where is the assumption that $\displaystyle \sigma$ is true in $\displaystyle N$? The assumption is that $\displaystyle A \vdash \neg \sigma$. Even if A is true in the natural model, that would mean that $\displaystyle \sigma$ is false. However, the hint says that A does not have to be true. In fact, the language of A may include, along with 0 and S, other functional and predicate symbols, and it may not be clear how to interpret them.

    I would also prefer to assume the fixpoint theorem for A as the hint seems to imply. The first proof in Section 3.0 of the book (the self-reference approach) seems to incorporate the proof of the fixpoint property, which is quite technical and nonintuitive. It may not be hard to finish your current approach, but I would start as follows. Let us write $\displaystyle \bar{n}$ for $\displaystyle S^n0$. The relation R(x, y) saying that x is a derivation of y is recursive, therefore, representable in A by some formula $\displaystyle \rho$. By the fixpoint property, there exists a formula $\displaystyle \sigma$ such that

    $\displaystyle A\vdash\sigma\leftrightarrow\neg\exists x\,\rho(x,\overline{\sharp\sigma})$ (*)

    Suppose $\displaystyle A\vdash\sigma$. This means that $\displaystyle R(n,\sharp\sigma)$ holds, so...

    Suppose that $\displaystyle A\vdash\neg\sigma$. Then $\displaystyle A\vdash\exists x\,\rho(x,\overline{\sharp\sigma})$ by (*), so, as you wrote, by $\displaystyle \omega$-consistency we have $\displaystyle A\not\vdash\neg\rho(\bar{n},\overline{\sharp\sigma })$ for some n. Therefore, ...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.5 Problem 2

    Quote Originally Posted by emakarov View Post
    Suppose that $\displaystyle A\vdash\neg\sigma$. Then $\displaystyle A\vdash\exists x\,\rho(x,\overline{\sharp\sigma})$ by (*), so, as you wrote, by $\displaystyle \omega$-consistency we have $\displaystyle A\not\vdash\neg\rho(\bar{n},\overline{\sharp\sigma })$ for some n. Therefore, ...
    I am trying to conclude from the above. Is the following O.K?

    Suppose that $\displaystyle A\vdash\neg\sigma$. Then, $\displaystyle \sigma \notin \text{Cn A}$ by the assumption that every recursive relation is representable (i.e., numeralwise determined) in the theory $\displaystyle \text{Cn }A$.
    It follows that $\displaystyle A \vdash \neg \exists x \rho(x, \overline{\sharp \sigma})$. Then $\displaystyle A \vdash \sigma$ by (*). It implies that $\displaystyle \sigma \in \text{Cn }A$, contradiction.

    Thus $\displaystyle A\not\vdash\neg\sigma$.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Enderton 3.5 Problem 2

    Quote Originally Posted by logics View Post
    Suppose that $\displaystyle A\vdash\neg\sigma$. Then, $\displaystyle \sigma \notin \text{Cn A}$ by the assumption that every recursive relation is representable (i.e., numeralwise determined) in the theory $\displaystyle \text{Cn }A$.
    For which exactly formula do you use the fact that it is numeralwise determined and how does it help show that $\displaystyle A\not\vdash\sigma$? I would say that if $\displaystyle A\vdash\sigma$, then the assumption $\displaystyle A\vdash\neg\sigma$ makes A inconsistent, but ω-consistency is stronger than simple consistency.

    Quote Originally Posted by logics View Post
    It follows that $\displaystyle A \vdash \neg \exists x \rho(x, \overline{\sharp \sigma})$.
    Could you explain how it follows? And where do you use ω-consistency?

    Continuing your proof, $\displaystyle A\not\vdash\sigma$ means that no number n is the code of a derivation of $\displaystyle \sigma$, i.e., $\displaystyle R(n,\sharp\sigma)$ is false for all n. Since $\displaystyle \rho$ represents R, we have $\displaystyle A\vdash\neg\rho(\bar{n},\overline{\sharp\sigma})$ for all n. Now use ω-consistency and (*).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.5 Problem 2

    Quote Originally Posted by emakarov View Post
    For which exactly formula do you use the fact that it is numeralwise determined and how does it help show that $\displaystyle A\not\vdash\sigma$?
    I used Theorem 33E and definition in page 207 to denote that either $\displaystyle \sigma \in \text{Cn A}$ or $\displaystyle \sigma \notin \text{Cn A}$. Is this wrong?
    Follow Math Help Forum on Facebook and Google+

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

    Re: Enderton 3.5 Problem 2

    Quote Originally Posted by logics View Post
    I used Theorem 33E and definition in page 207 to denote that either $\displaystyle \sigma \in \text{Cn A}$ or $\displaystyle \sigma \notin \text{Cn A}$.
    Of course, for any set S and object x at all, either $\displaystyle x\in S$ or $\displaystyle x\notin S$. I am still not sure how you concluded $\displaystyle \sigma\notin\mathop{\mathrm{Cn}}A$ from $\displaystyle \neg\sigma\in\mathop{\mathrm{Cn}}A$ in the following text.

    Quote Originally Posted by logics View Post
    Suppose that $\displaystyle A\vdash\neg\sigma$. Then, $\displaystyle \sigma \notin \text{Cn A}$ by the assumption that every recursive relation is representable (i.e., numeralwise determined) in the theory $\displaystyle \text{Cn }A$.
    Which formula and relation did you use with Theorem 33E and definition in page 207?

    For any theory A and a formula $\displaystyle \sigma$, there are four statements:

    (1) $\displaystyle A\vdash\sigma$
    (2) $\displaystyle A\not\vdash\neg\sigma$
    (3) $\displaystyle A\vdash\neg\sigma$
    (4) $\displaystyle A\not\vdash\sigma$

    In any case, precisely one of (1) and (4), as well as one of (2) and (3) holds. If A is inconsistent, then A derives everything, i.e., (1) and (3) are true and (2) and (4) are false. If A is consistent, then (1) implies (2) and (3) implies (4), but the converse implications are in general false.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.5 Problem 2

    For any theory A and a formula $\displaystyle \sigma$, there are four statements:

    (1) $\displaystyle A\vdash\sigma$
    (2) $\displaystyle A\not\vdash\neg\sigma$
    (3) $\displaystyle A\vdash\neg\sigma$
    (4) $\displaystyle A\not\vdash\sigma$

    In any case, precisely one of (1) and (4), as well as one of (2) and (3) holds. If A is inconsistent, then A derives everything, i.e., (1) and (3) are true and (2) and (4) are false. If A is consistent, then (1) implies (2) and (3) implies (4), but the converse implications are in general false.
    A is $\displaystyle \omega$-consistent by assumption, so it is consistent.

    $\displaystyle A\vdash\sigma\leftrightarrow\neg\exists x\,\rho(x,\overline{\sharp\sigma})$ (*)
    What conditions are required to apply the fixed point lemma to A instead of $\displaystyle A_E$?

    The below one is my updated proof based on the textbook page 266.

    To express $\displaystyle A \vdash \sigma$ for a sentence $\displaystyle \sigma$, we define

    $\displaystyle \text{Prb}_A\sigma = \exists v_2 \pi(S^{\sharp\sigma}0, v_2)$,

    where $\displaystyle \pi(v_1, v_2)$ numeralwise represents the binary relation (a, d) in $\displaystyle A_E$. (referred to textbook page 206 for the corresponding description including the binary relation).

    (Enderton, Page 266)

    (*) Whenever $\displaystyle A \vdash \sigma$, then $\displaystyle A_E \vdash \text{Prb}_A\sigma$.

    (**) $\displaystyle A_E \vdash (\sigma \leftrightarrow \neg\text{Prb}_A\sigma)$ (by Fixed Point lemma).


    Since $\displaystyle A$ itself is a recursively axiomatizable theory,

    (***) If $\displaystyle A \vdash \sigma$, then $\displaystyle A_E \vdash \sigma$.

    (****) If $\displaystyle A \vdash \neg\sigma$, then $\displaystyle A_E \vdash \neg\sigma$.

    Now, suppose $\displaystyle A \vdash \sigma$. Then, $\displaystyle A_E \vdash \sigma$ and $\displaystyle A_E \vdash \text{Prb}_A\sigma$ by (*) and (***). We also have $\displaystyle A_E \vdash \neg\sigma$ by (**), contradicting that $\displaystyle \text{Cn }A_E$ is consistent. Therefore, $\displaystyle A \not\vdash \sigma$.

    Suppose $\displaystyle A \vdash \neg\sigma$. Then, $\displaystyle A_E \vdash \neg\sigma$. It follows that $\displaystyle A_E \not\vdash \sigma$ (by consistency of $\displaystyle \text{Cn }A_E$), which implies that $\displaystyle A_E \vdash \neg \text{Prb}_A\sigma$ (by $\displaystyle \omega$-consistency of $\displaystyle A$). Then, $\displaystyle A_E \vdash \sigma$, contradicting that $\displaystyle \text{Cn }A_E$ is consistent. Therefore, $\displaystyle A \not\vdash \neg\sigma$.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Enderton 3.5 Problem 2

    Quote Originally Posted by logics View Post
    What conditions are required to apply the fixed point lemma to A instead of $\displaystyle A_E$?
    Good question. Hopefully, the fact that every recursive relation is representable is sufficient, but one has to go over the proof of fixpoint lemma and verify it.

    Quote Originally Posted by logics View Post
    Since $\displaystyle A$ itself is a recursively axiomatizable theory,

    (***) If $\displaystyle A \vdash \sigma$, then $\displaystyle A_E \vdash \sigma$.

    (****) If $\displaystyle A \vdash \neg\sigma$, then $\displaystyle A_E \vdash \neg\sigma$.
    This is not correct because A may have functional and predicate symbols that are outside the language of $\displaystyle A_E$. It may also have additional axioms. If you want to interpret A in $\displaystyle A_E$, you need to resort to encoding. That's why (and also because A is ω-consistent, which we have to use somehow) I suggest assuming the fixpoint lemma for A. Then it is not necessary to consider $\displaystyle A_E$ at all because by assumption A represents every recursive relation. In particular, there exists a formula $\displaystyle \pi$ representing the relation R(d, a) expressing "d is a derivation of a" in A.

    The fact that $\displaystyle A\vdash\phi$ implies $\displaystyle A\vdash\mathop{\mbox{Prb}}\phi$ for any formula $\displaystyle \phi$ can be easily adapted from $\displaystyle A_E$ to A. This covers the case when $\displaystyle A\vdash\sigma$.

    Quote Originally Posted by logics View Post
    Suppose $\displaystyle A \vdash \neg\sigma$. Then, $\displaystyle A_E \vdash \neg\sigma$. It follows that $\displaystyle A_E \not\vdash \sigma$ (by consistency of $\displaystyle \text{Cn }A_E$), which implies that $\displaystyle A_E \vdash \neg \text{Prb}_A\sigma$ (by $\displaystyle \omega$-consistency of $\displaystyle A$).
    I don't see how ω-consistency implies that $\displaystyle A_E \vdash \neg \text{Prb}_A\sigma$. At most, it says that $\displaystyle A_E \not\vdash \text{Prb}_A\sigma$. This inference also requires (replacing $\displaystyle A_E$ with A) the assumption that $\displaystyle \pi$ represents R and deserves to be written in more detail. It is sufficient to finish the proof because $\displaystyle A\vdash\neg\sigma$ implies $\displaystyle A\vdash\mathop{\mbox{Prb}}\sigma$ by the fixpoint lemma. Thus, the contradiction in the case when $\displaystyle A \vdash \neg\sigma$ comes from the fact that $\displaystyle A\vdash\phi$ and $\displaystyle A\not\vdash\phi$ for some formula $\displaystyle \phi$, not from $\displaystyle A\vdash\phi$, $\displaystyle A\vdash\neg\phi$ and consistency.
    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