ABSTRACT
In this part of the book we give an introduction to the theory of definable equivalence relations in the Borel reducibility hierarchy.
The notion of Borel reducibility is the most penetrating concept studied in the invariant descriptive set theory. It was originally borrowed from computability theory and structural complexity theory to help determine the relative complexity of equivalence relations. In this sense invariant descriptive set theory can be regarded as a complexity theory for equivalence relations. There are, however, two prominent features that are unique to invariant descriptive set theory. The first one is that almost no equivalence relations studied here are artificial. In fact almost all of them arose from other fields of mathematics and some of them have even been studied in those fields intensively before their study became the main focus of invariant descriptive set theory. Thus results in invariant descriptive set theory are relevant to a broad range of mathematical fields. The second feature, which might be more interesting, is that we are comparing objects or problems of different mathematical nature in the same framework, thus making new connections between mathematical fields. For instance, it is very common that a classification problem in algebra turns out to have the same complexity as a problem in topology or analysis.
5.1 Borel reductions Definition 5.1.1 Let E be an equivalence relation on set X and F an equivalence relation on set Y . A function f : X → Y is called a reduction from E to F if
