# If a unary relation is partially recursive, then so is its running total

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

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