Ultrafiltres absolus et problèmes d'extraction de sous-suites
Undecidability of topological and arithmetical properties of infinitary rational relations
We prove that for every countable ordinal one cannot decide whether a given infinitary rational relation is in the Borel class (respectively ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a -complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide whether...
Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
We prove that for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class (respectively ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a -complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide...
Undetermined sets of point-open games
We show that a set of reals is undetermined in Galvin's point-open game iff it is uncountable and has property C", which answers a question of Gruenhage.
Une démonstration du théorème de séparation des ensembles analytiques
Universal analytic preorders arising from surjective functions
Examples are presented of Σ₁¹-universal preorders arising by requiring the existence of particular surjective functions. These are: the relation of epimorphism between countable graphs; the relation of being a continuous image (or a continuous image of some specific kind) for continua; the relation of being continuous open image for dendrites.
Universal functions
A function of two variables F(x,y) is universal if for every function G(x,y) there exist functions h(x) and k(y) such that G(x,y) = F(h(x),k(y)) for all x,y. Sierpiński showed that assuming the Continuum Hypothesis there exists a Borel function F(x,y) which is universal. Assuming Martin's Axiom there is a universal function of Baire class 2. A universal function cannot be of Baire class 1. Here we show that it is consistent that for each α with 2 ≤ α < ω₁ there...
Very small sets
Vitali sets and Hamel bases that are Marczewski measurable
We give examples of a Vitali set and a Hamel basis which are Marczewski measurable and perfectly dense. The Vitali set example answers a question posed by Jack Brown. We also show there is a Marczewski null Hamel basis for the reals, although a Vitali set cannot be Marczewski null. The proof of the existence of a Marczewski null Hamel basis for the plane is easier than for the reals and we give it first. We show that there is no easy way to get a Marczewski null Hamel basis for the reals from one...
Wadge degrees of -languages of deterministic Turing machines
We describe Wadge degrees of -languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is where is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
Wadge Degrees of ω-Languages of Deterministic Turing Machines
We describe Wadge degrees of ω-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ξω where ξ = ω1CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
Weak Rudin-Keisler reductions on projective ideals
We consider a slightly modified form of the standard Rudin-Keisler order on ideals and demonstrate the existence of complete (with respect to this order) ideals in various projective classes. Using our methods, we obtain a simple proof of Hjorth’s theorem on the existence of a complete Π¹₁ equivalence relation. This proof enables us (under PD) to generalize Hjorth’s result to the classes of equivalence relations.
Weights of denumerable topological spaces
When a partial Borel order is linearizable
When does the Katětov order imply that one ideal extends the other?
We consider the Katětov order between ideals of subsets of natural numbers ("") and its stronger variant-containing an isomorphic ideal ("⊑ "). In particular, we are interested in ideals for which for every ideal . We find examples of ideals with this property and show how this property can be used to reformulate some problems known from the literature in terms of the Katětov order instead of the order "⊑ " (and vice versa).
When is an equivalance relation classifiable.
Wildness in the product groups
Non-abelian Polish groups arising as countable products of countable groups can be tame in arbitrarily complicated ways. This contrasts with some results of Solecki who revealed a very different picture in the abelian case.
Zerlegungsähnlichkeit von Punktmengen.
Αll -dense sets of reals can be isomorphic
Аксиома сравнимого выбора и униформизуемость проективных классов.