MHB Can bounded quantification define divisibility and primality?

[Mafaz]

View attachment 8760

 

[Evgeny.Makarov]

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]

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]

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 https://mathhelpboards.com/rules/ 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 $$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]

Thanks for your reply.
So what is this example ?
Is it for qoueint or reminder ?

 

[Mafaz]

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 https://mathhelpboards.com/rules/ 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 $$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]

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.