Displaying 341 – 360 of 370

Showing per page

Undecidability of topological and arithmetical properties of infinitary rational relations

Olivier Finkel (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We prove that for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class Σ α 0 (respectively Π α 0 ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a Σ 1 1 -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

Olivier Finkel (2010)

RAIRO - Theoretical Informatics and Applications

We prove that for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class Σ α 0 (respectively Π α 0 ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a Σ 1 1 -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

Janusz Pawlikowski (1994)

Fundamenta Mathematicae

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.

Universal analytic preorders arising from surjective functions

Riccardo Camerlo (2005)

Fundamenta Mathematicae

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

Paul B. Larson, Arnold W. Miller, Juris Steprāns, William A. R. Weiss (2014)

Fundamenta Mathematicae

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

Haim Judah, Amiran Lior, Ireneusz Recław (1997)

Colloquium Mathematicae

Vitali sets and Hamel bases that are Marczewski measurable

Arnold Miller, Strashimir Popvassilev (2000)

Fundamenta Mathematicae

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

Victor Selivanov (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 ξ = ω 1 CK 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

Victor Selivanov (2010)

RAIRO - Theoretical Informatics and Applications

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

Konstantinos A. Beros (2016)

Fundamenta Mathematicae

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 Π ¹ 2 n + 1 equivalence relations.

When does the Katětov order imply that one ideal extends the other?

Paweł Barbarski, Rafał Filipów, Nikodem Mrożek, Piotr Szuca (2013)

Colloquium Mathematicae

We consider the Katětov order between ideals of subsets of natural numbers (" K ") and its stronger variant-containing an isomorphic ideal ("⊑ "). In particular, we are interested in ideals for which K 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).

Wildness in the product groups

G. Hjorth (2000)

Fundamenta Mathematicae

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.

Currently displaying 341 – 360 of 370