- #1
Nono713
Gold Member
MHB
- 615
- 4
I've been asked in an exercise to show that the function $f(n)$ which returns the $n$th prime is a primitive recursive function. We've covered the basics of primitive recursion, the primitive recursive schematic notation, addition, multiplication, limited subtraction, bounded products, sums, quantifiers, bounded search (minimization), and relations/cases. Could someone check over my work, because I'm still not comfortable with how to build these kinds of proofs:
Premises:
- the prime decision function ($p(x) = 0$ if $x$ is not prime, $p(x) = 1$ otherwise) is primitive recursive
- the factorial function and subtraction function are primitive recursive (proved earlier)
Proof:
We first define $f(0) = 2$ (the first prime is $2$) which is a composition of primitive recursive functions (using the successor and zero functions), and is the first prime number. So the base case holds.
Next we assume that $f(n)$ is the $n$th prime number, and we define $f(n + 1)$ as "the least $x$ less than or equal to $f(n)! - f(n)$ such that $x + f(n) + 1$ is prime". From Euclid's proof of the infinitude of primes, which shows there exists a prime between $m$ and $m! + 1$ for any natural number $m$, the above means that $f(n + 1)$ returns the smallest prime in $[ f(n) + 1, f(n)! + 1 ]$, which is the next prime after $f(n)$. Therefore, by induction, $f(n)$ does indeed return the $n$th prime for all $n$.
The expression for $f(n + 1)$ is a (primitive recursive) bounded search, as we search in the interval $[ 0, f(n)! - f(n) ]$ for the least element $x$ which satisfies the primitive recursive relation "$x + f(n) + 1$ is prime", where the interval bounds are finite and are primitive recursive (composed from the zero function and a composition of factorial and subtraction respectively). Therefore $f(n)$ is primitive recursive.
I'm kind of wondering about using bounded search like this to search inside an interval that doesn't start at zero. I feel it is correct since the predicate is still primitive recursive but I'm not sure if it's sufficient justification. What do you guys think?
Premises:
- the prime decision function ($p(x) = 0$ if $x$ is not prime, $p(x) = 1$ otherwise) is primitive recursive
- the factorial function and subtraction function are primitive recursive (proved earlier)
Proof:
We first define $f(0) = 2$ (the first prime is $2$) which is a composition of primitive recursive functions (using the successor and zero functions), and is the first prime number. So the base case holds.
Next we assume that $f(n)$ is the $n$th prime number, and we define $f(n + 1)$ as "the least $x$ less than or equal to $f(n)! - f(n)$ such that $x + f(n) + 1$ is prime". From Euclid's proof of the infinitude of primes, which shows there exists a prime between $m$ and $m! + 1$ for any natural number $m$, the above means that $f(n + 1)$ returns the smallest prime in $[ f(n) + 1, f(n)! + 1 ]$, which is the next prime after $f(n)$. Therefore, by induction, $f(n)$ does indeed return the $n$th prime for all $n$.
The expression for $f(n + 1)$ is a (primitive recursive) bounded search, as we search in the interval $[ 0, f(n)! - f(n) ]$ for the least element $x$ which satisfies the primitive recursive relation "$x + f(n) + 1$ is prime", where the interval bounds are finite and are primitive recursive (composed from the zero function and a composition of factorial and subtraction respectively). Therefore $f(n)$ is primitive recursive.
I'm kind of wondering about using bounded search like this to search inside an interval that doesn't start at zero. I feel it is correct since the predicate is still primitive recursive but I'm not sure if it's sufficient justification. What do you guys think?