I'm having trouble understanding the prime and bounded minimalization which can be used to construct a primitive recursive function pn that enumerates the primes.
(Copied from the textbook "Languages and Machines" by Sudkamp)
Lemma:
Let pn(x) denote the xth prime. Then pn(x+1) <= pn(x)! + 1
The bound provided by the lemma is computed by the primitive recursive function fact(x) + 1.
The xth prime function can be obtained by primitive recursion:
$$ pn(0) = 2 $$
$$ fact(pn(x))+1$$ $$ pn(x+1) = \mu z [prime(z) \bullet gt(z, pn(x))] $$
Note: "fact(pn(x)) + 1" is directly above $\mu z$.
Please help me to understand this definition with examples and how it works, especially with the $\mu$ symbol in this context.
I'm also confused with Godel Numbering for encoding and decoding. Here is the formula that encodes a fixed number of inputs using the definition of Godel numbering. We let this formula be the n+1 variable function which encodes a sequence $x_0, x_1, ..., x_n$. The function $gn_{n-1}$ can be used to encode the components of an ordered n-tuple. The Godel number associated within the ordered pair [x0, x1] is $ gn_1(x0, x1)$.
$$ gn_n(x_0,...,x_n) = pn(0)^{x_0+1},...,pn(n)^{x_n+1} = \prod_{i=0}^n pn(i)^{x_i + 1}$$
Here is the formula that decodes to retrieve the components of the encoded sequence. This function returns the ith element of the sequence encoded in the Godel number x. The bounded $\mu $ operator is used to find the power of pn(i) in the prime decomposition of x.
$$dec (i, x) = \mu z [cosg(divides(x, pn(i)^{z+1}))]\ /1 $$
Note, there is an "x" right above $\mu z$ but I'm unable to write it.
Any example to illustrate the formulas is always helpful. Thank you.