# ${\mathrm{\Delta}}_{1}$ bootstrapping

This proves that a number of useful relations^{} and functions are ${\mathrm{\Delta}}_{1}$ in first order arithmetic, providing a bootstrapping of parts of mathematical practice into any system including the ${\mathrm{\Delta}}_{1}$ relations (since the ${\mathrm{\Delta}}_{1}$ relations are exactly the recursive ones, this includes Turing machines^{}).

First, we want to build a tupling relation which will allow a finite sets^{} of numbers to be encoded by a single number. To do this we first show that $R(a,b)\leftrightarrow a|b$ is ${\mathrm{\Delta}}_{1}$. This is true since $a|b\leftrightarrow \exists c\le b(a\cdot c=b)$, a formula^{} with only bounded quantifiers.

Next note that $P(x)\leftrightarrow $x is prime is ${\mathrm{\Delta}}_{1}$ since $$. Also $$.

These two can be used to define (the graph of) a primality function, $p(a)=a+1$-th prime. Let $$.

This rather awkward looking formula is worth examining, since it illustrates a principle which will be used repeatedly. $c$ is intended to be a function of the form ${2}^{0}\cdot {3}^{1}\cdot {5}^{2}\mathrm{\cdots}$ and so on. If it includes ${b}^{a}$ but not ${b}^{a+1}$ then we know that $b$ must be the $a+1$-th prime. The definition is so complicated because we cannot just say, as we’d like to, $p(a+1)$ is the smallest prime greater than $p(a)$ (since we don’t allow recursive definitions). Instead we embed the series of values this recursion would take into a single number ($c$) and guarantee that the recursive relationship holds for at least $a$ terms; then we just check if the $a$-th value is $b$.

Finally, we can define our tupling relation. Technically, since a given relation must have a fixed arity, we define for each $n$ a function $\u27e8{x}_{0},\mathrm{\dots},{x}_{n}\u27e9={\sum}_{\le n}{p}_{i}^{{x}_{i}+1}$. Then define ${(x)}_{i}$ to be the $i$-th element of $x$ when $x$ is interpreted as a tuple, so $\u27e8{(x)}_{0},\mathrm{\dots},{(x)}_{n}\u27e9=x$. Note that the tupling relation, even taken collectively, is not total. For instance $5$ is not a tuple (although it is sometimes convenient to view it as a tuple with “empty spaces”: $\u27e8\mathrm{\_},\mathrm{\_},5\u27e9$). In situations like this, and also when attempting to extract entries beyond the length, ${(x)}_{i}=0$ (for instance, ${(5)}_{0}=0$). On the other hand there is a $0$-ary tupling relation, $\u27e8\u27e9=1$.

Thanks to our definition of $p$, we have $\u27e8{x}_{0},\mathrm{\dots},{x}_{n}\u27e9=x\leftrightarrow x=p{(0)}^{{x}_{0}+1}\cdot \mathrm{\cdots}\cdot p{(n)}^{{x}_{n}+1}$. This is clearly ${\mathrm{\Delta}}_{1}$. (Note that we don’t use the $\sum $ as above, since we don’t have that, but since we have a different tupling function for each $n$ this isn’t a problem.)

For the reverse, ${(x)}_{i}=y\leftrightarrow ([p{(i)}^{y+1}|x]\wedge \mathrm{\neg}[p{(i)}^{y+2}|x])\vee ([y=0]\wedge \mathrm{\neg}[p(i)|x])$.

Also, define a length function by $\mathrm{len}(x)=y\leftrightarrow \mathrm{\neg}[p(y+1)|x]\wedge \forall z\le y[p(z)|x]$ and a membership relation by $$.

Armed with this, we can show that all primitive recursive functions^{} are ${\mathrm{\Delta}}_{1}$. To see this, note that $x=0$, the zero function, is trivially recursive, as are $x=Sy$ and ${p}_{n,m}({x}_{1},\mathrm{\dots},{x}_{n})={x}_{m}$.

The ${\mathrm{\Delta}}_{1}$ functions are closed under composition^{}, since if $\varphi (\overrightarrow{x})$ and $\psi (\overrightarrow{x})$ both have no unbounded^{} quantifiers, $\varphi (\psi (\overrightarrow{x}))$ obviously doesn’t either.

Finally, suppose we have functions $f(\overrightarrow{x})$ and $g(\overrightarrow{x},m,n)$ in ${\mathrm{\Delta}}_{1}$. Then define the primitive recursion $h(\overrightarrow{x},y)$ by first defining:

$$ |

and then $h(\overrightarrow{x},y)={(\overline{h}(\overrightarrow{x},y))}_{y}$.

${\mathrm{\Delta}}_{1}$ is also closed under minimization: if $R(\overrightarrow{x},y)$ is a ${\mathrm{\Delta}}_{1}$ relation then $\mu y.f(\overrightarrow{x},y)$ is a function giving the least $y$ satisfying $R(\overrightarrow{x},y)$. To see this, note that $$.

Finally, using primitive recursion it is possible to concatenate sequences^{}. First, to concatenate a single number, if $s=\u27e8{x}_{0},\mathrm{\dots}{x}_{n}\u27e9$ then $s{*}_{1}y=t\cdot p{(\mathrm{len}(s)+1)}^{y+1}$. Then we can define the concatenation^{} of $s$ with $t=\u27e8{y}_{0},\mathrm{\dots},{y}_{m}\u27e9$ by defining $f(s,t)=s$ and $g(s,t,j,i)=j{*}_{1}{(t)}_{i}$, and by primitive recursion, there is a function $h(s,t,i)$ whose value is the first $j$ elements of $t$ appended to $s$. Then $s*t=h(s,t,\mathrm{len}(t)$.

We can also define ${*}_{u}$, which concatenates only elements of $t$ not appearing in $s$. This just requires defining the graph of $g$ to be $g(s,t,j,i,x)\leftrightarrow [\mathrm{in}(s,{(t)}_{i})\wedge x=j]\vee [\mathrm{\neg}\mathrm{in}(s,{(t)}_{i})\wedge x=j{*}_{1}{(t)}_{i}]$

Title | ${\mathrm{\Delta}}_{1}$ bootstrapping |
---|---|

Canonical name | Delta1Bootstrapping |

Date of creation | 2013-03-22 12:58:25 |

Last modified on | 2013-03-22 12:58:25 |

Owner | Henry (455) |

Last modified by | Henry (455) |

Numerical id | 10 |

Author | Henry (455) |

Entry type | Example |

Classification | msc 03B10 |