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)

Let , be a sequence of pseudo-metric spaces, and let p≥1. For , let . For Borel reducibility between equivalence relations , we show it is closely related to finitely Hölder embeddability between pseudo-metric spaces.

We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set $= \omega$, of an $L_{\omega_1\omega}$ sentence; from this point of view, the reducibility can be thought (...) of as a (rather weak) sort of $L_{\omega_1\omega}$-interpretability notion). We prove a number of general results about this notion, but our main thrust is to situate various mathematically natural classes with respect to the preordering, most notably classes of algebraic structures such as groups and fields. (shrink)

We announce some new results regarding the classification problem for separable von Neumann algebras. Our results are obtained by applying the notion of Borel reducibility and Hjorth's theory of turbulence to the isomorphism relation for separable von Neumann algebras.

We investigate Borel reducibility between equivalence relations $E(X;p)=X^{\mathbb{N}}/\ell_{p}(X)'s$ where X is a separable Banach space. We show that this reducibility is related to the so called Hölder(α) embeddability between Banach spaces. By using the notions of type and cotype of Banach spaces, we present many results on reducibility and unreducibility between E(L r ; p)'s and E(c 0 ; p)'s for r, p ∈ [1, +∞). We also answer a problem presented by Kanovei in the affirmative (...) by showing that $\mathrm{C}\left({\mathrm{\mathbb{R}}}^{+}\right)/{\mathrm{C}}_{0}\left({\mathrm{\mathbb{R}}}^{+}\ri ght)$ is Borel bireducible to $\mathbb{R}^{\mathbb{N}}/c_{0}$. (shrink)

We study the κ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa $$\end{document}-Borel-reducibility of isomorphism relations of complete first order theories in a countable language and show the consistency of the following: For all such theories T and T′\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T^{\prime }$$\end{document}, if T is classifiable and T′\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T^{\prime }$$\end{document} is not, then the isomorphism of models of T′\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} (...) \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T^{\prime }$$\end{document} is strictly above the isomorphism of models of T with respect to κ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa $$\end{document}-Borel-reducibility. In fact, we can also ensure that a range of equivalence relations modulo various non-stationary ideals are strictly between those isomorphism relations. The isomorphism relations are considered on models of some fixed uncountable cardinality obeying certain restrictions. (shrink)

In [9] we have considered a wide class of "well-behaved" reducibilities for sets of reals. In this paper we continue with the study of Borel reducibilities by proving a dichotomy theorem for the degree-structures induced by good Borel reducibilities. This extends and improves the results of [9] allowing to deal with a larger class of notions of reduction (including, among others, the Baire class ξ functions).

The Borel reducibility theory of Polish equivalence relations, at least in its present form, was initiated independently in [FS89] and [HKL90]. There is now an extensive literature on this topic, including fundamental work on the Glimm-Effros dichotomy in [HKL90], on countable Borel equivalence relations in [DJK94], and on Polish group actions in [BK96].

We analyze the degree-structure induced by large reducibilities under the Axiom of Determinacy. This generalizes the analysis of Borel reducibilities given in Alessandro Andretta and Donald A. Martin [1], Luca Motto Ros [6] and Luca Motto Ros. [5] e.g. to the projective levels.

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and (...) corresponding complete functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya-Srivastava in order to prove a generalization of the Representation Theorem of Kreitz-Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach-Hausdorff-Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (shrink)

We show that if Ƒ is any "well-behaved" subset of the Borei functions and we assume the Axiom of Determinacy then the hierarchy of degrees on $P(^\omega \omega )$ induced by Ƒ turns out to look like the Wadge hierarchy (which is the special case where Ƒ is the set of continuous functions).

We construct two Borel equivalence relations on the generalized Baire space κκ, κ ω, with the property that neither of them is Borel reducible to the other. A small modification of the construction shows that the straightforward generalization of the Glimm-Effros dichotomy fails.

There is an ergodic, measure preserving, countable Borel equivalence relation E on a standard Borel probability space (X, µ) such that E\c is not essentially free on any conull C ⊂ X.

We formulate a Borel version of a corollary of Furman's superrigidity theorem for orbit equivalence and present a number of applications to the theory of countable Borel equivalence relations. In particular, we prove that the orbit equivalence relations arising from the natural actions of on the projective planes over the various p-adic fields are pairwise incomparable with respect to Borel reducibility.

We announce two new dichotomy theorems for Borel equivalence relations, and present the results in context by giving an overview of related recent developments.§1. Introduction. For X a Polish space and E a Borel equivalence relation on X, a classification of X up to E-equivalence consists of finding a set of invariants I and a map c : X → I such that xEy ⇔ c = c. To be of any value we would expect I and c (...) to be “explicit” or “definable”. The theory of Borel equivalence relations investigates the nature of possible invariants and provides a hierarchy of notions of classification.The following partial ordering is fundamental in organizing this study. Given equivalence relations E and F on X and Y, resp., we say that E can be Borel reduced to F, in symbolsif there is a Borel map f : X → Y with xEy ⇔ fFf. Then if is an embedding of X/E into Y/F, which is “Borel”.Intuitively, E ≤BF might be interpreted in any one of the following ways: The classi.cation problem for E is simpler than that of F: any invariants for F work as well for E. One can classify E by using as invariants F-equivalence classes. The quotient space X/E has “Borel cardinality” less than or equal to that of Y/F, in the sense that there is a “Borel” embedding of X/E into Y/F. (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.

It is shown that the power set of $\kappa$ ordered by the subset relation modulo various versions of the non-stationary ideal can be embedded into the partial order of Borel equivalence relations on $2^\kappa$ under Borel reducibility. Here $\kappa$ is an uncountable regular cardinal with $\kappa^{<\kappa}=\kappa$.

We prove Borel superrigidity results for suitably chosen actions of groups of the form SL2, where {p1, …, pt} is a finite nonempty set of primes, and present a number of applications to the theory of countable Borel equivalence relations. In particular, for each prime q, we prove that the orbit equivalence relations arising from the natural actions of SL2 on the projective lines ℚp ∪ {∞}, p ≠ q, over the various p-adic fields are pairwise incomparable with (...) respect to Borel reducibility. (shrink)

The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver [20] and Harrington, Kechris and Louveau [6] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on ω is above equality on , the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on . (...) In this article we examine the effective content of these and related results by studying effectively Borel equivalence relations under effectively Borel reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene’s O as a parameter is sufficient to restore the picture from the noneffective setting. A key lemma is that of the existence of two effectively Borel sets of reals, neither of which contains the range of the other under any effectively Borel function; the proof of this result applies Barwise compactness to a deep theorem of Harrington establishing for any recursive ordinal α the existence of singletons whose α-jumps are Turing incomparable. (shrink)

Working under large cardinal assumptions such as supercompactness, we study the Borel reducibility between equivalence relations modulo restrictions of the nonstationary ideal on some fixed cardinal κ. We show the consistency of Eλ-clubλ++,λ++, the relation of equivalence modulo the nonstationary ideal restricted to Sλλ++ in the space λ++, being continuously reducible to Eλ+-club2,λ++, the relation of equivalence modulo the nonstationary ideal restricted to Sλ+λ++ in the space 2λ++. Then we show that for κ ineffable Ereg2,κ, the relation of (...) equivalence modulo the nonstationary ideal restricted to regular cardinals in the space 2κ is Σ11-complete. We finish by showing that, for Π21-indescribable κ, the isomorphism relation between dense linear orders of cardinality κ is Σ11-complete. (shrink)

Families of Borel equivalence relations and quasiorders that are cofinal with respect to the Borel reducibility ordering, ≤B, are constructed. There is an analytic ideal on ω generating a complete analytic equivalence relation and any Borel equivalence relation reduces to one generated by a Borel ideal. Several Borel equivalence relations, among them Lipschitz isomorphism of compact metric spaces, are shown to be Kσ complete.

We study the Borel reducibility of isomorphism relations in the generalized Baire space. In the main result we show for inaccessible κ, that if T is a classifiable theory and is stable with the orthogonal chain property (OCP), then the isomorphism of models of T is Borel reducible to the isomorphism of models of.

We show that there is an antichain basis for neither the class of non-potentially closed Borel subsets of the plane under Borel rectangular reducibility nor the class of analytic graphs of uncountable Borel chromatic number under Borel reducibility.

If is a Polish metric space of dimension 0, then by Wadge’s lemma, no more than two Borel subsets of X are incomparable with respect to continuous reducibility. In contrast, our main result shows that for any metric space of positive dimension, there are uncountably many Borel subsets of that are pairwise incomparable with respect to continuous reducibility. In general, the reducibility that is given by the collection of continuous functions on a topological space \\) (...) is called the Wadge quasi-order for \\). As an application of the main result, we show that this quasi-order, restricted to the Borel subsets of a Polish space \\), is a well-quasiorder if and only if \\) has dimension 0. Moreover, we give further examples of applications of the construction of graph colorings that is used in the proofs. (shrink)

We consider Borel sets of finite rank $A \subseteq\Lambda^\omega$ where cardinality of Λ is less than some uncountable regular cardinal K. We obtain a "normal form" of A, by finding a Borel set Ω, such that A and Ω continuously reduce to each other. In more technical terms: we define simple Borel operations which are homomorphic to ordinal sum, to multiplication by a countable ordinal, and to ordinal exponentiation of base K, under the map which sends every (...) Borel set A of finite rank to its Wadge degree. (shrink)

A number of results have been obtained concerning Borel structures starting with Silver and Friedman followed by Harrington, Shelah, Marker, and Louveau. Friedman also initiated the model theory of Borel (in fact totally Borel) structures. By this we mean the study of the class of Borel models of a given first-order theory. The subject was further investigated by Steinhorn. The present work is meant to go further in this direction. It is based on the assumption that (...) the study of the class of, say, countable models of a theory reduces to analyzing a single $\omega_1$-saturated model. The question then arises as to when such a model can be totally Borel. We present here a partial answer to this problem when the theory under investigation is superstable. (shrink)

Let A and B be subsets of the space 2 N of sets of natural numbers. A is said to be Wadge reducible to B if there is a continuous map Φ from 2 N into 2 N such that A = Φ -1 (B); A is said to be monotone reducible to B if in addition the map Φ is monotone, that is, $a \subset b$ implies $\Phi (a) \subset \Phi(b)$ . The set A is said to be monotone (...) if a ∈ A and $a \subset b$ imply b ∈ A. For monotone sets, it is shown that, as for Wadge reducibility, sets low in the arithmetical hierarchy are nicely ordered. The ▵ 0 1 sets are all reducible to the (Σ 0 1 but not ▵ 0 1 ) sets, which are in turn all reducible to the strictly ▵ 0 2 sets, which are all in turn reducible to the strictly Σ 0 2 sets. In addition, the nontrivial Σ 0 n sets all have the same degree for n ≤ 2. For Wadge reducibility, these results extend throughout the Borel hierarchy. In contrast, we give two natural strictly Π 0 2 monotone sets which have different monotone degrees. We show that every Σ 0 2 monotone set is actually Σ 0 2 positive. We also consider reducibility for subsets of the space of compact subsets of 2 N . This leads to the result that the finitely iterated Cantor-Bendixson derivative D n is a Borel map of class exactly 2n, which answers a question of Kuratowski. (shrink)

Let E be an analytic equivalence relation on a Polish space. We introduce a framework for studying the possible “reasonable” complete classifications and the complexity of possible classifying invariants for E, such that: (1) the standard results and intuitions regarding classifications by countable structures are preserved in this framework; (2) this framework respects Borel reducibility; and (3) this framework allows for a precise study of the possible invariants of certain equivalence relations which are not classifiable by countable structures, (...) such as E1. In this framework we show that E1 can be classified, with classifying invariants which are κ-sequences of E0-classes where κ=b, and it cannot be classified in such a manner if κshrink)

We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by these relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a $\boldsymbol {\Sigma }^1_1$ complete equivalence relation. We then investigate the algorithmic properties of this reduction. We obtain that elementary bi-embeddability on the class of computable graphs is $\Sigma ^1_1$ (...) complete with respect to computable reducibility and show that the elementary bi-embeddability and bi-embeddability spectra realized by graphs are related. (shrink)

Louveau and Rosendal [5] have shown that the relation of bi-embeddability for countable graphs as well as for many other natural classes of countable structures is complete under Borel reducibility for analytic equivalence relations. This is in strong contrast to the case of the isomorphism relation, which as an equivalence relation on graphs (or on any class of countable structures consisting of the models of a sentence of L ω ₁ ω ) is far from complete (see [5, (...) 2]). In this article we strengthen the results of [5] by showing that not only does bi-embeddability give rise to analytic equivalence relations which are complete under Borel reducibility, but in fact any analytic equivalence relation is Borel equivalent to such a relation. This result and the techniques introduced answer questions raised in [5] about the comparison between isomorphism and bi-embeddability. Finally, as in [5] our results apply not only to classes of countable structures defined by sentences of ω ₁ ω , but also to discrete metric or ultrametric Polish spaces, compact metrizable topological spaces and separable Banach spaces, with various notions of embeddability appropriate for these classes, as well as to actions of Polish monoids. (shrink)

This thesis is divided into three parts, the first and second ones focused on combinatorics and classification problems on discrete and geometrical objects in the context of descriptive set theory, and the third one on generalized descriptive set theory at singular cardinals of countable cofinality.Descriptive Set Theory (briefly: DST) is the study of definable subsets of Polish spaces, i.e., separable completely metrizable spaces. One of the major branches of DST is Borel reducibility, successfully used in the last 30 (...) years to solve and compare many classification problems. One of our goals is the classification of knots, very familiar and tangible objects in everyday life, which also play an important role in modern mathematics. The study of knots and their properties is known as knot theory. Our plan is to gain insight into knots using discrete objects, such as linear and circular orders. This approach was already exploited in [6]. The first part of this work is therefore devoted to countable linear orders and the study of the quasi-order of convex embeddability and its induced equivalence relation. We obtain both combinatorial and descriptive set-theoretic results. We also expand our research to the case of circular orders.Another objective of this first part is to extend the notion of convex embeddability on countable linear orders. We provide a family of quasi-orders of which embeddability is a particular case as well. We study these quasi-orders from a combinatorial point of view and analyse their complexity with respect to Borel reducibility. Furthermore, we extend the analysis of these quasi-orders to the set of uncountable linear orders.The second part of the project deals with classification problems on knots and $3$ -manifolds. The goal here is to apply the results obtained in the first part to the study of proper arcs and knots, establishing lower bounds for the complexity of some natural relations between these geometrical objects. We also obtain some combinatorial results which are particularly interesting when we restrict to the set of wild proper arcs and wild knots, classes which haven’t received much attention so far. These parts are included in the two preprints [4, 5] in collaboration with my supervisor Alberto Marcone, Luca Motto Ros (University of Torino), and Vadim Weinstein (University of Oulu).The second part of this work also includes the classification of non-compact $3$ -manifolds up to homeomorphism (the case of compact $3$ -manifolds has already been solved: indeed, there are only countably many $3$ -manifolds up to homeomorphism; see [7]), and that of Cantor sets of $\mathbb {R}^3$ up to conjugation (answering to Question 5.5 of [3]). Here we resort to algebraic tools. Stone duality gives a neat way to go back-and-forth between totally disconnected Polish spaces and countable Boolean algebras (see [1]). The main ingredient is the Stone space of all ultrafilters on a Boolean algebra. In this work we introduce a weaker concept which we call “blurry filter”. Using blurry filters instead of ultrafilters enables one to extend the class of spaces under consideration beyond totally disconnected. As an application of this method, we show that both homeomorphism on non-compact $3$ -manifolds and conjugation of Cantor sets in $\mathbb {R}^3$ are completely classifiable by countable structures. These results are part of an upcoming paper in collaboration with Vadim Weinstein.The last part of this thesis concerns the natural generalization of descriptive set theory that occurs when countable is replaced by uncountable, called Generalized Descriptive Set Theory (briefly: GDST). In particular, we focus on the case of GDST for a singular cardinal $\kappa $ of countable cofinality. The goal here is to study the generalizations of the Perfect Set Property and the Baire Property to subsets of spaces of higher cardinalities, like the power set $\mathcal {P}(\kappa )$. We consider the question under which large cardinal hypotheses classes of definable subsets of these spaces possess such regularity properties, focusing on rank-into-rank axioms, like I2, and classes of sets definable by $\Sigma _1$ -formulas with parameters from various collections of sets. The obtained results are included in [2], a joint work with my co-supervisor Vincenzo Dimonte and Philipp Lücke (University of Hamburg).Abstract prepared by Martina IannellaE-mail: [email protected]: https://air.uniud.it/handle/11390/1262824. (shrink)

Let ⪯R be the preorder of embeddability between countable linear orders colored with elements of Rado's partial order . We show that ⪯R has fairly high complexity with respect to Borel reducibility , although its exact classification remains open.

We work in the context of ω-stable theories. We obtain a natural, algebraic equivalent of ENI-NDOP and discuss recent joint proofs with Shelah that if an ω-stable theory has either ENI-DOP or is ENI-NDOP and is ENI-deep, then the set of models of T with universe ω is Borel complete.

We introduce and study the framework of compact metric structures and their associated notions of isomorphisms such as homeomorphic and bi-Lipschitz isomorphism. This is subsequently applied to model various classification problems in analysis such as isomorphism ofC*-algebras and affine homeomorphism of Choquet simplices, where among other things we provide a simple proof of the completeness of the isomorphism relation of separable, simple, nuclearC*-algebras recently established by M. Sabok.

We study the $\kappa $ -Borel-reducibility of isomorphism relations of complete first-order theories by using coloured trees. Under some cardinality assumptions, we show the following: For all theories T and T’, if T is classifiable and T’ is unsuperstable, then the isomorphism of models of T’ is strictly above the isomorphism of models of T with respect to $\kappa $ -Borel-reducibility.

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)

We introduce an analogue of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time (...) generalization of the countable Borel equivalence relations, a key subclass of the Borel equivalence relations, and again show that several key properties carry over to the larger class. Lastly, we collect together several results from the literature regarding Borel reducibility which apply also to absolutely $\Delta^1_2$ reductions, and hence to the infinite time computable reductions. (shrink)

We study classes of right-angled Coxeter groups with respect to the strong submodel relation of a parabolic subgroup. We show that the class of all right-angled Coxeter groups is not smooth and establish some general combinatorial criteria for such classes to be abstract elementary classes (AECs), for them to be finitary, and for them to be tame. We further prove two combinatorial conditions ensuring the strong rigidity of a right-angled Coxeter group of arbitrary rank. The combination of these results translates (...) into a machinery to build concrete examples of AECs satisfying given model-theoretic properties. We exhibit the power of our method by constructing three concrete examples of finitary classes. We show that the first and third classes are nonhomogeneous and that the last two are tame, uncountably categorical, and axiomatizable by a single Lω1,ω-sentence. We also observe that the isomorphism relation of any countable complete first-order theory is κ-Borel reducible (in the sense of generalized descriptive set theory) to the isomorphism relation of the theory of right-angled Coxeter groups whose Coxeter graph is an infinite random graph. (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)

Answering one of the main questions of [S.-D. Friedman, T. Hyttinen and V. Kulikov, Generalized descriptive set theory and classification theory, Mem. Amer. Math. Soc. 230 80, Chap. 7], we show that there is a tight connection between the depth of a classifiable shallow theory [Formula: see text] and the Borel rank of the isomorphism relation [Formula: see text] on its models of size [Formula: see text], for [Formula: see text] any cardinal satisfying [Formula: see text]. This is achieved (...) by establishing a link between said rank and the [Formula: see text]-Scott height of the [Formula: see text]-sized models of [Formula: see text], and yields to the following descriptive set-theoretical analog of Shelah’s Main Gap Theorem: Given a countable complete first-order theory [Formula: see text], either [Formula: see text] is Borel with a countable Borel rank, or it is not Borel at all. The dividing line between the two situations is the same as in Shelah’s theorem, namely that of classifiable shallow theories. We also provide a Borel reducibility version of the above theorem, discuss some limitations to the possible complexities of [Formula: see text], and provide a characterization of categoricity of [Formula: see text] in terms of the descriptive set-theoretical complexity of [Formula: see text]. (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)

We study Schauder equivalence relations, which are Borel equivalence relations induced by actions of Banach spaces with Schauder bases. Firstly, we show that and are minimal Schauder equivalence relations. Then, we prove that neither of them is Borel reducible to the quotient where T is the Tsirelson space. This implies that they cannot form a basis for the Schauder equivalence relations. In addition, we apply an argument of Farah to show that every basis for the Schauder equivalence relations, (...) if such exist, has to be of cardinality. (shrink)

In this paper, notions of ‐like and c0‐like equivalence relations are introduced. We characterize the positions of ‐like and c0‐like equivalence relations in the Borel reducibility hierarchy by comparing them with equivalence relations and.

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.

Assuming every real has a sharp, we prove that for any $\mathop \prod \limits_\~ _1^1 $ equivalence relation either Borel reduces E₀ or in a $\mathop \Delta \limits_\~ _3^1 $ manner allows the assignment of bounded subsets of ω₁ as complete invariants.

There are continuum many ≤B-incomparable equivalence relations induced by a free, Borel action of a countable non-abelian free group — and hence, there are 2α0 many treeable countable Borel equivalence relations which are incomparable in the ordering of Borel reducibility.

A well known fact is that every Lebesgue measurable set is regular, i.e., it includes an F$_{\sigma}$ set of the same measure. We analyze this fact from a metamathematical or foundational standpoint. We study a family of Muchnik degrees corresponding to measure-theoretic regularity at all levels of the effective Borel hierarchy. We prove some new results concerning Nies's notion of LR-reducibility. We build some $\omega$-models of RCA$_0$which are relevant for the reverse mathematics of measure-theoretic regularity.

We consider the complexity of the isomorphism relation on countable first-order structures with transitive automorphism groups. We use the theory of Borel reducibility of equivalence relations to show that the isomorphism problem for vertex-transitive graphs is as complicated as the isomorphism problem for arbitrary graphs and determine for which first-order languages the isomorphism problem for transitive countable structures is as complicated as it is for arbitrary countable structures. We then use these results to characterize the complexity of the (...) isometry relation for certain classes of homogeneous and ultrahomogeneous metric spaces. (shrink)

We show that for any countable homogeneous ordered graph G, the conjugacy problem for automorphisms of G is Borel complete. In fact we establish that each such G satisfies a strong extension property called ABAP, which implies that the isomorphism relation on substructures of G is Borel reducible to the conjugacy relation on automorphisms of G.