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

Question

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?

Answer 1

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.