Let h(x) be the integer n such that $n \leq \sqrt2 < n+1$ Show that h(x) is primitive recursive.

I know how primitive recursive functions are defined, but showing an integer is primitive recursive is throwing me off. I need some help starting the proof.

  • $\begingroup$ I don't understand what you mean by $n \geq \sqrt2 < n+1$. Do you mean $n \geq \sqrt{2}$ and $n+1 > \sqrt{2}$? $\endgroup$ – fade2black Nov 21 '17 at 5:03
  • $\begingroup$ That was a typo - edited the question $\endgroup$ – mandib Nov 21 '17 at 5:05

This relation can be written as $$n \leq \sqrt{2} \text{ and } n+1 > \sqrt{2}$$ or equivalently $$ ((n^2 < 2) \text{ or } (n^2 = 2)) \text{ and } ((n+1)^2 > 2)$$ In terms of functions $$h(n) = and[or[ls(sqr(n),2), eq(sqr(n),2)], gr(sqr(n+1),2)]$$ So, we have exponentiation (squaring), increment by $1$ (i.e. $n+1$), less than, equal to, greater than, conjunction, and disjunction. They are all primitive recursive whose composition result in the primitive recursive predicate $h(n)$ equal to $1$ if $n \leq \sqrt{2} \text{ and } n+1 > \sqrt{2}$, and $0$ otherwise.

On @chi's hint:

In fact this predicate is true for only $n=1$. So this predicate is drastically simplified and takes the following form $$h(n)=eq(1,n)$$

  • 1
    $\begingroup$ What about h(n) = eq(1,n) ? $\endgroup$ – chi Nov 21 '17 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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