In recent years, much work in descriptive set theory has been focused on the Borel complexity of naturally occurring classification problems, in particular, the study of countable Borel equivalence relations and their structure under the quasi-order of Borel reducibility. Following the approach of Louveau and Rosendal in [25] for the study of analytic equivalence relations, we study countable Borel quasi-orders.;We are largely concerned in this thesis with universal countable Borel quasi-orders, i.e. countable Borel quasi-orders above all other countable Borel quasi-orders with regard to Borel reducibility. We first establish that there is a universal countable Borel quasi-order, using a Feldman-Moore-type result for countable Borel quasi-orders and an argument similar to that of Dougherty, Jackson, and Kechris in [5]. We then establish that several countable Borel quasi-orders are universal. An important example is an embeddability relation on descriptive set theoretic trees. This is used in many of the other proofs of universality.;Our main result is Theorem 5.5.2, which states that embeddability of finitely generated groups is a universal countable Borel quasi-order, answering a question of Louveau and Rosendal in [25]. This immediately implies that biembeddability of finitely generated groups is a universal countable Borel equivalence relation. Although it may have been possible to prove this only using results on countable Borel equivalence relations, the use of quasi-orders seems to be the most direct route to this result. The proof uses small cancellation theory. The same techniques are also used to show that embeddability of countable groups is a universal analytic quasi-order.;Finally, we discuss the structure of countable Borel quasi-orders under Borel reducibility, and we present some open problems.
展开▼
