Bad Wadge-like reducibilities on the Baire space

Luca Motto Ros¹

¹ Mathematisches Institut – Abteilung für Mathematische Logik Albert-Ludwigs-Universität Freiburg Eckerstraße 1 D-79104 Freiburg im Breisgau, Germany

Fundamenta Mathematicae, Tome 224 (2014) no. 1, pp. 67-95.

Résumé

We consider various collections of functions from the Baire space $ {}^{\omega } \omega $ into itself naturally arising in (effective) descriptive set theory and general topology, including computable (equivalently, recursive) functions, contraction mappings, and functions which are nonexpansive or Lipschitz with respect to suitable complete ultrametrics on $ {}^{\omega } \omega $ (compatible with its standard topology). We analyze the degree-structures induced by such sets of functions when used as reducibility notions between subsets of $ {}^{\omega } \omega $, and we show that the resulting hierarchies of degrees are much more complicated than the classical Wadge hierarchy; in particular, they always contain large infinite antichains, and in most cases also infinite descending chains.

Détail

DOI : 10.4064/fm224-1-4

Keywords: consider various collections functions baire space omega omega itself naturally arising effective descriptive set theory general topology including computable equivalently recursive functions contraction mappings functions which nonexpansive lipschitz respect suitable complete ultrametrics omega omega compatible its standard topology analyze degree structures induced sets functions reducibility notions between subsets omega omega resulting hierarchies degrees much complicated classical wadge hierarchy particular always contain large infinite antichains cases infinite descending chains