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.

We consider Borel equivalence relations E induced by actions of the infinite symmetric group, or equivalently the isomorphism relation on classes of countable models of bounded Scott rank. We relate the descriptive complexity of the equivalence relation to the nature of its complete invariants. A typical theorem is that E is potentially Π03 iff the invariants are countable sets of reals, it is potentially Π04 iff the invariants are countable sets of countable sets of reals, and so on. The proofs (...) use various techniques, including Vaught transforms, changing topologies, and the Scott analysis of countable models. (shrink)

We describe a new way to construct large subdirectly irreducibles within an equational class of algebras. We use this construction to show that there are forbidden geometries of multitraces for finite algebras in residually small equational classes. The construction is first applied to show that minimal equational classes generated by simple algebras of types 2, 3 or 4 are residually small if and only if they are congruence modular. As a second application of the construction we characterize residually small locally (...) finite abelian equational classes. (shrink)

Louveau, A., S. Shelah and B. Velikovi, Borel partitions of infinite subtrees of a perfect tree, Annals of Pure and Applied Logic 63 271–281. We define a notion of type of a perfect tree and show that, for any given type τ, if the set of all subtrees of a given perfect tree T which have type τ is partitioned into two Borel classes then there is a perfect subtree S of T such that all subtrees of S of type (...) τ belong to the same class. This result simultaneously generalizes the partition theorems of Galvin-Prikry and Galvin-Blass. The key ingredient of the proof is the theorem of Halpern-Laüchli on partitions of products of perfect trees. (shrink)

We provide partial answers to the following problem: Is the class of Borel linear orders well-quasi-ordered under embeddability? We show that it is indeed the case for those Borel orders which are embeddable in R ω , with the lexicographic ordering. For Borel orders embeddable in R 2 , our proof works in ZFC, but it uses projective determinacy for Borel orders embeddable in some $\mathbf{R}^n, n , and hyperprojective determinacy for the general case.

We prove two results about the embeddability relation between Borel linear orders: For $\eta$ a countable ordinal, let $2^\eta$ (resp. $2^{<\eta}$) be the set of sequences of zeros and ones of length $\eta$ (resp. $<\eta$), equipped with the lexicographic ordering. Given a Borel linear order $X$ and a countable ordinal $\xi$, we prove the following two facts. (a) Either $X$ can be embedded (in a $\triangle^1_1(X,\xi)$ way) in $2^{\omega\xi}$, or $2^{\omega\xi + 1}$ continuously embeds in $X$. (b) Either $X$ can (...) embedded (in a $\triangle^1_1(X,\xi)$ way) in $2^{\omega\xi}$, or $2^{\omega\xi}$ continuously embeds in $X$. These results extend previous work of Harrington, Shelah and Marker. (shrink)