I saw this question on a Mathematical Logic exam somewhere and I have been trying to find an answer for a while now.
Let $\mathcal{L}^=$ be a first order language with a single function symbol $f$, a single relation symbol $=$ and no constant symbols. Now, define the following $\mathcal{L}^=$-structures:
- $\mathcal{A} := \langle \mathbb{N}; =; x \mapsto x^2 \rangle$, and
- $\mathcal{B} := \langle \mathbb{N}; =; x \mapsto x^3 \rangle$.
The question asks whether there exists a formula $\phi$ such that $\mathcal{A}$ is a (normal) model of $\phi$ but $\mathcal{B}$ isn't, i.e. a $\phi$ such that $\mathcal{A} \vDash \phi$ and $\mathcal{B} \nvDash \phi$.
To give some context, the previous question asked the same but with the interpretation of the function symbol in each structure being $x \mapsto x+2$ and $x \mapsto x+3$ respectively. There is an obvious candidate for $\phi$ in that case since in the latter structure there are exactly two elements in the domain that are not in the range of the function and this is a property expressible in our first-order language.
The fact that such formula existed made me think that, since the problem seemed somewhat similar from a model theoretic point of view, there would be a formula for this problem. However, after a series of failed attempts, I am starting to think that perhaps such formula does not exist. In that case, how could the non-existence of that formula be proved?