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

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?

• We know that not only are these sets recursive, they are actually primitive recursive. Dec 16, 2022 at 2:39
• @MarkSaving They're a lot better than that, even - see either of the answers below. Dec 16, 2022 at 2:43

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 ^_^

• Dangit, beat me by 20 seconds! Dec 16, 2022 at 2:34

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.

• lol, fancy seeing you here :P Dec 16, 2022 at 2:34