Is $\{x \in \mathbb{N}| \mbox{ x is prime}\}$ primitive recursive?
Hello,
$x \in \{x \in \mathbb{N}| \mbox{ x is prime}\} $ if and only if $ \forall y : y \le x \Rightarrow (y=1 \vee y=x \vee \neg (y|x))$
I already know that the union, =, 'dividisble by' is primitive recursive. Now my problem is $\forall y ..$. We already discuss in the lecture that $R=\{(\overline{x},z): \mbox{for all } y<z: (\overline{x},y) \in P\}$ primitive recursive if $P \in \mathbb{N}^n$ is primitive recursive. But the exercise is of an other structure.
Yes, the set of prime numbers is primitive recursive. As you wrote, a number $z$ is prime if and only if there is no $y <z$ with $1 < y$ such that $y$ divides $z$. The set $$\{(y,z) : 1 < y < z \text{ and } y \text{ divides } z\}$$ is primitive recursive, and the set of non-primes is obtained from that set by a bounded quantification. The set of primes is then the complement of the set of non-primes; sometimes a special case is needed to ensure that $1$ is not called prime. So you have all the parts, and only need to assemble them.