Return to Answer

No. We don't need every primitive recursive function.

In fact every recursive function is the composition of two primitive recursive functions definable by $\Delta_0$ formulas, and using the minimization operator. Since not every primitive recursive function is $\Delta_0$ this shows that you don't really need all the primitive recursive functions after all.

This is because we can write the graph of every recursive function as a $\Sigma_1$ set, i.e. $f(\vec x)=y\iff\exists z\varphi(\vec x,y,z)$, where $\varphi$ is a $\Delta_0$ formula. We can define from $\varphi$ two functions $G$ and $H$ as follows:

• $G(\vec x,w)=\min_{y < w}\exists z < w\varphi(\vec x,y,z)$ - this function returns the least $y$ such that $\varphi(\vec x,y,z)$ holds, if such $z$ exists.
• $H(\vec x,w)=\exists y < w\exists z < w\varphi(\vec x,y,z)$ - this function returns $0$ if there is such $y$ and $z$ below $w$, and $1$ otherwise.

It is not difficult to see that indeed both $G$ and $H$ are primitive recursive, and defined by $\Delta_0$ formulas.

Now $f(\vec x)=G(\vec x,\mu w H(\vec x,w))$, and one can verify that even if $f$ is a partial function the result is the same (i.e. it does not extend $f$).

No. We don't need every primitive recursive function.

In fact every recursive function is the composition of two primitive recursive functions definable by $\Delta_0$ formulas, and using the minimization operator. Since not every primitive recursive function is $\Delta_0$ this shows that you don't really need all the primitive recursive functions after all.

This is because we can write the graph of every recursive function as a $\Sigma_1$ set, i.e. $f(\vec x)=y\iff\exists z\varphi(\vec x,y,z)$, where $\varphi$ is a $\Delta_0$ formula. We can define from $\varphi$ two functions $G$ and $H$ as follows:

• $G(\vec x,w)=\min_{y < w}\exists z < w\varphi(\vec x,y,z)$ - this function returns the least $y$ such that $\varphi(\vec x,y,z)$ holds, if such $z$ exists.
• $H(\vec x,w)=\exists y < w\exists z < w\varphi(\vec x,y,z)$ - this function returns $0$ if there is such $y$ and $z$ below $w$, and $1$ otherwise.

It is not difficult to see that indeed both $G$ and $H$ are primitive recursive, and defined by $\Delta_0$ formulas.

Now $f(\vec x)=G(\vec x,\mu w H(\vec x,w))$, and one can verify that even if $f$ is a partial function the result is the same (i.e. it does not extend $f$).

No. We don't need every primitive recursive function.

In fact every recursive function is the composition of two $\Delta_0$ functions with the minimization operator. Since every $\Delta_0$ function is primitive recursive, but not every primitive recursive is $\Delta_0$ this shows that you don't really need all the primitive recursive functions after all.

This is because we can write the graph of every recursive function as a $\Sigma_1$ set, i.e. $\exists z\varphi(\vec x,y,z)$ where $\varphi$ is a $\Delta_0$ formula. We can define from $\varphi$ two functions $G$ and $H$ as follows:

• $G(\vec x,w)=\min_{y < w}\exists z < w\varphi(\vec x,y,z)$ - this function returns the least $y$ such that $\varphi(\vec x,y,z)$ holds, if such $z$ exists.
• $H(\vec x,w)=\exists y < w\exists z < w\varphi(\vec x,y,z)$ - this function returns $0$ if there is such $y$ and $z$ below $w$, and $1$ otherwise.

Now $f(\vec x)=G(\vec x,\mu w H(\vec x,w))$, and one can verify that even if $f$ is a partial function the result is the same (i.e. it does not extend $f$).

No. We don't need every primitive recursive function.

In fact every recursive function is the composition of two primitive recursive functions definable by $\Delta_0$ formulas, and using the minimization operator. Since not every primitive recursive function is $\Delta_0$ this shows that you don't really need all the primitive recursive functions after all.

This is because we can write the graph of every recursive function as a $\Sigma_1$ set, i.e. $f(\vec x)=y\iff\exists z\varphi(\vec x,y,z)$, where $\varphi$ is a $\Delta_0$ formula. We can define from $\varphi$ two functions $G$ and $H$ as follows:

• $G(\vec x,w)=\min_{y < w}\exists z < w\varphi(\vec x,y,z)$ - this function returns the least $y$ such that $\varphi(\vec x,y,z)$ holds, if such $z$ exists.
• $H(\vec x,w)=\exists y < w\exists z < w\varphi(\vec x,y,z)$ - this function returns $0$ if there is such $y$ and $z$ below $w$, and $1$ otherwise.

It is not difficult to see that indeed both $G$ and $H$ are primitive recursive, and defined by $\Delta_0$ formulas.

Now $f(\vec x)=G(\vec x,\mu w H(\vec x,w))$, and one can verify that even if $f$ is a partial function the result is the same (i.e. it does not extend $f$).

No. We don't need every primitive recursive function.

In fact every recursive function is the composition of two $\Delta_0$ functions with the minimization operator. Since every $\Delta_0$ function is primitive recursive, but not every primitive recursive is $\Delta_0$ this shows that you don't really need all the primitive recursive functions after all.

No. We don't need every primitive recursive function.

In fact every recursive function is the composition of two $\Delta_0$ functions with the minimization operator. Since every $\Delta_0$ function is primitive recursive, but not every primitive recursive is $\Delta_0$ this shows that you don't really need all the primitive recursive functions after all.

This is because we can write the graph of every recursive function as a $\Sigma_1$ set, i.e. $\exists z\varphi(\vec x,y,z)$ where $\varphi$ is a $\Delta_0$ formula. We can define from $\varphi$ two functions $G$ and $H$ as follows:

• $G(\vec x,w)=\min_{y < w}\exists z < w\varphi(\vec x,y,z)$ - this function returns the least $y$ such that $\varphi(\vec x,y,z)$ holds, if such $z$ exists.
• $H(\vec x,w)=\exists y < w\exists z < w\varphi(\vec x,y,z)$ - this function returns $0$ if there is such $y$ and $z$ below $w$, and $1$ otherwise.

Now $f(\vec x)=G(\vec x,\mu w H(\vec x,w))$, and one can verify that even if $f$ is a partial function the result is the same (i.e. it does not extend $f$).