Recursive subsets of $\mathbb{N}$ and finite model theory

I wanted to write my solution to https://brilliant.org/problems/are-spectrums-recursive amongst other things to discuss something. Please read the problem description there. In the solution I came up with (see below) the non-trivial part involves showing that there be a recursive set which is not a spectrum. This comes down to constructing a set which in some sense ‘grows’ to fast. I would like to know, if there be a proof involving a more directly diagonal construction… or whether this be essentially the only way to prove this.

Theorem. Let $M\subseteq\mathbb{N}$. Then $M$ a spectrum $\Rightarrow$ $M$ recursive and the implication is strict.

Proof. ($\Rightarrow$.) Let $M\subseteq\mathbb{N}$ be a spectrum. Then there exists a formula $\varphi$ over $\sigma$, such that $M=\{|\frak{A}|:\frak{A}\textrm{ a \$\sigma\$-structure},~\mathfrak{A}\vDash\varphi\}$. Since the elements of a structure do not matter, and only finitely many symbols occur in $\varphi$, it suffices to restrict to models of finite signature with domains of the form $\{0,1,\ldots,n-1\}$. For any $n$ there are thus only finitely many $\sigma$-structures to check, each of which can be performed in a uniformly recursive manner, to determine, whether or not there is a structure of size $n$ satisfying $\varphi$. Hence $M$ is recursive.

($\not\Leftarrow$.) Wlog we restrict to a countably infinite vocabulary, $\sigma$, with countably infinitely many relations all arities, function all arities and constants. We also enumerate the symbols $\sigma$ such that it everything is recursive: determining whether or not a (code for a) formula is a well defined formula, whether or not a $\sigma$-structure of a given size exists (utilising the above-mentioned finite-reduction trick) that satisfies a given formula, the length (or complexity) of a formula, etc. I’ll leave out the details, as that is a tedium and does not shed any light on anything.

Defn 1. Let $[\cdot]$ denote a suitable coding of formulae (preferably not the horrible one that Gödel used, better one that uses the much more mathematically practical encoding via prime powers). Denote the corresponding (strikt) linear ordering of the formulae by $\prec$, ie $\psi\prec\phi$ iff $[\psi]<[\phi]$. Note that each formula has necessarily only finitely many $\prec$-predecessors.

Defn 2. For any $\sigma$-sentence, $\varphi$, let $M(\varphi)\subseteq\mathbb{N}$ denote the spectrum of $\varphi$. In the following subsets of naturals will be occasionally be viewed dually as an element of $2^{\omega}$.

Defn 3.

For $s\in 2^{<\omega}$ set $D(s):=\{\varphi\textrm{ a \$\sigma\$-sentence}:s\subseteq M(\varphi)\}$.

Defn 4.

Set $\delta:s\in 2^{<\omega}\mapsto\min\{[\varphi]:\varphi\in D(s)\}\in\mathbb{N}$.

Observation 5. $\delta$ is well-defined: For every $s\in 2^{<\omega}$ one has at least $s\subseteq M(\varphi_{s})$ where $\varphi_{s}:\equiv\bigvee_{i<|s|,~s(i)=1}\varphi_{i}\wedge\neg\bigvee_{i<|s|,~s(i)=0}\varphi_{i}$ and $\varphi_{i}:\equiv\exists{x_{0}}\exists{x_{1}}\ldots\exists{x_{n-1}}\bigwedge_{i<j<n}x_{i}\neq x_{j}\wedge\forall{x_{0}}\forall{x_{1}}\ldots\forall{x_{n}}\bigvee_{i<j<n}x_{i}=x_{j}$. It is easy to show that the map $s\mapsto[\varphi_{s}]$ is recursive. Due to the above ramble about ‘everything’ being recursive, and since $s\mapsto[\varphi_{s}]$ yields a clearly recursive function providing upper bounds for the code of the minimal sentence in $D(s)$, it holds that $\delta$ is a recursive function.

Defn 6. For any spectrum, $M$, let $\hat{\psi}_{M}$ denote the $\prec$-minimal sentence with $M(\hat{\psi}_{M})=M$.

The point of this construction is as follows.

Claim 7. For all spectra, $M$ there exists $s_{M}\subseteq M$ sufficiently large, such that for all $s\in 2^{<\omega}$ with $s_{M}\subseteq s\subseteq M$ it holds that $\delta(s)=[\hat{\psi}_{M}]$. Pf. Consider all sentences $\phi$ with $\phi\prec\hat{\psi}_{M}$. There are only finitely many of these! List them out: $\psi_{0},\psi_{1},\ldots,\psi_{N-1}$. Due to minimality, $M(\psi_{j})\neq M$ for all $j<N$. Since there are only finitely many sets here, and viewing these dually as elements of $2^{\mathbb{N}}$, there exists a finite segment $s_{M}\subseteq M$ so that $s_{M}\nsubseteq M(\psi_{i})$ for all $i<N$. The same holds true for any $s\in 2^{<\omega}$ with $s_{M}\subseteq s\subseteq M$. Thus for no sentence $\phi$ with $[\phi]<[\hat{\psi}_{M}]$ does it hold that $s\subseteq M(\phi)$. On the other hand, $\hat{\psi}_{M}$ is a sentence and $s\subseteq M=M(\hat{\psi}_{M})$. Hence $[\psi_{M}]=\delta(s)$. QED.

Corollary. Let $M$ be a spectrum and $m\in 2^{\mathbb{N}}$ the corresponding dual element. Then the sequence $(\delta(m\vert n))_{n\in\mathbb{N}}$ converges in $\mathbb{N}$, ie terminates.

That is, every spectrum can be identified in terms of its minimal sentence, via $\delta$ and a sufficiently large finite fragment of itself viewed as an element of $2^{\mathbb{N}}$. The idea now, is to come up with a way for recursive sets to escape this property of being captured in this manner.

Claim 8. The map $s\mapsto D(s)$ is antitone und hence $s\mapsto\delta(s)$ is monotone. Pf. Let $s\subseteq s'$ in $2^{<\omega}$. For $\phi\in D(s')$ it holds that $s'\subseteq M(\phi)$, hence $s\subseteq M(\phi)$, hence $\phi\in D(s)$. Thus $D(s')\subseteq D(s)$. QED.

Claim 9. For all $s\in 2^{<\omega}$ there exists $s'\supset s$ in $2^{<\omega}$, such that $\delta(s')>\delta(s)$. In fact, one can choose $s'$ to be one element longer than $s$. Pf. By monotonicity (claim 8) it suffices to show that $\delta(s')\neq\delta(s)$ for some $s'\supset s$. Let $\phi$ be the sentence such that $[\phi]=\delta(s)$. Let $M=M(\phi)$. Now choose $s'\supset s$ to be longer by one element, with $s'\nsubseteq M$: ie if $|s|\in M$, set $s'=s^{\frown}0$ and if $|s|\notin M$, set $s'=s^{\frown}1$. Then $\phi\notin D(s')$, since $s'\nsubseteq M(\phi)$. Hence $\delta(s')\neq[\phi]$. QED.

Claim 10. The map $\alpha:s\in 2^{<\mathbb{N}}\mapsto \min_{\text{lex}}\{s'\in 2^{<\omega}:\delta(s')>\delta(s)\}$ is recursive and satisfies $|\alpha(s)|=|s|+1$. Pf. For a given $s$ one only has to choose between $s':=s^{\frown}0$ and $s':=s^{\frown}1$. By claim 9 one of these satisfies $\delta(s')>\delta(s)$. If both of them do, then one chooses the first one (this is then the lexical minimum). Since $\delta$ is recursive, checking each option is recursive. Hence $\alpha$ is well-defined and recursive. QED.

Construction. Appealing to these results of monotonicity and we now apply a typical trick of constructing an object, exhibitting too rapid a growth in terms of $\delta$ and its initial segments. The idea is to appeal to initial segments of the set being constructed to avoid being captured by a sentence.

Set $d_{0}=\langle\rangle\in 2^{<\omega}$ and $d_{n+1}=\alpha(d_{n})$ for each $n\in\mathbb{N}$. Set $\Delta:=\{k\in\mathbb{N}:d_{k+1}(k)=1\}$.

It is easy to show that the relation $\{(k,n):k<n~\wedge~d_{n}(k)=1\}$ is recursive (appealing to primitive recursion and the recursivity of $\alpha$), and thus that $\Delta$ is recursive. Furthermore, by strict monotonicity of $\alpha$ (see claim 10), one has

$d_{0}\subset d_{1}\subset d_{2}\subset\ldots$, and thus $d:=\bigcup_{n\in\mathbb{N}}d_{n}\in 2^{\mathbb{N}}$ and furthermore $\Delta=\{k\in\mathbb{N}:d(k)=1\}$.

Hence $\Delta$ is the dual object to the infinite 0-1-sequence $d$.

We finally show that $\Delta$ is not a spectrum. By the corollary to Claim 7, and since $d$ is the dual object to $\Delta$ it suffices to show that $(\delta(d\vert n))_{n\in\mathbb{N}}$ does not terminate. Note that by construction $d\vert n =d_{n}$ for all $n\in\mathbb{N}$. Further, by construction, one has $\delta(d_{n+1})=\delta(\alpha(d_{n}))>\delta(d_{n})$ for all $n\in\mathbb{N}$. Hence $\delta(d_{0})<\delta(d_{1})<\delta(d_{2})<\ldots$. Hence the sequence $(\delta(d\vert n))_{n\in\mathbb{N}}$ does not terminate. Thus by the corollary to Claim 7, $\Delta$ cannot be a spectrum.

Hence, $\Delta$ is a recursive set that is not a spectrum. QED.

Note the notation: for $s\in 2^{<\omega}$, $f\in 2^{\mathbb{N}}$ and $n<|s|$ I denote by $s\vert n$ and $f\vert n$ the restriction of these functions to $\{0,1,2,\ldots,n-1\}$. In set theory, one denotes this set simply as $n$, so this notation makes sense.