${\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 $⟨x_0,\mathrm{\dots },x_n⟩={\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 $⟨{(x)}_0,\mathrm{\dots },{(x)}_n⟩=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”: $⟨\mathrm{\_},\mathrm{\_},5⟩$). 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, $⟨⟩=1$.

Thanks to our definition of $p$, we have $⟨x_0,\mathrm{\dots },x_n⟩=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=⟨x_0,\mathrm{\dots }{x}_n⟩$ then $s{*}_{1}y=t\cdot p{(\mathrm{len}(s)+1)}^{y+1}$. Then we can define the concatenation of $s$ with $t=⟨y_0,\mathrm{\dots },y_m⟩$ 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