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 . Then a spectrum recursive and the implication is strict.
Proof. (.) Let be a spectrum. Then there exists a formula over , such that . Since the elements of a structure do not matter, and only finitely many symbols occur in , it suffices to restrict to models of finite signature with domains of the form . For any there are thus only finitely many -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 satisfying . Hence is recursive.
(.) Wlog we restrict to a countably infinite vocabulary, , with countably infinitely many relations all arities, function all arities and constants. We also enumerate the symbols such that it everything is recursive: determining whether or not a (code for a) formula is a well defined formula, whether or not a -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 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 , ie iff . Note that each formula has necessarily only finitely many -predecessors.
Defn 2. For any -sentence, , let denote the spectrum of . In the following subsets of naturals will be occasionally be viewed dually as an element of .
For set .
Observation 5. is well-defined: For every one has at least where and . It is easy to show that the map is recursive. Due to the above ramble about ‘everything’ being recursive, and since yields a clearly recursive function providing upper bounds for the code of the minimal sentence in , it holds that is a recursive function.
Defn 6. For any spectrum, , let denote the -minimal sentence with .
The point of this construction is as follows.
Claim 7. For all spectra, there exists sufficiently large, such that for all with it holds that . Pf. Consider all sentences with . There are only finitely many of these! List them out: . Due to minimality, for all . Since there are only finitely many sets here, and viewing these dually as elements of , there exists a finite segment so that for all . The same holds true for any with . Thus for no sentence with does it hold that . On the other hand, is a sentence and . Hence . QED.
Corollary. Let be a spectrum and the corresponding dual element. Then the sequence converges in , ie terminates.
That is, every spectrum can be identified in terms of its minimal sentence, via and a sufficiently large finite fragment of itself viewed as an element of . 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 is antitone und hence is monotone. Pf. Let in . For it holds that , hence , hence . Thus . QED.
Claim 9. For all there exists in , such that . In fact, one can choose to be one element longer than . Pf. By monotonicity (claim 8) it suffices to show that for some . Let be the sentence such that . Let . Now choose to be longer by one element, with : ie if , set and if , set . Then , since . Hence . QED.
Claim 10. The map is recursive and satisfies . Pf. For a given one only has to choose between and . By claim 9 one of these satisfies . If both of them do, then one chooses the first one (this is then the lexical minimum). Since is recursive, checking each option is recursive. Hence 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 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 and for each . Set .
It is easy to show that the relation is recursive (appealing to primitive recursion and the recursivity of ), and thus that is recursive. Furthermore, by strict monotonicity of (see claim 10), one has
, and thus and furthermore .
Hence is the dual object to the infinite 0-1-sequence .
We finally show that is not a spectrum. By the corollary to Claim 7, and since is the dual object to it suffices to show that does not terminate. Note that by construction for all . Further, by construction, one has for all . Hence . Hence the sequence does not terminate. Thus by the corollary to Claim 7, cannot be a spectrum.
Hence, is a recursive set that is not a spectrum. QED.
Note the notation: for , and I denote by and the restriction of these functions to . In set theory, one denotes this set simply as , so this notation makes sense.