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

$</code> ... <code>$</code>...<code>."> 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 $</span> ... <span>$ or $</span> ... <span>$ 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.