3
$\begingroup$

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?

  • 0
    Review Link: Have you looked at [common-primitive-recursive-functions](http://en.wikipedia.org/wiki/Primitive_recursive_function#Some_common_primitive_e%20_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".2012-11-11
  • 0
    Thanks, I had already checked out the wikipedia page.2012-11-11
  • 0
    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.2012-11-11

2 Answers 2

2

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|$...

  • 0
    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?2012-11-11
  • 0
    @Ryan: That's what I describe in the answer!2012-11-11
  • 0
    @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)$.2012-11-11
  • 0
    @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.2012-11-11
  • 0
    I understand your solution, but I don't understand how your solution relates to your suggestion to bring in the restricted subtraction/absolute diff functon. I have found out from wikipedia that mod is listed as a common PR function, but because it hasn't been introduced in my course, I am not allowed to use it as a building block (unless of course I separately show that mod is PR).2012-11-11
  • 0
    Perhaps this is why my question hasn't been assigned as coursework. (It's the only "common PR function" listed in my course where the formal recursive definition hasn't been included, that's why I created this question here.) Anyway, thank you for your time and patience.2012-11-11
  • 1
    @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.2012-11-11
  • 0
    In more detail: Construct $f$ as $f(a,b,x,y)=f\!f(|x-y|,a,b)$, where $f\!f$ is directly defined by primitive recursion.2012-11-11
2

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$.")

  • 0
    Thanks Arthur. I will save your answer for when I reach the "characteristic function" part of my course material. :)2012-11-11