Suppose A is a linear order, possibly with countably many unary predicates added. We classify the isomorphism relation for countable models of Th\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {Th}$$\end{document} up to Borel bi-reducibility, showing there are exactly five possibilities and characterizing exactly when each can occur in simple model-theoretic terms. We show that if the language is finite, then the theory is ℵ0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\aleph _0$$\end{document}-categorical or Borel complete; this (...) generalizes a theorem due to Schirmann. (shrink)

We study the isomorphism relation on Borel classes of locally compact Polish metric structures. We prove that isomorphism on such classes is always classifiable by countable structures (equivalently: Borel reducible to graph isomorphism), which implies, in particular, that isometry of locally compact Polish metric spaces is Borel reducible to graph isomorphism. We show that potentially $\boldsymbol {\Pi }^{0}_{\alpha + 1}$ isomorphism relations are Borel reducible to equality on hereditarily countable sets of rank $\alpha $, $\alpha \geq 2$. We also study (...) approximations of the Hjorth-isomorphism game, and formulate a condition ruling out classifiability by countable structures. (shrink)

We investigate diagonal actions of Polish groups and the related intersection operator on closed subgroups of the acting group. The Borelness of the diagonal orbit equivalence relation is characterized and is shown to be connected with the Borelness of the intersection operator. We also consider relatively tame Polish groups and give a characterization of them in the class of countable products of countable abelian groups. Finally an example of a logic action is considered and its complexity in the Borel reducbility (...) hierarchy determined. (shrink)

Let ξ ≥ 1 be a countable ordinal. We study the Borel subsets of the plane that can be made [Formula: see text] by refining the Polish topology on the real line. These sets are called potentially [Formula: see text]. We give a Hurewicz-like test to recognize potentially [Formula: see text] sets.

In "A proof of Vaught's conjecture for ω-stable theories," the notions of ENI-NDOP and eni-depth have been introduced, which are variants of the notions of NDOP and depth known from Shelah's classification theory. First, we show that for an ω-stable first-order complete theory, ENI-NDOP allows tree decompositions of countable models. Then we discuss the relationship between eni-depth and the complexity of the isomorphism relation for countable models of such a theory in terms of Borel reducibility as introduced by Friedman and (...) Stanley and construct, in particular, a sequence of complete first-order ω-stable theories $(T_\alpha)_{\alpha < \omega_1}$ with increasing and cofinal eni-depth and isomorphism relations which are strictly increasing with respect to Borel reducibility. (shrink)

We present a countable complete first order theory T which is model theoretically very well behaved: it eliminates quantifiers, is ω-stable, it has NDOP and is shallow of depth two. On the other hand, there is no countable bound on the Scott heights of its countable models, which implies that the isomorphism relation for countable models is not Borel.

§1. I will start with a quick definition of descriptive set theory: It is the study of the structure of definable sets and functions in separable completely metrizable spaces. Such spaces are usually called Polish spaces. Typical examples are ℝn, ℂn, Hilbert space and more generally all separable Banach spaces, the Cantor space 2ℕ, the Baire space ℕℕ, the infinite symmetric group S∞, the unitary group, the group of measure preserving transformations of the unit interval, etc.In this theory sets are (...) classified in hierarchies according to the complexity of their definitions and the structure of sets in each level of these hierarchies is systematically analyzed. In the beginning we have the Borel sets in Polish spaces, obtained by starting with the open sets and closing under the operations of complementation and countable unions, and the corresponding Borel hierarchy. After this come the projective sets, obtained by starting with the Borel sets and closing under the operations of complementation and projection, and the corresponding projective hierarchy.There are also transfinite extensions of the projective hierarchy and even much more complex definable sets studied in descriptive set theory, but I will restrict myself here to Borel and projective sets, in fact just those at the first level of the projective hierarchy, i.e., the Borel (), analytic () and coanalytic () sets. (shrink)

This paper develops the foundations of the descriptive set theory of countable Borel equivalence relations on Polish spaces with particular emphasis on the study of hyperfinite, amenable, treeable and universal equivalence relations.

The study of continuous group actions is ubiquitous in mathematics, and perhaps the most general kinds of actions for which we can hope to prove theorems in just ZFC are those where a Polish group acts on a Polish space.For this general class we can find works such as [29] that build on ideas from ergodic theory and examine actions of locally compact groups in both the measure theoretic and topological contexts. On the other hand a text in model theory, (...) such as [12], will typically consider issues bearing on the actions by the symmetric group of all permutations of the integers. More generally [1] shows that the orbit equivalence relations induced by closed subgroups of the infinite symmetric group can be reduced to the isomorphism relation on corresponding classes of countable models.This paper considers a third category formed by the continuous actions of separable Banach spaces on Polish spaces. These examples cannot be subsumed under the two earlier headings, and it is known from [10] that theBorel cardinalitiesof the quotient spaces that arise from such actions are incomparable with the equivalence relations induced by the symmetric group or any locally compact Polish group action.One of the first things to be addressed concerns the complexity of these equivalence relations. This question forappears in [1]. (shrink)

We study the complexity of isomorphism of classes of metric structures using methods from infinitary continuous logic. For Borel classes of locally compact structures, we prove that if the equivalence relation of isomorphism is potentially $\mathbf {\Sigma }^0_2$, then it is essentially countable. We also provide an equivalent model-theoretic condition that is easy to check in practice. This theorem is a common generalization of a result of Hjorth about pseudo-connected metric spaces and a result of Hjorth–Kechris about discrete structures. As (...) a different application, we also give a new proof of Kechris’s theorem that orbit equivalence relations of actions of Polish locally compact groups are essentially countable. (shrink)

We introduce a new family of jump operators on Borel equivalence relations; specifically, for each countable group [Formula: see text] we introduce the [Formula: see text]-jump. We study the elementary properties of the [Formula: see text]-jumps and compare them with other previously studied jump operators. One of our main results is to establish that for many groups [Formula: see text], the [Formula: see text]-jump is proper in the sense that for any Borel equivalence relation [Formula: see text] the [Formula: see (...) text]-jump of [Formula: see text] is strictly higher than [Formula: see text] in the Borel reducibility hierarchy. On the other hand, there are examples of groups [Formula: see text] for which the [Formula: see text]-jump is not proper. To establish properness, we produce an analysis of Borel equivalence relations induced by continuous actions of the automorphism group of what we denote the full [Formula: see text]-tree, and relate these to iterates of the [Formula: see text]-jump. We also produce several new examples of equivalence relations that arise from applying the [Formula: see text]-jump to classically studied equivalence relations and derive generic ergodicity results related to these. We apply our results to show that the complexity of the isomorphism problem for countable scattered linear orders properly increases with the rank. (shrink)

A Polish group G is tame if for any continuous action of G, the corresponding orbit equivalence relation is Borel. When [Formula: see text] for countable abelian [Formula: see text], Solecki [Equivalence relations induced by actions of Polish groups, Trans. Amer. Math. Soc. 347 (1995) 4765–4777] gave a characterization for when G is tame. In [L. Ding and S. Gao, Non-archimedean abelian Polish groups and their actions, Adv. Math. 307 (2017) 312–343], Ding and Gao showed that for such G, the (...) orbit equivalence relation must in fact be potentially [Formula: see text], while conjecturing that the optimal bound could be [Formula: see text]. We show that the optimal bound is [Formula: see text] by constructing an action of such a group G which is not potentially [Formula: see text], and show how to modify the analysis of [L. Ding and S. Gao, Non-archimedean abelian Polish groups and their actions, Adv. Math. 307 (2017) 312–343] to get this slightly better upper bound. It follows, using the results of Hjorth et al. [Borel equivalence relations induced by actions of the symmetric group, Ann. Pure Appl. Logic 92 (1998) 63–112], that this is the optimal bound for the potential complexity of actions of tame abelian product groups. Our lower-bound analysis involves forcing over models of set theory where choice fails for sequences of finite sets. (shrink)