How natural numbers can be defined using primitive recursive $\Sigma_0^0$

Question

$$S=\{x\mid (\exists y_1)\cdots (\exists y_r)P(x,y_1,\ldots,y_r)\}, \qquad P \text{ primitive recursive.}$$

I do get how some set of natural numbers (or numbers) can be defined with $\Sigma_1^0$ formula, but I do not get how we can define set of natural numbers with $\Sigma_0^0$ formula - primitive recursive formula.

Also, for the quoted part, can $x$ be bounded - that is, in $P$ can we set $x \in D$ for some set $D$?

Or if I am getting utterly confused, please help me here.

Answer 1

Sets of numbers can be defined using $\Sigma^0_0$ formulae in exactly the same way as $\Sigma^0_1$ (or indeed $\Sigma^0_n$) formulae can be used to define them, as follows. Let $\varphi(x)$ be a formula in one free variable containing only bounded quantifiers.

Then the set $A$ such that for all $n \in \mathbb{N}$, $$n \in A \Leftrightarrow \varphi(n)$$

is a set of natural numbers defined by a primitive recursive formula.

---

Here's an example: the predicate "$n$ is prime". The natural way to express this is "Every factor of $n$ is equal to $1$ or $n$", or formally, $\forall{m} (m \text{ is a factor of } n \rightarrow m = 1 \vee m = n)$. We can express "$m$ is a factor of $n$" as $\exists{k} (k \times m = n)$. Substituting, we get

$$n \text{ is prime } \equiv \forall{m} (\exists{k} (k \times m = n) \rightarrow m = 1 \vee m = n).$$

This is not a $\Sigma^0_0$ formula: in fact it's $\Pi^0_2$. But it is equivalent to a $\Sigma^0_0$ formula, because of the general fact that, for $x, y, z \in \mathbb{N}$ if $x \times y = z$ then $x \leq z$ and $y \leq z$. So we can replace both quantifiers with quantifiers bounded by $n$:

$$n \text{ is prime } \equiv \forall{m \leq n} \, \exists{k \leq n} \, (k \times m = n \rightarrow m = 1 \vee m = n).$$

So the property of being prime is $\Sigma^0_0$, i.e. primitive recursive. Actually we can simplify the above formula slightly to

$$\forall{m < n} \, \exists{k \leq n} \, (k \times m = n \rightarrow m = 1).$$

---

In the final part of your question, you ask

Can $x$ be bounded - that is, in $P$ can we set $x \in D$ for some set $D$?

The answer here is yes, but it's slightly subtle. Suppose $\varphi^D$ is a $\Sigma^0_0$ formula with a parameter for $D$ (we write this as $\Sigma^{0,D}_0$). Then if $D$ is primitive recursive (that is, the domain of a primitive recursive characteristic function) then the set defined by $\varphi^D$ is also $\Sigma^0_0$. But if $D$ is more complicated—$\Sigma^0_n$ for some $n$, say—then the set defined by $\varphi^D$ will also be $\Sigma^0_n$.