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 prove a strong boundedness theorem for dilators: if A ⊆ DIL is Σ 1 1 , then there is a recursive dilator D 0 such that ∀ D ∈ A.

The main theorem of this paper is: If ƒ is a partial function from ℵ 1 to ℵ 1 which is ∑ 1 1 -bounded, then there is a weakly finite primitive recursive dilator D such that for all infinite αϵdom , ƒ ⩽ D . The proof involves only elementary combinatorial constructions of trees. A generalization to ptykes is also given.

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.

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)

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

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)

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

Purpose. To examine the existential anthropology of G. Marcel and E. Minkowski, in order to demonstrate the necessity of distinguishing the universal-spiritual, as human in human being, apart from the individual-existential in him, and to reveal the hierarchical correlation of biosocial, existential and spiritual spheres in personality. Theoretical basis. Within existential philosophy the author differentiates two separate traditions and proceeds from the insufficiency of the distinction of existential sphere, proposed by phenomenological tradition, showing the necessity of its correlation with the (...) spiritual sphere as a sphere of humanity, proposed by non-phenomenological tradition of G. Marcel and E. Minkowski. Originality. The author presents the anthropological conception of G. Marcel and E. Minkowski, in which human personality is understood as unity of individual-existential and universal-spiritual, which requires a special trans-empirical field of culture, which contains senses, images and symbols of humanity. Also, the author presents the recent developments of existential thinkers in distinguishing existential and spiritual dimensions, both not reducible to the physical and social dimensions. Conclusions. In both existential traditions, the specifically human was founded as a trans-biological and trans-social phenomenon, which appears as indefinable and non-predetermined. But in first tradition, humanity is understood as an existence, as a unique individuality, "project", variant of humanity, equivalent to other variants, and universal is understood as a community of human condition in the world. While in the second tradition, the universal is understood as spiritual. Thus, horizontal level of our private existence, as the process of movement from birth to death, is supplemented by vertical of human, universal ideals and images. Humanity appears as a task, on the way to which human being transcends beyond the limits of his individual "self" to the "super-individual", through inclusion into spiritual community, into universal culture. (shrink)

Michael Choniates (c. 1138–c. 1222), a pupil of Eustathius of Thessalonica, who was Greek Orthodox Metropolitan of Athens for some 25 years up to that city's capture by Frankish crusaders ina.d.1205, is best known to classical scholars as the possessor of probably the last complete copy of Callimachus'HecaleandAetia. He had brought with him from Constantinople many books of all kinds, and added to his collection when in Athens. Although an immense task, it would be well worth trying to identify all (...) Michael's classical allusions, as an indication of how much ancient Greek literature was still available just before Constantinople too succumbed to the crusaders. (shrink)

Both and are guaranteed by the London scholia , so the gap is reduced to the tantalizingly small one of a monosyllabic feminine noun in the accusative case, most probably of four letters. The number of possibilities cannot be unlimited. My own suggestion must necessarily remain in limbo in the present state of our knowledge concerning the poet or poets whom Callimachus is talking about, but at least it seems to me less bizarre than other restorations currently in the field.