Recursive relation and predicate If we let P(x,y) be a primitive recursive relation and g(x) be a primitive recursive function. Then how to show that there exists a y < g(x)*P(x,y) is a primitive recursive relation?
And how can we handle for the vase of all y < g(x)*P(x,y) is also a primitive recursive relation?
 A: Suppose you want to show the characteristic function of the property $H$ is p.r., where 

$$H(x) \leftrightarrow (\exists y < g(x))P(x, y).$$

We'll define characteristic functions as do Gödel, Kleene and many others, so that $h$ is the characteristic function of $H$ iff $h(n) = 0$ when $H(n)$ and $h(n) = 1$ otherwise. [If you follow the modern habit of making 1 the value 'true' for characteristic functions, then you'll have to make adjustments accordingly.]
Let $p(x, y)$ be the characteristic function of the relation $P(x, y)$. And assume for the moment $g(x) > 0$. Then consider the product

$$h(x) = p(x, 0) \cdot p(x, 1) \cdot p(x, 2) \cdot \ldots \cdot p(x, \{g(x)-1\})$$

This product is zero iff at least one of the terms on the right is zero, iff for some $y < g(x)$ $p(x, y) = 0$, i.e. iff for some $y < g(x)$, $P(x, y)$. So $h$ is indeed the desired characteristic function of $H$. 
So we just need to define $h(x)$ to make it equal that product, when $g(x) > 0$ and $h(x) = 1$ otherwise! One step at a time. First define $k$ so that it is p.r. and 
$$k(x, y) = p(x, 0) \cdot p(x, 1) \cdot p(x, 2) \cdot \ldots \cdot p(x, y)$$
and then put

$$h(x) = 1\quad\mathrm{if\ } g(x) = 0$$
  $$h(x) = k(x, \{g(x) - 1\})\quad\mathrm{otherwise}$$ 

If we can show $k$ is p.r., then since (by hypothesis) so is $g(x)$, $h$ will be p.r. by definition by cases and composition.
But we have
$$k(x, 0) = p(x, 0)$$
$$k(x, Sy) = k(x, y) \times p(x, Sy)$$
So $k$ will indeed have the right values and is shown to be p.r., given $p$ is p.r. So we are done.
That leaves the other half of the question (for the bounded universal rather than the bounded existential), which is proved similarly.
