Monotone reducibility over the Cantor space
HTML articles powered by AMS MathViewer
- by Randall Dougherty PDF
- Trans. Amer. Math. Soc. 310 (1988), 433-484 Request permission
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
- Douglas Cenzer, Monotone reducibility and the family of infinite sets, J. Symbolic Logic 49 (1984), no. 3, 774–782. MR 758928, DOI 10.2307/2274130
- Randall Dougherty, Monotone but not positive subsets of the Cantor space, J. Symbolic Logic 52 (1987), no. 3, 817–818. MR 902994, DOI 10.2307/2274367
- Randall Dougherty, Sequential discreteness and clopen-$I$-Boolean classes, J. Symbolic Logic 52 (1987), no. 1, 232–242. MR 877873, DOI 10.2307/2273880
- Felix Hausdorff, Set theory, Chelsea Publishing Co., New York, 1957. Translated by John R. Aumann, et al. MR 0086020
- H. Jerome Keisler, Universal homogeneous Boolean algebras, Michigan Math. J. 13 (1966), 129–132. MR 195770
- Kenneth Kunen, Set theory, Studies in Logic and the Foundations of Mathematics, vol. 102, North-Holland Publishing Co., Amsterdam-New York, 1980. An introduction to independence proofs. MR 597342
- Richard Laver, Linear orders in $(\omega )^{\omega }$ under eventual dominance, Logic Colloquium ’78 (Mons, 1978) Studies in Logic and the Foundations of Mathematics, vol. 97, North-Holland, Amsterdam-New York, 1979, pp. 299–302. MR 567675
- Richard Laver, On Fraïssé’s order type conjecture, Ann. of Math. (2) 93 (1971), 89–111. MR 279005, DOI 10.2307/1970754
- E. G. K. Lopez-Escobar, An interpolation theorem for denumerably long formulas, Fund. Math. 57 (1965), 253–272. MR 188059, DOI 10.4064/fm-57-3-253-272
- A. Louveau and J. Saint-Raymond, Borel classes and closed games: Wadge-type and Hurewicz-type results, Trans. Amer. Math. Soc. 304 (1987), no. 2, 431–467. MR 911079, DOI 10.1090/S0002-9947-1987-0911079-0 A. Miller, Some problems in set theory and model theory, Doctoral Dissertation, Univ. of California, Berkeley, 1978.
- Yiannis N. Moschovakis, Descriptive set theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR 561709
- Joseph G. Rosenstein, Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662564 W. Wadge, Reducibility and determinateness on the Baire space, Doctoral Dissertation, Univ. of California, Berkeley, 1983.
Additional Information
- © Copyright 1988 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 310 (1988), 433-484
- MSC: Primary 03E15; Secondary 54F05
- DOI: https://doi.org/10.1090/S0002-9947-1988-0943302-1
- MathSciNet review: 943302