Ultrafiltres absolus et problèmes d'extraction de sous-suites
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...
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...
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.
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.
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...
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...
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].
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].
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.
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).
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.