Results 1 to 9 of 9

Math Help - Enderton 3.5 Problem 2

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Enderton 3.5 Problem 2

    Let A be a recursive set of sentences in a recursively numbered language with \bold{0} and \bold{S}. Assume that every recursive relation is representable in the theory \text{Cn }A. Further assume that A is \omega-consistent; i.e., there is no formula \phi such that A \vdash \exists x \phi(x) and for all a \in \mathbb{N}, A \vdash \neg \phi(\bold{S}^a\bold{0}). Construct a sentence \sigma indirectly asserting that it is not a theorem of A, and show that neither A \vdash \sigma nor 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 A be true in N=(\mathbb{N}; 0, S, <, +, \cdot, E). Nor is it required that A include A_E; the fixed point argument can still be applied.
    ======================

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

    Another question is why \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 \text{Cn }A by assumption, there is a formula \rho represents R corresponding to A in the theory \text{Cn }A (Enderton 2nd edition, pp 185).

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

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

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

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

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

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

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

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Enderton 3.5 Problem 2

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

    Quote Originally Posted by logics View Post
    Now, \not\models_N \forall v_3 \neg \rho (S^q0, S^q0, v_3). It means \sigma is false in N, contradicting that \sigma is true in N (Enderton 2nd edition, pp 185).
    Where is the assumption that \sigma is true in N? The assumption is that A \vdash \neg \sigma. Even if A is true in the natural model, that would mean that \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 \bar{n} for S^n0. The relation R(x, y) saying that x is a derivation of y is recursive, therefore, representable in A by some formula \rho. By the fixpoint property, there exists a formula \sigma such that

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

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

    Suppose that A\vdash\neg\sigma. Then A\vdash\exists x\,\rho(x,\overline{\sharp\sigma}) by (*), so, as you wrote, by \omega-consistency we have 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 A\vdash\neg\sigma. Then A\vdash\exists x\,\rho(x,\overline{\sharp\sigma}) by (*), so, as you wrote, by \omega-consistency we have 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 A\vdash\neg\sigma. Then, \sigma \notin \text{Cn A} by the assumption that every recursive relation is representable (i.e., numeralwise determined) in the theory \text{Cn }A.
    It follows that A \vdash \neg \exists x \rho(x, \overline{\sharp \sigma}). Then A \vdash \sigma by (*). It implies that \sigma \in \text{Cn }A, contradiction.

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

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Enderton 3.5 Problem 2

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

    Quote Originally Posted by logics View Post
    It follows that 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, A\not\vdash\sigma means that no number n is the code of a derivation of \sigma, i.e., R(n,\sharp\sigma) is false for all n. Since \rho represents R, we have 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 A\not\vdash\sigma?
    I used Theorem 33E and definition in page 207 to denote that either \sigma \in \text{Cn A} or \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,517
    Thanks
    771

    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 \sigma \in \text{Cn A} or \sigma \notin \text{Cn A}.
    Of course, for any set S and object x at all, either x\in S or x\notin S. I am still not sure how you concluded \sigma\notin\mathop{\mathrm{Cn}}A from \neg\sigma\in\mathop{\mathrm{Cn}}A in the following text.

    Quote Originally Posted by logics View Post
    Suppose that A\vdash\neg\sigma. Then, \sigma \notin \text{Cn A} by the assumption that every recursive relation is representable (i.e., numeralwise determined) in the theory \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 \sigma, there are four statements:

    (1) A\vdash\sigma
    (2) A\not\vdash\neg\sigma
    (3) A\vdash\neg\sigma
    (4) 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 \sigma, there are four statements:

    (1) A\vdash\sigma
    (2) A\not\vdash\neg\sigma
    (3) A\vdash\neg\sigma
    (4) 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 \omega-consistent by assumption, so it is consistent.

    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 A_E?

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

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

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

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

    (Enderton, Page 266)

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

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


    Since A itself is a recursively axiomatizable theory,

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

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

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

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

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    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 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 A itself is a recursively axiomatizable theory,

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

    (****) If A \vdash \neg\sigma, then A_E \vdash \neg\sigma.
    This is not correct because A may have functional and predicate symbols that are outside the language of A_E. It may also have additional axioms. If you want to interpret A in 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 A_E at all because by assumption A represents every recursive relation. In particular, there exists a formula \pi representing the relation R(d, a) expressing "d is a derivation of a" in A.

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

    Quote Originally Posted by logics View Post
    Suppose A \vdash \neg\sigma. Then, A_E \vdash \neg\sigma. It follows that A_E \not\vdash \sigma (by consistency of \text{Cn }A_E), which implies that A_E \vdash \neg \text{Prb}_A\sigma (by \omega-consistency of A).
    I don't see how ω-consistency implies that A_E \vdash \neg \text{Prb}_A\sigma. At most, it says that A_E \not\vdash \text{Prb}_A\sigma. This inference also requires (replacing A_E with A) the assumption that \pi represents R and deserves to be written in more detail. It is sufficient to finish the proof because A\vdash\neg\sigma implies A\vdash\mathop{\mbox{Prb}}\sigma by the fixpoint lemma. Thus, the contradiction in the case when A \vdash \neg\sigma comes from the fact that A\vdash\phi and A\not\vdash\phi for some formula \phi, not from A\vdash\phi, 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: January 5th 2012, 11:49 AM
  2. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 19th 2011, 07:34 AM
  3. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 05:46 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum