Results 1 to 9 of 9

Math Help - Enderton 3.1 problem 1 (p.193)

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Enderton 3.1 problem 1 (p.193)

    Let A_S^* be the set of sentences consisting of S1, S2, and all sentences of the form

    \phi(0) \rightarrow \forall v_1(\phi(v_1) \rightarrow \phi(Sv_1)) \rightarrow \forall v_1 \phi(v_1),

    where \phi is a wff (in the language of N_S) in which no variable except v_1 occurs free. Show that A_S \subseteq \text{Cn }A_S^*. Conclude that \text{Cn }A_S^* = \text{Th }N_S. (Here \phi(t) is by definition \phi_t^{v_1}. The sentence displayed above is called the induction axiom for \phi.)

    The necessary definitions can be found here (especially, page 2, slide 7).

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

    We show that if \psi \in A_S, then \psi \in \text{Cn }A_S^*. Therefore, we show each S1, S2, S3, S4.1, S4.2 \ldots, S4.n is a sentence in \text{Cn }A_S^*. If \psi = S1 (resp. S2), \psi \in \text{Cn }A_S^* by assumption.

    S3 asserts that any nonzero number is the successor of somthing.

    How do I show that each S3, S4.1, S4.2, ... , and S4.n is a sentence in \text{Cn }A_S^*?

    From there, how do I conclude \text{Cn }A_S^* = \text{Th }N_S?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Enderton 3.1 problem 1 (p.193)

    The sentence schema you're given is the definition of the principle of finite induction. It should be sufficient to derive the other axioms from the first two and induction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Enderton 3.1 problem 1 (p.193)

    If T is a set of sentences, is Cn T the set of all sentences that can be derived from T?

    Quote Originally Posted by Annatala View Post
    The sentence schema you're given is the definition of the principle of finite induction. It should be sufficient to derive the other axioms from the first two and induction.
    Yes. Usually it is sufficient to write the proofs informally. The study of first-order logic is supposed to convince one that reasonably detailed informal proofs cab be converted to formal derivations. Just write carefully the induction statement (i.e., the property P(n) such that you need to prove \forall n\,P(n)), the base case, the induction hypothesis, etc. Let us know about the concrete difficulties you are having.

    Quote Originally Posted by logics View Post
    From there, how do I conclude \text{Cn }A_S^* = \text{Th }N_S?
    If my assumption about Cn above is true, then for any sets T, S, if T\subseteq\mathop{\mathrm{Cn}} S, then \mathop{\mathrm{Cn}} T\subseteq\mathop{\mathrm{Cn}} S. So, \mathop{\mathrm{Cn}} A_S\subseteq\mathop{\mathrm{Cn}} A^*_S. Also, \mathop{\mathrm{Cn}} A^*_S is satisfiable, so you can use the reasoning of the theorem on slide 11.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.1 problem 1 (p.193)

    Quote Originally Posted by Annatala View Post
    The sentence schema you're given is the definition of the principle of finite induction. It should be sufficient to derive the other axioms from the first two and induction.
    I don't understand what you mean by that.

    For example, how do you show that S3 is a sentence in \text{Cn }A_S^* by using the first two and induction?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.1 problem 1 (p.193)

    The set of consequences of \Sigma, \text{Cn }\Sigma, is defined as

    \text{Cn }\Sigma = \{\sigma | \Sigma \models \sigma\}=\text{Th Mod }\Sigma.

    In the textbook, we have \text{Cn }A_S = \text{Th }N_S .

    I have not figured out how to prove the first part yet, i.e., A_S \subseteq \text{Cn }A_S^*.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Enderton 3.1 problem 1 (p.193)

    Quote Originally Posted by logics View Post
    For example, how do you show that S3 is a sentence in \text{Cn }A_S^* by using the first two and induction?
    Induction here implies that the only objects in the universe are the ones you can get to through successor, so you do it like this:

    Take the property "this object is either zero, or is the successor of some number x". You would agree this is S3 I hope. Well, induction is easy:

    1) Zero meets this property. (base)
    2) For any number y, if y meets this property, then Sy meets this property. (inductive step)
    3) By FPI, all objects meet this property.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.1 problem 1 (p.193)

    Quote Originally Posted by Annatala View Post
    Induction here implies that the only objects in the universe are the ones you can get to through successor, so you do it like this:

    Take the property "this object is either zero, or is the successor of some number x". You would agree this is S3 I hope. Well, induction is easy:

    1) Zero meets this property. (base)
    2) For any number y, if y meets this property, then Sy meets this property. (inductive step)
    3) By FPI, all objects meet this property.

    I don't think your 2) is the inductive hypothesis. Your 2) is basically what we need to prove.

    Do you mean

    \forall y_1(y_1 \neq 0 \rightarrow \exists x\text{ } y_1=Sx) \rightarrow \forall y_1(Sy_1 \neq 0\rightarrow \exists x \text{ } Sy_1 = Sx) \in \text{Cn }A_S^*, where
    \forall y_1(y_1 \neq 0 \rightarrow \exists x \text{ } y_1=Sx) \in \text{Cn }A_S^* is the inductive hypothesis?

    How do you prove this?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Enderton 3.1 problem 1 (p.193)

    Quote Originally Posted by logics View Post
    I don't think your 2) is the inductive hypothesis. Your 2) is basically what we need to prove.

    Do you mean

    \forall y_1(y_1 \neq 0 \rightarrow \exists x\text{ } y_1=Sx) \rightarrow \forall y_1(Sy_1 \neq 0\rightarrow \exists x \text{ } Sy_1 = Sx) \in \text{Cn }A_S^*, where
    \forall y_1(y_1 \neq 0 \rightarrow \exists x \text{ } y_1=Sx) \in \text{Cn }A_S^* is the inductive hypothesis?

    How do you prove this?
    No, my approach is correct: I was trying to lead you there without going all the way.

    You're allowed to assume all sentences of the form:

    \phi(0) \rightarrow \forall v_1(\phi(v_1) \rightarrow \phi(Sv_1)) \rightarrow \forall v_1 \phi(v_1)

    Before we begin the induction, we define \phi_0 \leftrightarrow (\exists x,y (x = 0 \vee x = Sy)) and plug it into the sentence for \phi.

    Using the above sentence, we can prove \phi_0 holds for zero. We can also prove that if it holds for some number, it holds for the successor of that number (because of how we defined \phi_0 this is always true). Based on the expression above, this means \forall v_1 \phi_0(v_1): every number is either zero or a successor. But this is exactly what we wished to show.

    Does that help? :) Try the others on your own if you get it now.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Enderton 3.1 problem 1 (p.193)

    Quote Originally Posted by Annatala View Post
    Take the property "this object is either zero, or is the successor of some number x". You would agree this is S3 I hope. Well, induction is easy:

    1) Zero meets this property. (base)
    2) For any number y, if y meets this property, then Sy meets this property. (inductive step)
    3) By FPI, all objects meet this property.
    Quote Originally Posted by logics View Post
    I don't think your 2) is the inductive hypothesis. Your 2) is basically what we need to prove.
    That's why I said:
    Quote Originally Posted by emakarov View Post
    Just write carefully the induction statement (i.e., the property P(n) such that you need to prove \forall n\,P(n)), the base case, the induction hypothesis, etc.
    You need to prove \forall y\,(y \ne 0\to\exists x\,y = Sx). Removing the universal quantifier, we are left with the property P(y)\stackrel{\text{def}}{=}y \ne 0\to\exists x\,y = Sx. This is the property you prove by induction, which is also the induction hypothesis in the case of regular (weak) induction. As has been said, in simple cases the induction statement is obtained just by removing the universal quantifier from the statement one has to prove. In more complex cases one needs to strengthen the property to make the induction step go through. In the case of strong induction, the induction hypothesis is \forall z\,(z<y\to P(z)).

    For a procedure to create a proof by induction, see this post.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enderton 3.7 Problem 1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 14th 2012, 09:55 AM
  2. Enderton 3.7 Problem 2
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 14th 2012, 08:32 AM
  3. Enderton 3.4 Problem 1
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 24th 2011, 06:17 AM
  4. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 19th 2011, 07:34 AM
  5. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 05:46 AM

Search Tags


/mathhelpforum @mathhelpforum