JavaScript is disabled for your browser. Some features of this site may not work without it.
Decidability in the Hyperdegrees and a Theorem of Hyperarithmetic Analysis

Author
Barnes, James Samuel
Abstract
In this thesis we explore two different topics: the complexity of the theory of the hyperdegrees, and the reverse mathematics of a result in graph theory. For the first, we show the $\Sigma_{2}$ theory of the hyperdegrees as an upper-semilattice is decidable, as is the $\Sigma_{2}$ theory of the hyperdegrees below Kleene's $\mathcal{O}$ as an upper-semilattice with greatest element. These results are related to questions of extensions of embeddings into both structures, i.e., when do embeddings of a structure extend to embeddings of a superstructure. The second part is joint work with Richard Shore and Jun Le Goh. We investigate a theorem of graph theory and find that one formalization is a theorem of hyperarithmetic analysis: the second such example found, as it were, in the wild. This work is ongoing, and more may appear in future publications.
Date Issued
2018-08-30Subject
Computability; Hyperarithmetic; Recursion; Logic
Committee Chair
Shore, Richard A.
Committee Member
Kozen, Dexter Campbell; Nerode, Anil
Degree Discipline
Mathematics
Degree Name
Ph. D., Mathematics
Degree Level
Doctor of Philosophy
Rights
Attribution 4.0 International
Rights URI
Type
dissertation or thesis
Except where otherwise noted, this item's license is described as Attribution 4.0 International