- Games for functions
- Baire classes, Weihrauch degrees, transfinite computations, and ranks
- Award date
- 24 April 2018
- Number of pages
- Document type
- PhD thesis
- Faculty of Science (FNWI)
Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
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.
- ILLC Dissertation Series DS-2018-09.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.