6
$\begingroup$

We can define prime numbers by the following formula in the language of arithmetic: $$P(x):= x>1 \land \forall y< x(\exists z\leq x(y\cdot z =x)\to y=1) $$

This formula is $\Delta_0$ and its properties can be proved in strong enough systems of arithmetic, but in some sub intuitionistic theories of arithmetic properties of this formula can not be proven. By AKS algorithm prime numbers are $\Delta^b_1$ definable in the language of bounded arithmetics (Actually these numbers are polynomial time decidable). My question is about the complexity of defining prime numbers in the language of arithmetic.

Q1. Is there any $E_1$ formula for defining prime numbers?

Q2. Is there any $E^+_1$ formula for defining prime numbers?

$E^+_1$ formulas are $E_1$ formulas which do not have implication or negation.

$\endgroup$
6
  • $\begingroup$ @BjørnKjos-Hanssen: $\psi$ is an $E_1$ formula iff $\psi := \exists x_1<t_1\exists x_2<t_2...\exists x_n<t_n\phi(x_1,...,x_n)$ such that $\phi(x_1,...,x_n)$ be quantifier free. $\endgroup$ May 14, 2017 at 19:54
  • $\begingroup$ I'm still a bit confused: isn't implication just a hidden universal quantifier? $\endgroup$
    – fedja
    May 14, 2017 at 21:58
  • $\begingroup$ @fedja: Yes, They are alike. What part of my question make you confused? $\endgroup$ May 15, 2017 at 5:15
  • $\begingroup$ Q1 was answered already at mathoverflow.net/questions/106409/… $\endgroup$ May 15, 2017 at 6:41
  • $\begingroup$ Since inequality is definable by an $E_1^+$ formula, Q1 and Q2 are equivalent. $\endgroup$ May 15, 2017 at 8:17

0