Monotone reducibility and the family of infinite sets
Journal of Symbolic Logic 49 (3):774-782 (1984)
| Abstract | Let A and B be subsets of the space 2 N of sets of natural numbers. A is said to be Wadge reducible to B if there is a continuous map Φ from 2 N into 2 N such that A = Φ -1 (B); A is said to be monotone reducible to B if in addition the map Φ is monotone, that is, $a \subset b$ implies $\Phi (a) \subset \Phi(b)$ . The set A is said to be monotone if a ∈ A and $a \subset b$ imply b ∈ A. For monotone sets, it is shown that, as for Wadge reducibility, sets low in the arithmetical hierarchy are nicely ordered. The ▵ 0 1 sets are all reducible to the (Σ 0 1 but not ▵ 0 1 ) sets, which are in turn all reducible to the strictly ▵ 0 2 sets, which are all in turn reducible to the strictly Σ 0 2 sets. In addition, the nontrivial Σ 0 n sets all have the same degree for n ≤ 2. For Wadge reducibility, these results extend throughout the Borel hierarchy. In contrast, we give two natural strictly Π 0 2 monotone sets which have different monotone degrees. We show that every Σ 0 2 monotone set is actually Σ 0 2 positive. We also consider reducibility for subsets of the space of compact subsets of 2 N . This leads to the result that the finitely iterated Cantor-Bendixson derivative D n is a Borel map of class exactly 2n, which answers a question of Kuratowski | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,701 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesBoško Živaljević (1991). U-Meager Sets When the Cofinality and the Coinitiality of U Are Uncountable. Journal of Symbolic Logic 56 (3):906-914.
Jan Kraszewski (2001). Properties of Ideals on the Generalized Cantor Spaces. Journal of Symbolic Logic 66 (3):1303-1320.
John P. Burgess (1988). Sets and Point-Sets: Five Grades of Set-Theoretic Involvement in Geometry. PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:456 - 463.
Slawomir Solecki (1994). Covering Analytic Sets by Families of Closed Sets. Journal of Symbolic Logic 59 (3):1022-1031.
Jeanleah Mohrherr (1983). Kleene Index Sets and Functional M-Degrees. Journal of Symbolic Logic 48 (3):829-840.
Ernst Kleinert (2007). On the Reducibility of Relations: Variations on a Theme of Peirce. Transactions of the Charles S. Peirce Society 43 (3):509 - 520.
Kenneth Schilling & Boško Živaljević (1997). Louveau's Theorem for the Descriptive Set Theory of Internal Sets. Journal of Symbolic Logic 62 (2):595-607.
J. Duparc (2001). Wadge Hierarchy and Veblen Hierarchy Part I: Borel Sets of Finite Rank. Journal of Symbolic Logic 66 (1):56-86.
John T. Gill Iii & Paul H. Morris (1974). On Subcreative Sets and S-Reducibility. Journal of Symbolic Logic 39 (4):669 - 677.
William C. Calhoun (2006). Degrees of Monotone Complexity. Journal of Symbolic Logic 71 (4):1327 - 1341.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads2 ( #232,575 of 549,113 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
