David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 49 (3):774-782 (1984)
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||categorize this paper)|
|Through your library||Configure|
References found in this work BETA
No references found.
Citations of this work BETA
Samy Zafrany (1980). Borel Ideals Vs. Borel Sets of Countable Relations and Trees. Annals of Pure and Applied Logic 43 (2):161-195.
Similar books and articles
Boš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.
Added to index2009-01-28
Total downloads2 ( #258,312 of 1,089,155 )
Recent downloads (6 months)0
How can I increase my downloads?