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

• $\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? 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. 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? Nov 16, 2018 at 2:44
• @fleablood what is $r$? 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? Nov 16, 2018 at 2:54

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. Nov 16, 2018 at 7:11
• @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. Nov 16, 2018 at 7:35