Consider the set of natural numbers $\Bbb N$ as a signature structure $(=, S)$, where $S$ is interpreted as a function of $S(x) = x+ 1$. Prove that the two-place relation y = x + N can be expressed by the formula of this signature, the length of which is $O(\log N)$.
It is clear that the predicate x + N can always be expressed in terms of the function $S$ by the formula of length $O(N)$, but how to do this by the ratio of length $O(\log N)$?
And is it even possible?
The idea is to build $N$ by doubling, which takes $O(\log N)$ steps. We can write a formula expressing $y=x+2n$ (or $y=x+2n+1$) using a formula expressing $y=x+n$ and some logical connectives to "apply it twice" while only writing it once: $$ \begin{align} \phi_{2n}(x,y)&:=\exists z\ \forall s\forall t\ (s=x\land t=z)\lor(s=z\land t=y)\to\phi_n(s,t)\\ \phi_{2n+1}(x,y)&:=\exists z\ \phi_{2n}(x,z)\land y=S(z) \end{align} $$
using fresh variable names at each stage in place of $z,s,t$ to avoid collisions with subformulas.