Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
What is lower case p? and why did we introduce k? And I do not understand the difference for < vs. <= with modifying above proof. Can you please illustrate? Thanks – Buddy Holly Jan 31 '13 at 9:12
$p$, as explained, is the characteristic function of $P$. I've filled in a few more details. – Peter Smith Jan 31 '13 at 14:29
Thank you, but I dont see what to do with the question I am asking regarding <. Do I need to use induction? I need help in filling in the gaps. – Buddy Holly Feb 1 '13 at 1:00
I also make the convention that 1 is a success and 0 isn't. So does the above version now look good with my edit if I follow this convention? – Buddy Holly Feb 1 '13 at 8:57
@BuddyHolly Yes, by duality, the universal case (with "1" the value true for the caracteristic function) will look like the existential case (with the old traditional choice of "0" as the value true for the caracteristic function). But it would be a bit unhappy to change the definition of a characteristic function between the two cases you are asked to prove! – Peter Smith Feb 1 '13 at 9:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.