delta-zero formula and power of 2

Question

How can we show that $x=2^k$ for some $k$ is equivalent (in the Naturals) to a $\Delta_0$ formula?

So, I'm stuck at showing that 'y divides x' and '2 divides y' are equivalent in the Naturals to $\Delta_0$ formulas.

Answer 1

If $x=2^k$ then every prime number which divides $x$ has to be $2$. Of course that saying "every prime number" is an unbounded assertion, but luckily no prime number which is larger than $x$ can divide $x$, so we can instead write it as follows:

$x=2^k$ if and only if $x\neq 0$ and for every $p<x$, if $p$ is prime and $p\mid x$ then $p=2$.

Now we need to verify that "$k$ is a prime number" and $k\mid n$ are both bounded statement, but that's not very hard:

1. Recall that $k\mid n$ if and only if there exists $m<n+1$ such that $k\cdot m=n$. Under this definition every number divides zero, and zero divides every number. Formally speaking we have the following bounded: $$k\mid n\iff\exists m<s(n):k\cdot m=n.$$
2. Recall that $p$ is a prime if whenever $k<p$ and $k\mid p$ then $k=1$, but we also have that $0$ divides every number, so we actually have $p$ is a prime if $1<p$ and for every $k<p$, if $k\mid p$ then $k<2$. Again we have only one quantifier and it is bounded, so we have the following formula: $$p\text{ is prime} \iff s(0)<p\land\forall k<p:k\mid p\rightarrow k<s(s(0)).$$

So now to combine everything together we have as follows:

$$x=2^k\iff\lnot(x=0)\land\forall p<x:p\text{ is prime}\land p\mid x\rightarrow p=s(s(0)).$$

There is one quantifier which is bounded, over two formulas containing only bounded quantifiers themselves. Therefore the whole statement is bounded, that is to say $\Delta_0$.

Answer 2

Obviously, $x > 1$ is a power of 2 iff (A): every $y > 1$ which divides $x$ is itself divisible by 2.

Use the fact that factors of a number are less than it to bound the quantifiers in formalizing statement (A), and you'll get a $\Delta_0$ wff.