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)

In the paper Randomizations of Scattered Sentences, Keisler showed that if Martin’s axiom for aleph one holds, then every scattered sentence has few separable randomizations, and asked whether the conclusion could be proved in ZFC alone. We show here that the answer is “yes”. It follows that the absolute Vaught conjecture holds if and only if every \-sentence with few separable randomizations has countably many countable models.

Suppose that $\sigma\in{\mathcal{L}}_{\omega _{1},\omega }$ is such that all equations occurring in $\sigma$ are positive, have the same set of variables on each side of the equality symbol, and have at least one function symbol on each side of the equality symbol. We show that $\sigma$ satisfies Vaught’s conjecture. In particular, this proves Vaught’s conjecture for sentences of $ {\mathcal{L}}_{\omega _{1},\omega }$ without equality.

The consistency of a second-order version of Morley’s Theorem on the number of countable models was proved in [EHMT23] with the aid of large cardinals. We here dispense with them.

We offer a topological treatment of scattered theories intended to help to explain the parallelism between, on the one hand, the theorems provable using Descriptive Set Theory by analysis of the space of countable models and, on the other, those provable by studying a tree of theories in a hierarchy of fragments of infinintary logic. We state some theorems which are, we hope, a step on the road to fully understanding counterexamples to Vaught's Conjecture. This framework is in the early (...) stages of development, and one area for future exploration is the possibility of extending it to a setting in which the spaces of types of a theory are uncountable. (shrink)

We give a model theoretic proof, replacing admissible set theory by the Lopez-Escobar theorem, of Makkai's theorem: Every counterexample to Vaught's Conjecture has an uncountable model which realizes only countably many ℒ$_{ω₁,ω}$-types. The following result is new. Theorem: If a first-order theory is a counterexample to the Vaught Conjecture then it has 2\sp ℵ₁ models of cardinality ℵ₁.

Let $T$ be a theory in a countable fragment of $\mathcal{L}_{\omega_{1},\omega}$ whose extensions in countable fragments have only countably many types. Sacks proves a bounding theorem that generates models of high Scott rank. For this theorem, a tree hierarchy is developed for $T$ that enumerates these extensions. In this paper, we effectively construct a predecessor function for formulas defining types in this tree hierarchy as follows. Let $T_{\gamma}\subseteq T_{\delta}$ with $T_{\gamma}$- and $T_{\delta}$-theories on level $\gamma$ and $\delta$, respectively. Then if (...) $\ulcorner p\urcorner $ is a formula that defines a type for $T_{\delta}$, our predecessor function provides a formula for defining its subtype in $T_{\gamma}$. By constructing this predecessor function, we weaken an assumption for Sacks’s result. (shrink)

The notion of a weakly scattered theory T is defined. T need not be scattered. For each a model of T, let sr() be the Scott rank of . Assume sr() ≤ ω\sp A \sb 1 for all a model of T. Let σ\sp T \sb 2 be the least Σ₂ admissible ordinal relative to T. If T admits effective k-splitting as defined in this paper, then θσ\cal Aθ\cal A$ a model of T.