0
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ $\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? $\endgroup$
    – fleablood
    Nov 16, 2018 at 2:36
  • $\begingroup$ @fleablood Can you please expand a little bit on your notation? I am not sure what you mean, sorry. $\endgroup$
    – Daniels Krimans
    Nov 16, 2018 at 2:38
  • $\begingroup$ "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? $\endgroup$
    – fleablood
    Nov 16, 2018 at 2:44
  • $\begingroup$ @fleablood what is $r$? $\endgroup$
    – Daniels Krimans
    Nov 16, 2018 at 2:50
  • $\begingroup$ $r$ is a typo for $d$. I'm just defining the remainder function. Why doesn't it seem algebraic to you? $\endgroup$
    – fleablood
    Nov 16, 2018 at 2:54

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Daniels Krimans
    Nov 16, 2018 at 7:11
  • $\begingroup$ @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. $\endgroup$
    – spaceisdarkgreen
    Nov 16, 2018 at 7:17
  • $\begingroup$ @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. $\endgroup$
    – spaceisdarkgreen
    Nov 16, 2018 at 7:35
  • $\begingroup$ ..... " 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. $\endgroup$
    – fleablood
    Nov 16, 2018 at 17:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .