Given the following godel coding scheme:
$$\langle a_0,a_1,\ldots,a_{k-1}\rangle\implies 2^k 3^{a_0} 5^{a_1}\cdots\pi(k)^{a_{k-1}}$$
$ \\ $
How does one show that the function $sub(s,c,d)$ that replaces any appearance of the number c in the sequence coded by s with the number d is primitive recursive??
Note: Most of these are from Boolos' "Computability and Logic". It is going to be strongly assumed here that one is familiar with properties of recursive functions and relations. I will define these functions and leave it to the reader to verify they are recursive:
$ \\ $
quo(x,y) to be the quotient of x by y
$$quo(x,y):= \begin{cases} (\xi\ z \leq x) & y*z \leq x & ,y \neq 0 \\ \\ 0 & & ,y = 0 \end{cases} $$
$(\xi\ $ here means the greatest$)$
$\\$
lo(x,y) the highest exponent of y dividing x(in practice, the exponent of y in prime factorization of x
$$lo(x,y):= \begin{cases} (\xi\ z \leq x) & y^z |\, x & x,y>1 \\ \\ 0 & & else \end{cases} $$
$ \\ $
lh(s): length of sequence encoded by s
$$lh(s):= lo(s,2)$$
$ \\ $
ent(s,i): The ith entry in the sequence coded by s
$$ent(s,i) = lo(s,\pi(i+1))$$
$ \\ $
Recursive definition of y divides x
$$y|x \iff \big(\exists z \leq x\big)\ x= y*z$$
$ \\ $
Recursive definition of prime number
$$Prime(y) \iff \ y > 1 \quad \land \quad \big(\forall z \leq y\big)\big(\ z\,|\, y \implies z = y \lor z = 1\big)$$
$ \\ $
nPr(x) the next prime after x (mu means least here)
$$nPr(x):=\big(\mu y \leq x!+1\big)(x < y \ \land \ Prime(y)\big) $$
$ \\ $
PI(n): the nth prime counting 2 as the 0th
$$\pi(0):= 2, \quad \pi(n+1):= nPr(n)$$
$ \\ $
fst(s): 1st (really 0th) entry in the sequence coded by s
$$fst(s):= ent(s,0)$$
sub(s,c,d): sequence obtained by substituting occurrences of c for d in sequence coded by s.
Here we use course of values recursion, have to define an auxiliary function:
$$sub(s,c,d,0):=s$$
$ \\ $
$$ sub(s,c,d,i+1):= \begin{cases} sub(s,c,d,i) & \quad ent(s,i) \neq c \\ \\ quo\bigg(sub(s,c,d,i),nPr(\pi(i))^c\bigg)*nPr(\pi(i))^d & \quad ent(s,i) = c \end{cases} $$
and finally $$sub(s,c,d):= sub(s,c,d,lh(s))$$