Thread: How to write this in first order peano arithmetic

1. 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

2. 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.

3. Re: How to write this in first order peano arithmetic

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

??

4. Re: How to write this in first order peano arithmetic

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) → ...)".

5. Re: How to write this in first order peano arithmetic

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).

6. Re: How to write this in first order peano arithmetic

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).

7. 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)