Using the theory of Borel equivalence relations we analyze the isomorphism relation on the countable models of a theory and develop a framework for measuring the complexity of possible complete invariants for isomorphism.

We prove the following Main Theorem: $ZF + AD + V = L(R) \Rightarrow DC$ . As a corollary we have that $\operatorname{Con}(ZF + AD) \Rightarrow \operatorname{Con}(ZF + AD + DC)$ . Combined with the result of Woodin that $\operatorname{Con}(ZF + AD) \Rightarrow \operatorname{Con}(ZF + AD + \neg AC^\omega)$ it follows that DC (as well as AC ω ) is independent relative to ZF + AD. It is finally shown (jointly with H. Woodin) that ZF + AD + ¬ DC (...) R , where DC R is DC restricted to reals, implies the consistency of ZF + AD + DC, in fact implies R # (i.e. the sharp of L(R)) exists. (shrink)

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)

§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)

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)

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.

§ 1. Introduction. In this communication we present some recent results on the classification of Polish metric spaces up to isometry and on the isometry groups of Polish metric spaces. A Polish metric space is a complete separable metric space.Our first goal is to determine the exact complexity of the classification problem of general Polish metric spaces up to isometry. This work was motivated by a paper of Vershik [1998], where he remarks : “The classification of Polish spaces up to (...) isometry is an enormous task. More precisely, this classification is not ‘smooth’ in the modern terminology.” Our Theorem 2.1 below quantifies precisely the enormity of this task.After doing this, we turn to special classes of Polish metric spaces and investigate the classification problems associated with them. Note that these classification problems are in principle no more complicated than the general one above. However, the determination of their exact complexity is not necessarily easier.The investigation of the classification problems naturally leads to some interesting results on the groups of isometries of Polish metric spaces. We shall also present these results below.The rest of this section is devoted to an introduction of some basic ideas of a theory of complexity for classification problems, which will help to put our results in perspective. Detailed expositions of this general theory can be found, e.g., in Hjorth [2000], Kechris [1999], [2001]. (shrink)

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)

Let Γ be a collection of relations on the reals and let M be a set of reals. We call M a perfect set basis for Γ if every set in Γ with parameters from M which is not totally included in M contains a perfect subset with code in M. A simple elementary proof is given of the following result (assuming mild regularity conditions on Γ and M): If M is a perfect set basis for Γ, the field of (...) every wellordering in Γ is contained in M. An immediate corollary is Mansfield's Theorem that the existence of a Σ 1 2 wellordering of the reals implies that every real is constructible. Other applications and extensions of the main result are also given. (shrink)

LetXbe a standard Borel space, and letEbe acountableBorel equivalence relation onX, i.e., a Borel equivalence relationEfor which every equivalence class [x]Eis countable. By a result of Feldman-Moore [FM],Eis induced by the orbits of a Borel action of a countable groupGonX.The structure of general countable Borel equivalence relations is very little understood. However, a lot is known for the particularly important subclass consisting of hyperfinite relations. A countable Borel equivalence relation is calledhyperfiniteif it is induced by a Borel ℤ-action, i.e., by (...) the orbits of a single Borel automorphism. Such relations are studied and classified in [DJK]. It is shown in Ornstein-Weiss [OW] and Connes-Feldman-Weiss [CFW] that for every Borel equivalence relationEinduced by a Borel action of a countable amenable groupGonXand for every probability measure μ onX, there is a Borel invariant setY⊆Xwith μ = 1 such thatE↾Y is hyperfinite. Motivated by this result, Weiss [W2] raised the question of whether everyEinduced by a Borel action of a countable amenable group is hyperfinite. Later on Weiss showed that this is true forG= ℤn. However, the problem is still open even for abelianG. Our main purpose here is to provide a weaker affirmative answer for general amenableG. We need a definition first. Given two standard Borel spacesX, Y, auniversally measurableisomorphism betweenXandYis a bijection ƒ:X→Ysuch that both ƒ, ƒ-1are universally measurable. Notice now that to assert that a countable Borel equivalence relation onXis hyperfinite is trivially equivalent to saying that there is a standard Borel spaceYand a hyperfinite Borel equivalence relationFonY, which isBorelisomorphic toE, i.e., there is a Borel bijection ƒ:X→YwithxEy⇔ ƒFƒ. We have the following theorem. (shrink)