# Showing the predicate $n \leq \sqrt2 < n+1$ is primitive recursive

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.

• 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}$? – fade2black Nov 21 '17 at 5:03
• That was a typo - edited the question – 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.
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)$$
• What about h(n) = eq(1,n) ? – chi Nov 21 '17 at 8:54