# Category of finite models of a $\tau$-sentence

Let $$\varphi$$ be an $$\tau$$-sentence, we define the generalized spectrum of $$\varphi$$ as the class of its finite models, $$\text{GenSpec}(\varphi):=\{\mathcal{A}; \mathcal{A} \models \varphi, \lvert A\rvert < \aleph_0\}$$ and the spectrum of $$\varphi$$ as the set of cardinalities of finite models $$\text{Spec}(\varphi):=\{\lvert A \rvert; \mathcal{A}\in\text{GenSpec}(\varphi)\}.$$

It is well known that coding $$\text{Spec}(\varphi)$$ using binary strings results in precisely all $$\text{NE}$$ sets, this follows from the Fagin's theorem which states that the set of binary encoded linearly ordered structures of $$\text{GenSpec}(\varphi)$$ are precisely the $$\text{NP}$$ sets of binary encoded strctures.

Equip $$\text{GenSpec}(\varphi)$$ with all $$\tau$$-structure morphisms and call this category $$\text{MOD}_{\text{fin}}(\varphi)$$.

The question: Is it known whether for every $$\varphi$$ an $$\tau$$-sentence there exists $$\psi$$ a $$\tau$$-sentence such that $$\text{Spec}( \varphi)=\text{Spec}(\psi),$$ and $$\text{MOD}_{\text{fin}}(\psi)$$ is a grupoid? In other words, do morphisms matter while considering spectra of FO sentences?

A correction, to start: "$$\mathcal{C}$$ is discrete" does not mean "$$\text{Mor}(\mathcal{C}) = \emptyset$$". Instead, a discrete category has only identity arrows. And even with that correction, your question as written has a somewhat trivial negative answer: The class $$\text{GenSpec}(\varphi)$$ is always closed under isomorphism, and the category $$\text{MOD}_{\text{fin}}(\varphi)$$ will always contain all isomorphisms. So as long as $$\varphi$$ has any nonempty models, $$\text{MOD}_{\text{fin}}(\varphi)$$ will not be discrete.

I suspect you really want to ask whether you can find $$\psi$$ such that $$\text{MOD}_{\text{fin}}(\psi)$$ is a groupoid, i.e. such that every arrow is an isomorphism. So I'll go forward with that interpretation of the question.

If you fix a signature $$\tau$$, then the answer is no in general. For example, suppose $$\tau$$ is the empty signature (so a $$\tau$$-structure is a pure set). For any $$\tau$$-structure $$M$$ with $$|M|\geq 2$$, there is a $$\tau$$-homomorphism $$M\to M$$ which is not an isomorphism (e.g. any constant function). So if $$\varphi$$ is any $$\tau$$-sentence with $$\text{Spec}(\varphi)\not\subseteq \{0,1\}$$, and $$\psi$$ is any $$\tau$$-sentence with $$\text{Spec}(\psi) = \text{Spec}(\varphi)$$, then $$\text{MOD}_{\text{fin}}(\psi)$$ is not a groupoid.

On the other hand, if you allow the signature to change, the answer to your question is positive. Let $$\varphi$$ be a $$\tau$$-sentence, and let $$\tau'$$ be $$\tau$$ together with some new symbols:

• A binary relation $$<$$.
• A binary relation $$S$$.
• Two unary relations $$F$$ and $$L$$.
• For each relation symbol $$R$$ in $$\tau$$, a relation symbol $$R_\lnot$$ of the same arity.

Let $$\psi$$ be the conjunction of $$\varphi$$ with sentences expressing the following:

• $$<$$ is a strict linear order.
• $$S$$ is the successor relation for $$<$$.
• $$F$$ defines the first element of the order $$<$$.
• $$L$$ defines the last element of the order $$<$$.
• $$R_\lnot$$ defines the complement of the relation $$R$$.

Since any finite model of $$\varphi$$ can be expanded to a model of $$\psi$$, we have $$\text{Spec}(\varphi) = \text{Spec}(\psi)$$. And you can check that any $$\tau'$$-homomorphism between models of $$\psi$$ is an isomorphism. So $$\text{MOD}_{\text{fin}}(\psi)$$ is a groupoid.