Which subsets of $\mathbb{N}$ can be the sizes of finite models?

Question

Let $T$ be a finite first order theory (equivalently a single sentence) in a finite language. It is clear that $\{n\in\mathbb{N}:\exists M, M\models T\land |M|=n\}$ is computable: to see if there is a model of size $n$ just enumerate all structures of size $n$ and check one by one if any of them satisfies $T$. I guess this argument actually gives an upper bound on the time complexity of that set.

Conversely which computable sets can arise in this way? I wonder if given a Turing machine we can find a theory whose (finite) models are exactly "truncations" of the running process of that Turing machine. Maybe this is also related to descriptive finite model theory?

Answer 1

As you noticed, we can restrict attention to a single sentence $\varphi$. Your set of interest is called the spectrum of $\varphi$, and it is very well studied.

As one answer to your question (available in the linked wikipedia article), a set $S \subseteq \mathbb{N}$ is the spectrum of some formula $\varphi$ if and only if it's $\mathsf{NEXP}$-time decidable.

---

I hope this helps ^_^

Answer 2

This is the finite spectrum problem. It is know that $X\subseteq\mathbb{N}$ is a finite spectrum (= a set of the type you describe) if and only if $X$ is decidable by a nondeterminstic Turing machine in exponential time; snappily "spectrums = $\mathsf{NEXPTIME}$." It is wildly open whether the complement of a spectrum is again a spectrum!

See the paper Durand/Jones/Makowsky/More, 50 years of the finite spectrum problem for more background on this.