# Primitive recursive definition of the “divisibility” relation

Let $$d(x,y)= \begin{cases} 1, &\text{if }x\text{ is divisible by }y \\ 0, &\text{otherwise.} \end{cases}$$

How can I define $d(x,y)$ in terms of just the basic primitive recursive functions (zero, successor, identity, projection) and the composition and primitive recursive operations?

-
Review Link: Have you looked at common-primitive-recursive-functions? You'll find an elaborations of the basic primitive functions you refer to, and how, from those, we can obtain limited subtraction...and so forth. The link will take you to some primitive function, including division, but if you scroll to the top, and read from the start, it may shed some insight on how to define divisibility using more primitive functions as "building blocks". –  amWhy Nov 11 '12 at 20:32
I just moved the link & my answer to the "comment" section below your question, and removed it from my answer (since deleted). I simply wanted you to have quick access to it if you want to revisit the post/site in the future. You just get automatically notified if someone "comments" or answers your question. –  amWhy Nov 11 '12 at 22:13

The natural approach would be to define the modulus function $$m(0,y) = 0$$ $$m(x+1,y) = \begin{cases} 0 & \text{if }m(x,y)+1= y \\ m(x,y)+1 &\text{otherwise}\end{cases}$$ Then $d$ is simply $$d(x,y) = \begin{cases} 1 &\text{if }m(y,x)=0 \\ 0 &\text{otherwise}\end{cases}$$

So everything will be easy if you can express $$f(a,b,x,y) = \begin{cases} a & \text{if }x=y \\ b & \text{otherwise} \end{cases}$$ Do you have some components that might be useful for that? For example if you have the restricted subtraction function $(x,y)\mapsto \max(0,x-y)$, you can build $|x-y|$ from that, and then implement $f$ by primitive recursion over the value of $|x-y|$...

-
Oh yes I do have the modified difference function you refer to, but I haven't been able to figure out how to build $d$ from this function. Can you give a hint perhaps? –  Ryan Nov 11 '12 at 18:15
@Ryan: That's what I describe in the answer! –  Henning Makholm Nov 11 '12 at 18:20
@Ryan: Nobody says $d$ itself needs to be defined directly by primitive recursion. In the definition I propose in my answer, it is constructed by composition: $d(x,y)=f(1,0,m(y,x),0)$. –  Henning Makholm Nov 11 '12 at 18:38
@Ryan: Are you reading my answer at all? It (and my previous comment) tells you exactly what to compose. And yes, you do need define some auxiliary functions -- thougn not necessarily the modulus function if you go with Arthur's hint instead. –  Henning Makholm Nov 11 '12 at 19:00
@Ryan: The part of my answer that explains how you can use absolute difference to build $f$ is this "... and then implement $f$ by primitive recursion over the value of $|x-y|$". If you're not allowed to define any auxiliary PR functions (such as modulus) during your solution simply because they are not mentioned in the text, then I think you're screwed. –  Henning Makholm Nov 11 '12 at 19:12

Note, that the following functions are primitive recursive

• the (characteristic function of the) equality predicate $$\mathrm{Eq} (x,y) = \begin{cases} 1, &\text{if }x = y \\ 0, &\text{if }x \neq y; \end{cases}$$
• usual multiplication of natural numbers.

Note, also, that if $f(x,\vec{u})$ is a primitive recursive function, then so is the function $y \mapsto \sum_{x\leq y} f(x,\vec{u})$.

Using this we can define the divisibility predicate by $$d ( x , y ) = \textstyle{\sum_{z \leq x}} \mathrm{Eq} ( y \cdot z , x ).$$ (In actual fact, this equation is not that cryptic. Note that if $\chi(y,\vec{x})$ is the characteristic function of some predicate, then $\sum_{y \leq z} \chi(y,\vec{x})$ will be positive iff $\chi(y,\vec{x}) = 1$ for some $y \leq z$, and so $\min \{ 1 , \sum_{y \leq z} \chi(y,\vec{x}) \}$ will be the characteristic function for the predicate "$(\exists y \leq z) ( \chi(y,\vec{x}))$." Since given $x,y$ there is at most one $z \leq x$ such that $y \cdot z = x$, we can dispense with the "$\min$" in this specific case. The right-hand-side of the formula above can then be read as the characteristic function of the predicate "$( \exists z \leq x ) ( y \cdot z = x )$" which is exactly what we mean by "$x$ is divisible by $y$.")

-
Thanks Arthur. I will save your answer for when I reach the "characteristic function" part of my course material. :) –  Ryan Nov 11 '12 at 19:18