- Thread starter
- #1

- Thread starter Mafaz
- Start date

- Thread starter
- #1

- Jan 30, 2012

- 2,488

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.

- Thread starter
- #3

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.

- Jan 30, 2012

- 2,488

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).Actually I need to follow the question and to have base and inductive case.

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.

- Thread starter
- #5

- Thread starter
- #6

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?

- Jan 30, 2012

- 2,488