Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence, in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work showing that certain classes of mathematical structures admit classification while others do not. In the present paper, we (...) describe some recent work on classification in computable structure theory.Section 1 gives some background from model theory and descriptive set theory. From model theory, we give sample structure and non-structure theorems for classes that include structures of arbitrary cardinality. We also describe the notion of Scott rank, which is useful in the more restricted setting of countable structures. From descriptive set theory, we describe the basic Polish space of structures for a fixed countable language with fixed countable universe. We give sample structure and non-structure theorems based on the complexity of the isomorphism relation, and on Borel embeddings.Section 2 gives some background on computable structures. We describe three approaches to classification for these structures. The approaches are all equivalent. However, one approach, which involves calculating the complexity of the isomorphism relation, has turned out to be more productive than the others. Section 3 describes results on the isomorphism relation for a number of mathematically interesting classes—various kinds of groups and fields. In Section 4, we consider a setting similar to that in descriptive set theory. We describe an effective analogue of Borel embedding which allows us to make distinctions even among classes of finite structures. Section 5 gives results on computable structures of high Scott rank. Some of these results make use of computable embeddings. Finally, in Section 6, we mention some open problems and possible directions for future work. (shrink)

Every countable structure has a sentence of the infinitary logic $\mathcal {L}_{\omega _1 \omega }$ which characterizes that structure up to isomorphism among countable structures. Such a sentence is called a Scott sentence, and can be thought of as a description of the structure. The least complexity of a Scott sentence for a structure can be thought of as a measurement of the complexity of describing the structure. We begin with an introduction to the area, with short and simple proofs (...) where possible, followed by a survey of recent advances. (shrink)

We calculate the complexity of Scott sentences of scattered linear orders. Given a countable scattered linear order L of Hausdorff rank $\alpha $ we show that it has a ${d\text {-}\Sigma _{2\alpha +1}}$ Scott sentence. It follows from results of Ash [2] that for every countable $\alpha $ there is a linear order whose optimal Scott sentence has this complexity. Therefore, our bounds are tight. We furthermore show that every Hausdorff rank 1 linear order has an optimal ${\Pi ^{\mathrm {c}}_{3}}$ (...) or ${d\text {-}\Sigma ^{\mathrm {c}}_{3}}$ Scott sentence and give a characterization of those linear orders of rank $1$ with ${\Pi ^{\mathrm {c}}_{3}}$ optimal Scott sentences. At last we show that for all countable $\alpha $ the class of Hausdorff rank $\alpha $ linear orders is $\boldsymbol {\Sigma }_{2\alpha +2}$ complete and obtain analogous results for index sets of computable linear orders. (shrink)

If [Formula: see text] is a proper Polish metric space and [Formula: see text] is any countable dense submetric space of [Formula: see text], then the Scott rank of [Formula: see text] in the natural first-order language of metric spaces is countable and in fact at most [Formula: see text], where [Formula: see text] is the Church–Kleene ordinal of [Formula: see text] which is the least ordinal with no presentation on [Formula: see text] computable from [Formula: see text]. If [Formula: (...) see text] is a rigid Polish metric space and [Formula: see text] is any countable dense submetric space, then the Scott rank of [Formula: see text] is countable and in fact less than [Formula: see text]. (shrink)

Using the theory of Borel equivalence relations we analyze the isomorphism relation on the countable models of a theory and develop a framework for measuring the complexity of possible complete invariants for isomorphism.

Strengthening known instances of Vaught Conjecture, we prove the Glimm-Effros dichotomy theorems for countable linear orderings and for simple trees. Corollaries of the theorems answer some open questions of Friedman and Stanley in an L ω 1ω -interpretability theory. We also give a survey of this theory.

Makkai [10] produced an arithmetical structure of Scott rank $\omega _{1}^{\mathit{CK}}$. In [9]. Makkai's example is made computable. Here we show that there are computable trees of Scott rank $\omega _{1}^{\mathit{CK}}$. We introduce a notion of "rank homogeneity". In rank homogeneous trees, orbits of tuples can be understood relatively easily. By using these trees, we avoid the need to pass to the more complicated "group trees" of [10] and [9]. Using the same kind of trees, we obtain one of rank (...) $\omega _{1}^{\mathit{CK}}$ that is "strongly computably approximable". We also develop some technology that may yield further results of this kind. (shrink)

This paper presents an approach to truth and the Liar paradox which combines elements of context dependence and hierarchy. This approach is developed formally, using the techniques of model theory in admissible sets. Special attention is paid to showing how starting with some ideas about context drawn from linguistics and philosophy of language, we can see the Liar sentence to be context dependent. Once this context dependence is properly understood, it is argued, a hierarchical structure emerges which is neither ad (...) hoc nor unnatural. (shrink)

Computable structures of Scott rank ${\omega_1^{CK}}$ are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of ${\mathcal{L}_{\omega_1 \omega}}$ , this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank ${\omega_1^{CK}}$ whose computable infinitary theories are each ${\aleph_0}$ -categorical. General conditions are given, covering many known methods for constructing computable structures with Scott rank ${\omega_1^{CK}}$ , which guarantee that the (...) resulting structure is a model of an ${\aleph_0}$ -categorical computable infinitary theory. (shrink)

The Hanf number for a set S of sentences in \ is the least infinite cardinal \ such that for all \, if \ has models in all infinite cardinalities less than \, then it has models of all infinite cardinalities. Friedman asked what is the Hanf number for Scott sentences of computable structures. We show that the value is \. The same argument proves that \ is the Hanf number for Scott sentences of hyperarithmetical structures.

This paper calculates, in a precise way, the complexity of the index sets for three classes of computable structures: the class $K_{\omega _{1}^{\mathit{CK}}}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}$ , the class $K_{\omega _{1}^{\mathit{CK}}+1}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}+1$ , and the class K of all structures of non-computable Scott rank. We show that I(K) is m-complete $\Sigma _{1}^{1},\,I(K_{\omega _{1}^{\mathit{CK}}})$ is m-complete $\Pi _{2}^{0}$ relative to Kleen's O, and $I(K_{\omega _{1}^{\mathit{CK}}+1})$ is m-complete $\Sigma _{2}^{0}$ relative to O.

Let M be a structure for a language L on a set M of urelements. HYP(M) is the least admissible set above M. In § 1 we show that pp(HYP(M)) [ = the collection of pure sets in HYP(M] is determined in a simple way by the ordinal α = ⚬(HYP(M)) and the $\mathscr{L}_{\propto\omega}$ theory of M up to quantifier rank α. In § 2 we consider the question of which pure countable admissible sets are of the form pp(HYP(M)) for (...) some M and show that all sets L α (α admissible) are of this form. Other positive and negative results on this question are obtained. (shrink)

In recent years higher recursion theory has experienced a deep interaction with other areas of logic, particularly set theory (fine structure, forcing, and combinatorics) and infinitary model theory. In this paper we wish to illustrate this interaction by surveying the progress that has been made in two areas: the global theory of the κ-degrees and the study of closure ordinals.

§0. Introduction. In [16], Barwise described his graduate study at Stanford. He told of his interactions with Kreisel and Scott, and said how he chose Feferman as his advisor. He began working on admissible fragments of infinitary logic after reading and giving seminar talks on two Ph.D. theses which had recently been completed: that of Lopez-Escobar, at Berkeley, on infinitary logic [46], and that of Platek [58], at Stanford, on admissible sets.Barwise's work on infinitary logic and admissible sets is described (...) in his thesis [4], the book [13], and papers [5]—[16]. We do not try to give a systematic review of these papers. Instead, our goal is to give a coherent introduction to infinitary logic and admissible sets. We describe results of Barwise, of course, because he did so much. In addition, we mention some more recent work, to indicate the current importance of Barwise's ideas. Many of the central results are stated without proof, but occasionally we sketch a proof, to indicate how the ideas fit together.Chapters 1 and 2 describe infinitary logic and admissible sets at the time Barwise began his work, circa 1965. From Chapter 3 on, we survey the developments that took place after Barwise appeared on the scene.§1. Background on infinitary logic. In this chapter, we describe the situation in infinitary logic at the time that Barwise began his work. We need some terminology. By a vocabulary, we mean a set L of constant symbols, and relation and operation symbols with finitely many argument places. As usual, by an L-structureM, we mean a universe set M with an interpretation for each symbol of L. (shrink)

We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$, $\Pi _{\alpha }$, or $\mathrm {d-}\Sigma _{\alpha }$. We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit (...) ordinal. This answers a question left open by A. Miller.We also construct examples of computable structures of high Scott rank with Scott complexities $\Sigma _{\omega _1^{CK}+1}$ and $\mathrm {d-}\Sigma _{\omega _1^{CK}+1}$. There are three other possible Scott complexities for a computable structure of high Scott rank: $\Pi _{\omega _1^{CK}}$, $\Pi _{\omega _1^{CK}+1}$, $\Sigma _{\omega _1^{CK}+1}$. Examples of these were already known. Our examples are computable structures of Scott rank $\omega _1^{CK}+1$ which, after naming finitely many constants, have Scott rank $\omega _1^{CK}$. The existence of such structures was an open question. (shrink)

There exists a countable structure of Scott rank where and where the -theory of is not ω-categorical. The Scott rank of a model is the least ordinal β where the model is prime in its -theory. Most well-known models with unbounded atoms below also realize a non-principal -type; such a model that preserves the Σ1-admissibility of will have Scott rank . Makkai [M. Makkai, An example concerning Scott heights, J. Symbolic Logic 46 301–318. [4]] produces a hyperarithmetical model of Scott (...) rank whose -theory is ω-categorical. A computable variant of Makkai’s example is produced in [W. Calvert, S.S. Goncharov, J.F. Knight, J. Millar, Categoricity of computable infinitary theories, Arch. Math. Logic . [1]; J. Knight, J. Millar, Computable structures of rank J. Math. Logic . [2]]. (shrink)

We extend a theorem of Barwise and Nadel describing the relationship between approximations of canonical Scott sentences and admissible sets to the case of orbit equivalence relations induced on an arbitrary Polish space by a Polish group action.

Hjorth introduced a Scott analysis for general Polish group actions, and asked whether his notion of rank satisfies a boundedness principle similar to the one of Scott rank—namely, if the orbit equivalence relation is Borel, then Hjorth ranks are bounded. We answer Hjorth’s question positively. As a corollary we prove the following conjecture of Hjorth—for every limit ordinal \, the set of elements whose orbit is of complexity less than \ is a Borel set.

Let G be a closed subgroup of S∞ and X be a Polish G -space. To every x ∈ X we associate an admissible set Ax and show how questions about X which involve Baire category can be formalized in Ax.

The first main result isolates some conditions which fail for the class of graphs and hold for the class of Abelian p-groups, the class of Abelian torsion groups, and the special class of "rank-homogeneous" trees. We consider these conditions as a possible definition of what it means for a class of structures to have "Ulm type". The result says that there can be no Turing computable embedding of a class not of Ulm type into one of Ulm type. We apply (...) this result to show that there is no Turing computable embedding of the class of graphs into the class of "rank-homogeneous" trees. The second main result says that there is a Turing computable embedding of the class of rank-homogeneous trees into the class of torsion-free Abelian groups. The third main result says that there is a "rank-preserving" Turing computable embedding of the class of rank-homogeneous trees into the class of Boolean algebras. Using this result, we show that there is a computable Boolean algebra of Scott rank ${\mathrm{\omega }}_{1}^{\mathrm{C}\mathrm{K}}$. (shrink)