Results 1 to 7 of 7

Math Help - How to write this in first order peano arithmetic

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    How to write this in first order peano arithmetic

    v1 is a prime of the form p^2+p+1, where p is prime

    my approach....

    (There exists v1)(P(p)-->(v1=p*P+P+0') )

    it looks too simply, can i get a feedback thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: How to write this in first order peano arithmetic

    v1 is a prime of the form p^2+p+1, where p is prime
    This has to be a formula with one free variable v1.

    (There exists v1)(P(p)-->(v1=p*P+P+0') )
    Here, on the other hand, the only free variable is p. Also, in p*P, it confuses p, which is a number, with P, which is apparently a unary predicate saying that its argument is prime.

    You need to say that (1) there exists some prime p, (2) v1 = p * p + p + 0' and (3) v1 is prime.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    Re: How to write this in first order peano arithmetic

    (Ep)(Ev1)(P(v1)^P(p)-->(v1=p*p+p+1)))

    ??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: How to write this in first order peano arithmetic

    Quote Originally Posted by emakarov View Post
    This has to be a formula with one free variable v1.
    Your formula quantifies over v1, so it is not free. Free variables are a formula's inputs, so to speak.

    In addition, what happens when ∃p chooses a number that is not prime? Then the premise P(v1) ∧ P(p) is false and the formula is automatically true. The English phrase "there exists a p satisfying P such that..." is translated into "∃p (P(p) ∧ ...)", while "for all p satisfying P it is true that..." is translated into "∀p (P(p) → ...)".
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: How to write this in first order peano arithmetic

    Quote Originally Posted by ikurwae89 View Post
    v1 is a prime of the form p^2+p+1, where p is prime
    Let's suppose you've already worked out how to say 'p is prime' with a formula P(p) with only the primitives of the language.

    So

    P(v1) & Ep(P(p) & v1 = p^(2+p+1))

    However, if the exponentiation symbol (^) is not a primitive of your language, then you have to define ^ from the rest of the primitives. That is not a simple matter. Godel first showed how to do it, using the Chinese remainder theorem. (There might be ways to do it without using the Chinese remainder theorem, but that's how it's done ordinarily).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: How to write this in first order peano arithmetic

    Quote Originally Posted by MoeBlee View Post
    P(v1) & Ep(P(p) & v1 = p^(2+p+1))
    The original question used p^2+p+1 rather than p^(2+p+1).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: How to write this in first order peano arithmetic

    Okay, so it's (p^2)+p+1 rather than p^(2+p+1).

    So we don't need the stuff I said about exponentiation. Just:

    P(v1) & Ep(P(p) & v1 = (p*p)+p+1)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 26th 2011, 05:03 AM
  2. Replies: 0
    Last Post: May 26th 2008, 10:16 PM
  3. Express in First Order Peano Arithmetic (FOPA)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 9th 2008, 09:35 PM
  4. More peano arithmetic.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 27th 2006, 08:54 AM
  5. peano arithmetic
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: July 26th 2006, 10:19 PM

Search Tags


/mathhelpforum @mathhelpforum