Games for functions Baire classes, Weihrauch degrees, transfinite computations, and ranks

Open Access
Authors
Supervisors
Cosupervisors
  • A.M. Pauly
Award date 24-04-2018
ISBN
  • 9789402810004
Number of pages 129
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
  • Faculty of Science (FNWI)
Abstract
Game characterizations of classes of functions in descriptive set theory have their origins in the seminal work of Wadge, with further developments by several others. In this thesis we study such characterizations from several perspectives. We define modifications of Semmes's game characterization of the Borel functions, obtaining game characterizations of the Baire class $\alpha$ functions for each fixed $\alpha < \omega_1$. We also define a construction of games which transforms a game characterizing a class $\Lambda$ of functions into a game characterizing the class of functions which are piecewise $\Lambda$ on a countable partition by $\Pi^0_\alpha$ sets, for each $0 < \alpha < \omega_1$. We then define a parametrized Wadge game by using computable analysis, and show how the parameters affect the class of functions that is characterized by the game. As an application, we recast our games characterizing the Baire classes into this framework. Furthermore, we generalize our game characterizations of function classes to generalized Baire spaces, show how the notion of computability on Baire space can be transferred to generalized Baire spaces, and show that this is appropriate for computable analysis by defining a representation of Galeotti's generalized real line and analyzing the Weihrauch degree of the intermediate value theorem for that space. Finally, we show how the game characterizations of function classes discussed lead in a natural way to a stratification of each class into a hierarchy, intuitively measuring the complexity of functions in that class. This idea and the results presented open new paths for further research.
Document type PhD thesis
Note ILLC Dissertation Series DS-2018-09.
Language English
Downloads
Permalink to this page
cover
Back