«Abstract. We give a new deﬁnition of Scott rank motivated by our main theorem: For every countable structure A and ordinal α ω1, we have that: ...»
A ROBUSTER SCOTT RANK
Abstract. We give a new deﬁnition of Scott rank motivated by our main theorem: For
every countable structure A and ordinal α ω1, we have that: every automorphism orbit is
Σin -deﬁnable without parameters if and only if A has a Πin Scott sentence, if and only if A
α α+1 is uniformly boldface ∆0 -categorical. As a corollary, we show that a structure is computably α categorical on a cone if and only if it is the model of a countably categorical Σin sentence.
1. Introduction This paper has two main objectives. One is to introduce what the author believes is the right deﬁnition of Scott rank. The other is to provide a simple structural characterization for the notion of computable categoricity on a cone.
1.1. Scott ranks. The Scott rank measures the complexity of a structure in terms of the complexity of the automorphism orbits of its tuples. It is a very useful tool in inﬁnitary model theory, descriptive set theory, and computable structure theory. Its original formulation comes from Scott’s proof [Sco65] that every countable structure is the unique countable model of some Lω1,ω sentence. Since then, a few non-equivalent formulations of Scott rank have been proposed. We review them in Section 3.1.
It is known that the Scott rank of a structure is connected to the complexity of its Soctt sentence, which is connected to its level of categoricity, etc. One can prove that some of these measures of complexities provide upper and lower bounds for the others. Our main theorem exposes these connections in the sharpest possible way.
Let A be a countable structure and α be a countable ordinal. The following
(U1) Every automorphism orbit is Σin -deﬁnable without parameters.
α (U2) A has a Πin Scott sentence.
α+1 (U3) A is uniformly boldface ∆0 -categorical.
α Let us quickly explain the terms in the theorem. The “in” in Σin is for “inﬁnitary;” We α refer the reader to [AK00, Section 6.4] for background on the hierarchy of Lω1,ω formulas. The automorphism orbit of a tuple a in a structure A is the set of all other tuples automorphic to ¯ a. Since every deﬁnable set is a union of automorphism orbits, we have that (U1) is equivalent ¯ to saying that every Lω1,ω -deﬁnable relation in A is Σin -deﬁnable (deﬁnability being without α parameters). For (U2), recall that a Scott sentence for a countable structure A is an inﬁnitary sentence whose only countable model is A. Scott [Sco65] proved that such a sentences always exist. In other words, part (U2) says that A is the model of a countably categorical Πin α+1 sentence. Part (U3) refers to a diﬀerent notion of categoricity, the one used in computability theory. A structure is uniformly boldface ∆0 -categorical if it is uniformly ∆0 -categorical α α relative to some oracle; we will explain this in detail in Section 2.2.
Theorem 1.1 and its continuation below show the robustness of the statements (U1), (U2),
and (U3). Motivated by the theorem, we propose yet another notion of Scott rank:
In other words, the Scott rank of A is the least α satisfying the statements of Theorem 1.1.
We hope that having a robuster notion of Scott rank can help better understand it.
We continue our main theorem by adding four more properties. Depending on the background of the reader, some of these properties will sound more relevant than others. We will explain each of them brieﬂy right after the theorem, and in more detail later in the paper.
Theorem (1.1 continued). The following are also equivalent to (U1), (U2) and (U3):
The set of presentations of A is Π0 (U4) α+1 in the Borel hierarchy.
Every Πin -type realized in A is Σin -supported within A.
(U5) α α There is a Πin -sentence ϕ true of A such that if B |= ϕ, then B ≡α+1 A.
(U6) α+1 No tuple in A is α-free.
(U7) In (U4), we are referring to the set of presentations of A as a set of reals, and looking at its complexity from the viewpoint of descriptive set theory. The equivalence between (U4) and (U2) follows from Lopez-Escobar’s theorem [LE65], that says that a class of presentations of structures, closed under isomorphism, is Π0 in the Borel hierarchy if and only if it is β Πin -axiomatizable.
β For part (U5), a type p(¯) is Σin -supported within A if there is a Σin -formula ϕ(¯) that x x α α implies, within A, all the formulas in p(¯), and of course that is realized in A. Part (U5) x follows trivially from (U1), as the Σin -formula deﬁning the orbit clearly implies the Πin -type α α of the elements in the orbit. The reason we introduce this weakening of (U1) is that it will be very useful in our proof as a pivotal point to prove the rest of the statements.
In (U6), ≡α+1 refers to Σin -elementary equivalence, also known as (α + 1)-back-and-forth α+1 equivalence. Part (U6) follows trivially from (U2), as the Scott sentence of A serves as ϕ for (U6). The interesting feature about (U6) is that it implies that A has maximal under ≤α+1, which is a useful fact if one is trying to ﬁnd the structures that satisfy the theorem.
(See Subsection 2.3 for a deﬁnition of the (α + 1)-back-and-forth relations ≤α+1.) When K has countably many Πin -types (i.e. it is Σin -small–see [Mon]), (U6) is equivalent to A being α α maximal under ≤α+1 (as it follows from [Mon10, Lemma 2.2]). Thus, in classes where we have a good understanding of the ≤n -back-and-forth types, like Boolean algebras [HM12] for instance, we can ﬁnd the structures which satisfy Theorem 1.1 by searching for the ≤α+1 maximal ones.
Part (U7) is a very combinatorial property sometimes useful in proofs and constructions.
The notion of α-freeness was introduced by Ash and Knight and was used to give a characterization of ∆0 -categoricity for α-friendly structures. We will get back to this in Section α 2.3.
The proof of most of the equivalences in Theorem 1.1 are not particularly diﬃcult, and require putting together variations of various known results. The most interesting implication is (U2) ⇒ (U5), which uses a sharper version of the usual omitting types theorem for inﬁnitary logic. Once set up correctly, the proof of this omitting types theorem is very similar to the standard one. To avoid introducing the notions of consistency property, fragment, and other notions of inﬁnitary logic, we prove a variation better suited for our purposes.
a cone. The reader only interested in the inﬁnitary model theory part may skip this section and move on to Section 3.
2.1. Computable categoricity on a cone. The notion of computable categoricity, originally introduced by Mal’cev [Mal62], has been intensively studied in computability theory in the past decades. Many of the properties one considers in computable structure theory are not invariant under isomorphisms; that is, structures may have isomorphic computable presentations with diﬀerent computational properties. For instance, there are computable presentations of the countable, inﬁnite-dimensional Q-vector space, Q∞, where all the ﬁnitedimensional subspaces are computable, and computable presentations of Q∞ where no ﬁnitedimensional subspace is computable (see [DHK+ 07]). Computably categorical structures are
exactly the ones where this does not happen:
Deﬁnition 2.1. A computable structure A is computably categorical if there is a computable isomorphism between any two computable copies of A.
There has been a lot of work characterizing the computably categorical structures within certain classes of structures. Precise characterizations have been found for linear orders (Dzgoev and Goncharov [GD80]), Boolean algebras (Goncharov, and independently La Roche [LR78]), ordered abelian groups (Goncharov, Lempp, and Solomon [GLS03]), torsion-free abelian groups (Nurtazin [Nur74]), p-groups (Goncharov [Gon80] and Smith [Smi81]), trees of ﬁnite height (Lempp, McCoy, R. Miller, and Solomon [LMMS05]), etc.
On the other hand, there are many classes where we do not expect such characterization are even possible. Downey, Kach, Lempp, Lewis-Pye, Montalb´n and Turetsky [DKL+ ] recently a showed that there is no structural characterization for the notion of computable categoricity by showing that the index set of the computably categorical structures is Π1 -complete. In contrast, the relativized version of computable categoricity is relatively well-behaved, as proved by Goncharov [Gon75] long ago.
Deﬁnition 2.2. Given X ∈ 2ω, an X-computable structure A is X-computably categorical if there is an X-computable isomorphism between any two X-computable copies of A. A structure A is relatively computably categorical if it is X-computably categorical for all X ∈ 2ω.
Goncharov [Gon75] showed that a structure A is relative computably categorical if and only if it has a c.e. Scott family of ∃-formulas. In this paper, we look at a diﬀerent variation of the deﬁnition of computable categoricity that has an even nicer structural classiﬁcation.
Deﬁnition 2.3. A structure A is computably categorical on a cone if there is a Y ∈ 2ω such that A is X-computably categorical for all X ≥T Y.
We remark that, when we are looking at natural examples, most properties relativize.
Thus, for natural structures, the three notions, computable categoricity, relative computable categoricity and computable categoricity on a cone, coincide. As a corollary of Theorem 1.1, we get our second main result.
Theorem 2.4. Let A be a countable structure. The following are equivalent:
(1) A is computably categorical on a cone.
(2) A has a Σin Scott sentence.
Let us note that A has a Σin Scott sentence if and only if there exists a tuple a ∈ Aω such ¯ that (A, a) has a Πin -Scott sentence, which is equivalent to (A, a) having categoricity Scott ¯ ¯
rank 1. This generalizes through the transﬁnite in the expected way:
Let A be a countable structure and α a countable ordinal. The following are
4 ANTONIO MONTALBAN
The lightface version, with parameters, of the equivalence (U1) ⇔ (U7) appears in [AK00, Proposition 17.6 and Theorem 17.7] under the assumption that A satisﬁes an eﬀectiveness condition called α-friendliness. To show that (U1) ⇔ (U7), all we need to do is observe that every structure is α-friendly relative to a large enough oracle, and that (U1) is equivalent to saying that A has a Σc -Scott family on a cone. We also need to observe that the parameter-free α version of [AK00, Proposition 17.6 and Theorem 17.7] holds via almost the same proofs.
References[AK00] C.J. Ash and J. Knight. Computable Structures and the Hyperarithmetical Hierarchy. Elsevier Science, 2000.
[AKMS89] Chris Ash, Julia Knight, Mark Manasse, and Theodore Slaman. Generic copies of countable structures. Ann. Pure Appl. Logic, 42(3):195–205, 1989.
[Ash87] C. J. Ash. Categoricity in hyperarithmetical degrees. Ann. Pure Appl. Logic, 34(1):1–14, 1987.
[DHK03] R. Downey, D. Hirschfeldt, and B. Khoussainov. Uniformity in the theory of computable structures.
Algebra Logika, 42(5):566–593, 637, 2003.
[DHK+ 07] Downey, Hirschfeldt, Kach, Lempp, A. Montalb´n, and Mileti. Subspaces of computable vector a spaces. Journal of Algebra, 314(2):888–894, August 2007.
[DKL+ ] R. Downey, A. Kach, S. Lempp, A.E.M. Lewis-Pye, A. Montalb´n, and D. Turetsky. The complexity a of computable categoricity. Submitted for publication.
[Gao07] Su Gao. Complexity ranks of countable models. Notre Dame J. Formal Logic, 48(1):33–48 (electronic), 2007.
[GD80] S. S. Gonˇarov and V. D. Dzgoev. Autostability of models. Algebra i Logika, 19(1):45–58, 132, 1980.
c [GLS03] Sergey S. Goncharov, Steﬀen Lempp, and Reed Solomon. The computable dimension of ordered abelian groups. Adv. Math., 175(1):102–143, 2003.
[Gon75] S. S. Gonˇarov. Selfstability, and computable families of constructivizations. Algebra i Logika, c 14(6):647–680, 727, 1975.
[Gon80] Sergey S. Goncharov. Autostability of models and abelian groups. Algebra i Logika, 19(1):23–44, 132, 1980.
[HM12] Kenneth Harris and Antonio Montalb´n. On the n-back-and-forth types of Boolean algebras. Trans.
a Amer. Math. Soc., 364(2):827–866, 2012.
[Kei71] H. Jerome Keisler. Model theory for inﬁnitary logic. Logic with countable conjunctions and ﬁnite quantiﬁers. North-Holland Publishing Co., Amsterdam, 1971. Studies in Logic and the Foundations of Mathematics, Vol. 62.
[LE65] E. G. K. Lopez-Escobar. An interpolation theorem for denumerably long formulas. Fund. Math., 57:253–272, 1965.
[LMMS05] Steﬀen Lempp, Charles McCoy, Russell Miller, and Reed Solomon. Computable categoricity of trees of ﬁnite height. J. Symbolic Logic, 70(1):151–215, 2005.
[LR78] Peter E. La Roche. Contributions to Recursive Algebra. ProQuest LLC, Ann Arbor, MI, 1978. Thesis (Ph.D.)–Cornell University.
[Mal62] Anatolii I. Mal’cev. On recursive Abelian groups. Dokl. Akad. Nauk SSSR, 146:1009–1012, 1962.
[Mon] Antonio Montalb´n. Computability theoretic classiﬁcations for classes of structures. Submitted for a publication.
[Mon10] Antonio Montalb´n. Counting the back-and-forth types. Journal of Logic and Computability, page a doi: 10.1093/logcom/exq048, 2010.
[Nur74] A. T. Nurtazin. Computable classes and algebraic criteria for autostability. PhD thesis, Institute of Mathematics and Mechanics, Alma-Ata, 1974.
[Sac07] Gerald E. Sacks. Bounds on weak scattering. Notre Dame J. Formal Logic, 48(1):5–31, 2007.
[Sco65] Dana Scott. Logic with denumerably long formulas and ﬁnite strings of quantiﬁers. In Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), pages 329–341. North-Holland, Amsterdam, 1965.