Square numbers and spectrums Let the spectrum of a formula $\varphi$ be the set of positive integers $n$ such that $\varphi$ has a finite model whose cardinality is exactly $n$.
In a first-order language consisting of a unary predicate $P$ and unary function symbols $f$ and $g$ (besides the equality symbol $=$) can we find a formula $\varphi$ whose spectrum is the set of square numbers?
I have no idea how to approach this question, and what role the two functions might have in $\varphi$. It would be great if someone could clarify what the role of the two functions $f$ and $g$ might be in the formula $\varphi$.

Edit
I can see that, in a model $\mathfrak{M}_2$ whose domain is $D_2 =\{a,b\}$, and where $P^{\mathfrak{M}_2} \neq \emptyset$ and $P^{\mathfrak{M}_2} \subseteq \{a,b \}$, since $|P^{\mathfrak{M}_2} \times P^{\mathfrak{M}_2}|$ would then be at most 4, so that the there cannot be a bijection between $D_2$ and $P^{\mathfrak{M}_2} \times P^{\mathfrak{M}_2}$, since they differ in cardinality. The same would hold for $\mathfrak{M}_3$ whose domain is $D_3 =\{a,b, c\}$, and where $P^{\mathfrak{M}_3} \neq \emptyset$ and $P^{\mathfrak{M}_3} \subseteq \{a,b, c \}$. So for any model $\mathfrak{M}$ the required bijection can only occur if $|P^\mathfrak{M}| = \sqrt{|\mathfrak{M}|}$. Given a model $\mathfrak{M}$ with domain $D$, one way to obtain the desired bijection would be to have $\sqrt{n}$ elements of the domain $D$ satisfy $P^\mathfrak{M}$ (where $D$ has cardinality $n$) and map the $d \in P^\mathfrak{M}$ to pairs $(d, d)$, and the $e \not\in P^\mathfrak{M}$ to pairs $(e,f)$ or $(f,e)$, where $e \neq f$.
I can't see clearly how to ensure these constraints are met with a suitable formula of predicate logic in the language described in my question.
 A: Let $\varphi$ be the conjunction of the following sentences:

*

*$\forall z\,P(f(z))\land P(g(z))$

*$\forall z\forall z'\,((f(z) = f(z')\land g(z) = g(z'))\rightarrow z = z')$

*$\forall x\forall y\,((P(x)\land P(y))\rightarrow \exists z\,(f(z) = x\land g(z) = y))$
Suppose $M\models \varphi$ is a finite model. Then:

*

*says $f$ and $g$ are both functions $M\to P$. Together, they induce a function $h\colon M\to P^2$, given by $h(z) = (f(z),g(z))$.

*says $h$ is injective.

*says $h$ is surjective.

It follows that $|M| = |P^2| = |P|^2$, which is a square number. This shows that the spectrum of $\varphi$ is contained in the set of square numbers.
Conversely, let $m = p^2$ be a square number. Note that $p\leq m$. We define a model $M$ with domain $\{0,\dots,m-1\}$ by setting $P = \{0,\dots,p-1\}$. For any $z\in \{0,\dots,m-1\}$, let $f(z)$ be the quotient of $m$ when divided by $p$, and let $g(z)$ be the remainder (so $f(z)$ and $g(z)$ are the unique natural numbers less than $p$ such that $z = pf(z)+g(z)$). Then $M\models \varphi$, so every square number is in the spectrum of $\varphi$.
A: Hint: Let $L$ be a language with a predicate $P$ and two unary functions $f_1,f_2$. Find an $L$-sentence $\varphi$ whose models are structures $M$ such that there is a bijection between $M$ and $P(M)^2$.
