$\mathcal {N}\models \phi(n)$ if and only if $n$ is a power of 2, i.e. $n\in \{1,2,4,8,...\}$.

Question

Let $\mathcal {L}$ be the language $\{\mathbf {1},+,\cdot,$exp$,<\}$ where $\mathbf {1}$ is a constant symbol, $+,\cdot$, exp are binary function symbols, and $ < $ is a binary relation symbol. Let $\mathcal {N}$ be the $\mathcal {L}$-structure $(\mathbb {N},\mathbf {1}^{\mathcal {N}},+^{\mathcal {N}},\cdot^{\mathcal {N}},$ exp$^{\mathcal {N}},<^{\mathcal {N}})$, where $\mathbf {1}^{\mathcal {N}},+^{\mathcal {N}},\cdot^{\mathcal {N}},<^{\mathcal {N}}$ are the usual operations, and exp$^{\mathcal {N}}(n,m)=n^m$. Find an $\mathcal {L}$-formula $\phi(v_1)$ such that for every $n\in \mathbb {N}$, $\mathcal {N}\models \phi(n)$ if and only if $n$ is a power of 2, i.e. $n\in \{1,2,4,8,...\}$.

Answer 1

What does it mean for $n$ to be a power of $2$?

It means that there is some natural number $m$ such that $n=2^m$. How can you express this using a formula with the available symbols?

You need a formula $\phi(v_1)$ in which $v_1$ is a free variable, i.e. $v_1$ is not bounded by quantifiers. You want that the formula says that $v_1$ is a power of two.

The following formula will do:

$\exists v_2 (v_1=\mbox{exp}(1+1,v_2))$