# How to write this in first order peano arithmetic

• Jul 1st 2011, 01:22 AM
ikurwae89
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 :)(Rofl)
• Jul 1st 2011, 02:49 AM
emakarov
Re: How to write this in first order peano arithmetic
Quote:

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.

Quote:

(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.
• Jul 1st 2011, 10:49 PM
ikurwae89
Re: How to write this in first order peano arithmetic
(Ep)(Ev1)(P(v1)^P(p)-->(v1=p*p+p+1)))

??
• Jul 2nd 2011, 06:33 AM
emakarov
Re: How to write this in first order peano arithmetic
Quote:

Originally Posted by emakarov
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) → ...)".
• Jul 3rd 2011, 01:30 PM
MoeBlee
Re: How to write this in first order peano arithmetic
Quote:

Originally Posted by ikurwae89
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).
• Jul 3rd 2011, 01:55 PM
emakarov
Re: How to write this in first order peano arithmetic
Quote:

Originally Posted by MoeBlee
P(v1) & Ep(P(p) & v1 = p^(2+p+1))

The original question used p^2+p+1 rather than p^(2+p+1).
• Jul 3rd 2011, 02:23 PM
MoeBlee
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)