I wanted to write my solution to [**Agnishom’s**] [problem](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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

There are no comments in this discussion.