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