# Remainder function being arithmetic

I am reading Kleene's "Introduction to Metamathematics" chapter 9 section 48, where he mentions that "We know that the predicate $$rm(c,d)=w$$, where $$w$$ is the remainder when $$c$$ is divided by $$d$$, is arithmetical" (1971 ed. pp.239).

I know that $$rm(c,d)=w$$ is primitive recursive but I have trouble understanding why it is arithmetical. I would like to understand this without using the result that all primitive recursive functions are arithmetical.

Definition: Predicate is arithmetical if it can be expressed explicitly in terms of constant, variable natural numbers, functions $$+$$, $$\cdot$$, equality $$=$$, the operations "implies", "and", "or", "not", and the quantifiers "for all", "there exists", combined according to the usual syntactical rules.

I would appreciate your help!

• $\forall c,d\in \mathbb N,\exists ! k,w|c=kd+w \land 0< w\le r; rm(c,d):= w$. Surely that is arithmetical? Commented Nov 16, 2018 at 2:36
• @fleablood Can you please expand a little bit on your notation? I am not sure what you mean, sorry. Commented Nov 16, 2018 at 2:38
• "For all natural ($0$ is included) $c,d\ne 0$ there exist a unique natural numbers $k,w$ so that $c = kd + w$ and $0\le w < r$ and we define $rm(c,d):=w$" Is that not arithmetical? Commented Nov 16, 2018 at 2:44
• @fleablood what is $r$? Commented Nov 16, 2018 at 2:50
• $r$ is a typo for $d$. I'm just defining the remainder function. Why doesn't it seem algebraic to you? Commented Nov 16, 2018 at 2:54

## 1 Answer

As indicated by fleablood in the comments, we can write the relation $$rm(c,d)=w$$ as $$w and, to fully comply with your requirements, $$w can be expressed as $$\exists z(\lnot(z=0)\land d = w+z)$$

• Hi! Thanks for your answer. I would like to have the property of remainder that $rm(c,0)=0*k+c$, in other words, $rm(c,0)=c$. Using your definition, this is not the case. Because no matter what value we consider $w<0$ will always be false, so $rm(c,0)=w$ will always be false. Commented Nov 16, 2018 at 7:11
• @DanielsKrimans Yes if we want to make it a total function then I guess we should handle the case of dividing by zero. Setting the remainder equal to zero in this case sounds fine. So... add a clause to the formula to handle this case. Commented Nov 16, 2018 at 7:17
• @DanielsKrimans I misread: you want to set the remainder when dividing $c$ by zero to be $c$... seems strange to me, but hey, it’s just a default value for a nonsense case, so go for it. And it’s just as easily handled as using zero. Commented Nov 16, 2018 at 7:35
• ..... " I would like to have the property of remainder that..." you never said anything about defining a new and different arithmetic function. You asked why an existing and defined function was arithmetic. If you have a specific question I suggest you actually ask that question. This answers the question that you did ask. Commented Nov 16, 2018 at 17:42