Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Monotone reducibility over the Cantor space

Author: Randall Dougherty
Journal: Trans. Amer. Math. Soc. 310 (1988), 433-484
MSC: Primary 03E15; Secondary 54F05
MathSciNet review: 943302
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Define the partial ordering $ \leqslant $ on the Cantor space $ {}^\omega 2$ by $ x \leqslant y$ iff $ \forall n\,x(n) \leqslant y(n)$ (this corresponds to the subset relation on the power set of $ \omega $). A set $ A \subseteq {}^\omega 2$ is monotone reducible to a set $ B \subseteq {}^\omega 2$ iff there is a monotone (i.e., $ x \leqslant y \Rightarrow f(x) \leqslant f(y)$) continuous function $ f:{}^\omega 2 \to {}^\omega 2$ such that $ x \in A$ iff $ f(x) \in B$. In this paper, we study the relation of monotone reducibility, with emphasis on two topics: (1) the similarities and differences between monotone reducibility on monotone sets (i.e., sets closed upward under $ \leqslant $) and Wadge reducibility on arbitrary sets; and (2) the distinction (or lack thereof) between `monotone' and `positive,' where `positive' means roughly `a priori monotone' but is only defined in certain specific cases. (For example, a $ \Sigma _2^0$-positive set is a countable union of countable intersections of monotone clopen sets.) Among the main results are the following: Each of the six lowest Wadge degrees contains one or two monotone degrees (of monotone sets), while each of the remaining Wadge degrees contains uncountably many monotone degrees (including uncountable antichains and descending chains); and, although `monotone' and `positive' coincide in a number of cases, there are classes of monotone sets which do not match any notion of `positive.'

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03E15, 54F05

Retrieve articles in all journals with MSC: 03E15, 54F05

Additional Information

Keywords: Cantor space, monotone sets, positive sets, Wadge reducibility, difference hierarchy, Borel hierarchy
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society