Monotone Reducibility and the Family of Infinite Sets
Cenzer, Douglas
J. Symbolic Logic, Tome 49 (1984) no. 1, p. 774-782 / Harvested from Project Euclid
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 $\Phi$ from $2^N$ into $2^N$ such that $A = \Phi^{-1} (B); A$ is said to be monotone reducible to $B$ if in addition the map $\Phi$ is monotone, that is, $a \subset b$ implies $\Phi (a) \subset \Phi(b)$. The set $A$ is said to be monotone if $a \in A$ and $a \subset b$ imply $b \in A$. For monotone sets, it is shown that, as for Wadge reducibility, sets low in the arithmetical hierarchy are nicely ordered. The $\triangle^0_1$ sets are all reducible to the ($\Sigma^0_1$ but not $\triangle^0_1$) sets, which are in turn all reducible to the strictly $\triangle^0_2$ sets, which are all in turn reducible to the strictly $\Sigma^0_2$ sets. In addition, the nontrivial $\Sigma^0_n$ sets all have the same degree for $n \leq 2$. For Wadge reducibility, these results extend throughout the Borel hierarchy. In contrast, we give two natural strictly $\Pi^0_2$ monotone sets which have different monotone degrees. We show that every $\Sigma^0_2$ monotone set is actually $\Sigma^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.
Publié le : 1984-09-14
Classification: 
@article{1183741617,
     author = {Cenzer, Douglas},
     title = {Monotone Reducibility and the Family of Infinite Sets},
     journal = {J. Symbolic Logic},
     volume = {49},
     number = {1},
     year = {1984},
     pages = { 774-782},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183741617}
}
Cenzer, Douglas. Monotone Reducibility and the Family of Infinite Sets. J. Symbolic Logic, Tome 49 (1984) no. 1, pp.  774-782. http://gdmltest.u-ga.fr/item/1183741617/