Results 1 to 4 of 4

Math Help - Help with using Herbrand's Theorem

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    2

    Help with using Herbrand's Theorem

    I need to prove using Herbrand's Theorem the following. I've tried in a few directions (and solved a few other problems using the theorem), but can't solve this one.

    Any directions will be greatly appreciated!

    Help with using Herbrand's Theorem-logic.jpg
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    Just reproducing the theorem in a larger size:

    (\forall x)(x=0)\vee(\exists y)(x=s(y))
    \vdash(\forall x)((x=0)\vee(x=s(0))\vee(\exists y)(x=s(s(y)))).

    Is that correct?

    Question: does the initial for all x apply to the entire disjunct before the \vdash symbol?

    I'm afraid I can't be of much more use than this. Herbrand's theorem is beyond what I've done in logic.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2010
    Posts
    2

    Fixed question

    (\forall x) ((x=0)\vee(\exists y)(x=s(y)))

    \vdash (\forall x) ((x=0)\vee(x=s(0))\vee(\exists y)(x=s(s(y))))

    Thanks for noting the problem
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    When you say "use Herbrand's theorem" do you mean that you need to perform this proof in some particular kind of sequent calculus?

    Otherwise, in ordinary natural deduction, a proof is easy:

    Suppose x is not 0 nor the successor of 0. Then there is a z such that x is the successor of z. But such z is itself either 0 or a successor. But z can't be 0, since x is not the successor of 0. So let z be the successor of y. So x is the successor of the successor of y. Then fill out the routine quantifer and sentential logic steps to complete the proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. Replies: 3
    Last Post: May 14th 2010, 11:04 PM
  3. Prove Wilson's theorem by Lagrange's theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 10th 2010, 02:07 PM
  4. Replies: 2
    Last Post: April 3rd 2010, 05:41 PM
  5. Replies: 0
    Last Post: November 13th 2009, 06:41 AM

Search Tags


/mathhelpforum @mathhelpforum