Recursive subsets of N\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 MNM\subseteq\mathbb{N}. Then MM a spectrum \Rightarrow MM recursive and the implication is strict.

Proof. (\Rightarrow.) Let MNM\subseteq\mathbb{N} be a spectrum. Then there exists a formula φ\varphi over σ\sigma, such that M={A:A a $\sigma$-structure, Aφ}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,,n1}\{0,1,\ldots,n-1\}. For any nn 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 nn satisfying φ\varphi. Hence MM 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(φ)NM(\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ω2^{\omega}.

Defn 3.

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

Defn 4.

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

Observation 5. δ\delta is well-defined: For every s2<ωs\in 2^{<\omega} one has at least sM(φs)s\subseteq M(\varphi_{s}) where φs:i<s, s(i)=1φi¬i<s, s(i)=0φi\varphi_{s}:\equiv\bigvee_{i<|s|,~s(i)=1}\varphi_{i}\wedge\neg\bigvee_{i<|s|,~s(i)=0}\varphi_{i} and φi:x0x1xn1i<j<nxixjx0x1xni<j<nxi=xj\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[φs]s\mapsto[\varphi_{s}] is recursive. Due to the above ramble about ‘everything’ being recursive, and since s[φs]s\mapsto[\varphi_{s}] yields a clearly recursive function providing upper bounds for the code of the minimal sentence in D(s)D(s), it holds that δ\delta is a recursive function.

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

The point of this construction is as follows.

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

Corollary. Let MM be a spectrum and m2Nm\in 2^{\mathbb{N}} the corresponding dual element. Then the sequence (δ(mn))nN(\delta(m\vert n))_{n\in\mathbb{N}} converges in N\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 2N2^{\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 sD(s)s\mapsto D(s) is antitone und hence sδ(s)s\mapsto\delta(s) is monotone. Pf. Let sss\subseteq s' in 2<ω2^{<\omega}. For ϕD(s)\phi\in D(s') it holds that sM(ϕ)s'\subseteq M(\phi), hence sM(ϕ)s\subseteq M(\phi), hence ϕD(s)\phi\in D(s). Thus D(s)D(s)D(s')\subseteq D(s). QED.

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

Claim 10. The map α:s2<Nminlex{s2<ω:δ(s)>δ(s)}\alpha:s\in 2^{<\mathbb{N}}\mapsto \min_{\text{lex}}\{s'\in 2^{<\omega}:\delta(s')>\delta(s)\} is recursive and satisfies α(s)=s+1|\alpha(s)|=|s|+1. Pf. For a given ss one only has to choose between s:=s0s':=s^{\frown}0 and s:=s1s':=s^{\frown}1. By claim 9 one of these satisfies δ(s)>δ(s)\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 d0=2<ωd_{0}=\langle\rangle\in 2^{<\omega} and dn+1=α(dn)d_{n+1}=\alpha(d_{n}) for each nNn\in\mathbb{N}. Set Δ:={kN:dk+1(k)=1}\Delta:=\{k\in\mathbb{N}:d_{k+1}(k)=1\}.

It is easy to show that the relation {(k,n):k<n  dn(k)=1}\{(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

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

Hence Δ\Delta is the dual object to the infinite 0-1-sequence dd.

We finally show that Δ\Delta is not a spectrum. By the corollary to Claim 7, and since dd is the dual object to Δ\Delta it suffices to show that (δ(dn))nN(\delta(d\vert n))_{n\in\mathbb{N}} does not terminate. Note that by construction dn=dnd\vert n =d_{n} for all nNn\in\mathbb{N}. Further, by construction, one has δ(dn+1)=δ(α(dn))>δ(dn)\delta(d_{n+1})=\delta(\alpha(d_{n}))>\delta(d_{n}) for all nNn\in\mathbb{N}. Hence δ(d0)<δ(d1)<δ(d2)<\delta(d_{0})<\delta(d_{1})<\delta(d_{2})<\ldots. Hence the sequence (δ(dn))nN(\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 s2<ωs\in 2^{<\omega}, f2Nf\in 2^{\mathbb{N}} and n<sn<|s| I denote by sns\vert n and fnf\vert n the restriction of these functions to {0,1,2,,n1}\{0,1,2,\ldots,n-1\}. In set theory, one denotes this set simply as nn, so this notation makes sense.

Note by R Mathe
1 year, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...