Let $\mathcal L^=$ be a first-order language with equality, with a single one-place function symbol $f$. Let $\mathcal A,\mathcal B$ be two $\mathcal L^=$-structures both with domain equal to $\Bbb N$. Further let $\mathcal A$ interpret the symbol $f$ as the function $f^{\mathcal A}(x)=x^2$ and $f^{\mathcal B}(x)=x^3$.
Is there a closed $\mathcal L^=$ formula which is true for precisely one of these structures? Decide this without using quantifier elimination.
I am almost certain that these are not isomorphic and therefore I cannot prove, in this way, that the structures are elementarily equivalent.
However, I also can't think of a formula which distinguishes them. They both have precisely two fixed points of the function: $f(0)=0$ and $f(1)=1$ in both settings. We can't talk about between-ness to help out. We can't name any specific numbers or arithmetic operations other than the one given by $f$.
I can't think of how I would apply Los-Vaught since I can't think of a theory which I could show to be complete. I suppose I could try to write down formulas that seem to say everything I can think of about $f$, like "there are precisely two fixed points, and for all other numbers, they do not map to these fixed points". But that just doesn't seem like it would be complete, or if it is, I wouldn't know how to show it.
I don't think Lowenheim-Skolem would help because they're both already countable structures.
I strongly suspect that there is no closed formula distinguishing them, but I'm out of ideas about how to prove it.
As discussed in the comments, indeed one can build an isomorphism. I didn't realize this because I thought any mapping from the nonsquare 2, for example, and the nonsquare 8, would have some kind of bad interactions -- but what I was forgetting is that although 8 comes up as an eventual power of 2, that doesn't matter because we're mapping these to cubes and so the interaction that I was worried about doesn't occur.
Anyway, the more complete answer goes a little like this: Define $g$ to be any bijection from the non-squares to the non-cubes. Then extend $g$ to a function $h:\Bbb N\to\Bbb N$ by defining $h(x)=g(x)$ on any non-square $x$, and $h(x^2) = [g(x)]^3$ for everything else.