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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.