I am studying Recursive Functions and I found online course notes of Stephen Cook. In the notes, I found this very interesting exercise:

Exercise 8   For each unary relation $R(x)$ define the unary function $\#R(x)$ by $$\#R(x) = |\{y\leq x : R(y)\}|$$ where $|S|$ is the number of elements in a set $S$.

(a) Show that if $R$ is primitive recursive, then $\#R$ is primitive recursive.

(b) Let $\pi(x)$ be the number of prime numbers $\leq x$. For example $\pi(6)=3$, since $\{2,3,5\}$ comprise the set of primes $\leq 6$. Prove that $\pi(x)$ is primitive recursive.

I am asking if there is a standard method to prove that $R(y)$ is a primitive recursive relation ($R(y)$ is the set of all numbers less than or equal to $x$).

  • $\begingroup$ I cannot understand your question. Are you asking how to prove part (a)? Try using primitive recursion. $\endgroup$ – Yuval Filmus Nov 12 '19 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.