Welcome to our community

Be a part of something great, join today!

prove primitive recursive

Mafaz

New member
Jan 26, 2019
4
3Q.png
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,488
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
Jan 26, 2019
4
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.

Would please help me.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,488
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
Jan 26, 2019
4
Thanks for your reply.
So what is this example ?
Is it for qoueint or reminder ?
 

Mafaz

New member
Jan 26, 2019
4
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
Jan 30, 2012
2,488
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.