Monotone reducibility and the family of infinite sets

Journal of Symbolic Logic 49 (3):774-782 (1984)
  Copy   BIBTEX

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 89,330

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On Subcreative Sets and S-Reducibility.John T. Gill Iii & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669 - 677.
On the reducibility of relations: Variations on a theme of Peirce.Ernst Kleinert - 2007 - Transactions of the Charles S. Peirce Society 43 (3):509 - 520.
Kleene index sets and functional m-degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
Covering analytic sets by families of closed sets.Sławomir Solecki - 1994 - Journal of Symbolic Logic 59 (3):1022-1031.
Sets and Point-Sets: Five Grades of Set-Theoretic Involvement in Geometry.John P. Burgess - 1988 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:456 - 463.
Properties of ideals on the generalized Cantor spaces.Jan Kraszewski - 2001 - Journal of Symbolic Logic 66 (3):1303-1320.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.

Analytics

Added to PP
2009-01-28

Downloads
49 (#282,996)

6 months
5 (#237,114)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

On Borel ideals.Fons van Engelen - 1994 - Annals of Pure and Applied Logic 70 (2):177-203.
Borel ideals vs. Borel sets of countable relations and trees.Samy Zafrany - 1989 - Annals of Pure and Applied Logic 43 (2):161-195.

Add more citations

References found in this work

No references found.

Add more references