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 Free Access

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

  • [1] D. Cenzer, Monotone reducibility and the family of infinite sets, J. Symbolic Logic 49 (1984), 774-782. MR 758928 (86a:03052)
  • [2] R. Dougherty, Monotone but not positive subsets of the Cantor space, J. Symbolic Logic 52 (1987), 817-818. MR 902994 (88j:03033)
  • [3] -, Sequential discreteness and clopen-I-Boolean classes, J. Symbolic Logic 52 (1987), 232-242. MR 877873 (88c:03048)
  • [4] F. Hausdorff, Set theory, Chelsea, New York, 1957. MR 0086020 (19:111a)
  • [5] H. Keisler, Universal homogeneous Boolean algebras, Michigan Math. J. 13 (1966), 129-132. MR 0195770 (33:3968)
  • [6] K. Kunen, Set theory, North-Holland, Amsterdam, 1980. MR 597342 (82f:03001)
  • [7] R. Laver, Linear orders in $ {(\omega )^\omega }$ under eventual dominance, Logic Colloquium `78 (M. Boffa et al., eds.), North-Holland, Amsterdam, 1979. MR 567675 (81e:03051)
  • [8] -, On Fraïssés order type conjecture, Ann. of Math. 93 (1971), 89-111. MR 0279005 (43:4731)
  • [9] E. Lopez-Escobar, An interpolation theorem for denumerably long formulas, Fund. Math. 57 (1965), 253-274. MR 0188059 (32:5500)
  • [10] A. Louveau and J. Saint Raymond, Borel classes and closed games: Wadge-type and Hurewicztype results, Trans. Amer. Math. Soc. 304 (1987), 431-467. MR 911079 (89g:03068)
  • [11] A. Miller, Some problems in set theory and model theory, Doctoral Dissertation, Univ. of California, Berkeley, 1978.
  • [12] Y. Moschovakis, Descriptive set theory, North-Holland, Amsterdam, 1980. MR 561709 (82e:03002)
  • [13] J. Rosenstein, Linear orderings, Academic Press, New York, 1982. MR 662564 (84m:06001)
  • [14] W. Wadge, Reducibility and determinateness on the Baire space, Doctoral Dissertation, Univ. of California, Berkeley, 1983.

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