# prove primitive recursive

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
Hi, and welcome to the forum!

Its easiest to prove first that bounded search on a primitive recursive (PR) condition produces a PR function. I means that if the characteristic function of a relation $R(x)$ is PR, then the function that, given $n$, returns the smallest $k\le n$ such that $R(k)$ holds or $n+1$ if no such $k$ exists is PR. More generally $R$ may have parameters $y_1,\ldots,y_p$. Let's denote the bounded search function by $\min_{x\le n}R(x,y_1,\ldots,y_p)$. Then quotient, remainder and greatest common divisor can be obtained in this way because they return a number that is smaller than one of the arguments. It is also possible to show that bounded quantifications $\exists x\le n\,R(x,y_1,\ldots,y_p)$ and $\forall x\le n\,R(x,y_1,\ldots,y_p)$ on a PR relation $R$ are PR. This allows expressing divisibility and primality. For example,
$\text{Prime}(x)\iff 1<x\land \forall u\le x-1\;\forall v\le x-1\,uv\ne x.$

Several of your examples are described in the book "Computability and Logic" by G. Boolos, J. Burgess and R. Jeffrey, fifth edition, chapters 6 and 7. It requires some reading, but it has a lot of detailed examples.

If you have further questions, please post them here.

#### Mafaz

##### New member
Hi, and welcome to the forum!

Its easiest to prove first that bounded search on a primitive recursive (PR) condition produces a PR function. I means that if the characteristic function of a relation $R(x)$ is PR, then the function that, given $n$, returns the smallest $k\le n$ such that $R(k)$ holds or $n+1$ if no such $k$ exists is PR. More generally $R$ may have parameters $y_1,\ldots,y_p$. Let's denote the bounded search function by $\min_{x\le n}R(x,y_1,\ldots,y_p)$. Then quotient, remainder and greatest common divisor can be obtained in this way because they return a number that is smaller than one of the arguments. It is also possible to show that bounded quantifications $\exists x\le n\,R(x,y_1,\ldots,y_p)$ and $\forall x\le n\,R(x,y_1,\ldots,y_p)$ on a PR relation $R$ are PR. This allows expressing divisibility and primality. For example,
$\text{Prime}(x)\iff 1<x\land \forall u\le x-1\;\forall v\le x-1\,uv\ne x.$

Several of your examples are described in the book "Computability and Logic" by G. Boolos, J. Burgess and R. Jeffrey, fifth edition, chapters 6 and 7. It requires some reading, but it has a lot of detailed examples.

If you have further questions, please post them here.

thanks but I have difficulty to prove especially prime and divisibility . Actually I need to follow the question and to have base and inductive case.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
Actually I need to follow the question and to have base and inductive case.
The usual way of proving that divisibility is PR goes through defining several intermediate PR functions. Perhaps you expect me to write the precise definition of $\mathit{div}(x,y)$ right away, but I'd rather not for two reasons: as I said, this requires intermediate definitions, and you need to show some work, too (see forum rule 11).

First you need to get a textbook that discusses PR functions and study why some some usual functions such as addition, multiplication, factorial, predecessor and subtraction are PR. Also read what PR relations are and why their class is closed under conjunction, disjunction and negation. Next we need to prove that finite sums and bounded existential quantifier on a PR condition is again PR. Perhaps this is also discussed in your textbook. For example, if $$\displaystyle g(n,y)=\sum_{x=0}^n f(x,y)$$ where $f(x,y)$ is PR, then $g(n,y)$ is also PR because
\begin{align*}
g(0,y)&=f(0,y)\\
g(n+1,y)&=g(n,y)+f(n+1,y)
\end{align*}
Now try proving that if $R(x,y)$ is a PR relation, then $P(n,y)=\exists x\le n\,R(x,y)$ is also a PR relation.

#### Mafaz

##### New member
So what is this example ?
Is it for qoueint or reminder ?

#### Mafaz

##### New member
The usual way of proving that divisibility is PR goes through defining several intermediate PR functions. Perhaps you expect me to write the precise definition of $\mathit{div}(x,y)$ right away, but I'd rather not for two reasons: as I said, this requires intermediate definitions, and you need to show some work, too (see forum rule 11).

First you need to get a textbook that discusses PR functions and study why some some usual functions such as addition, multiplication, factorial, predecessor and subtraction are PR. Also read what PR relations are and why their class is closed under conjunction, disjunction and negation. Next we need to prove that finite sums and bounded existential quantifier on a PR condition is again PR. Perhaps this is also discussed in your textbook. For example, if $$\displaystyle g(n,y)=\sum_{x=0}^n f(x,y)$$ where $f(x,y)$ is PR, then $g(n,y)$ is also PR because
\begin{align*}
g(0,y)&=f(0,y)\\
g(n+1,y)&=g(n,y)+f(n+1,y)
\end{align*}
Now try proving that if $R(x,y)$ is a PR relation, then $P(n,y)=\exists x\le n\,R(x,y)$ is also a PR relation.

Thanks but what is this function for?

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
Bounded existential quantification can be used to define divisibility and primality, and bounded minimization from post #2, which is similar, can be used to define the rest of the functions in post #1.