dc.contributor.author Barnes, James Samuel dc.date.accessioned 2018-10-23T13:35:05Z dc.date.available 2018-10-23T13:35:05Z dc.date.issued 2018-08-30 dc.identifier.other Barnes_cornellgrad_0058F_10991 dc.identifier.other http://dissertations.umi.com/cornellgrad:10991 dc.identifier.other bibid: 10489800 dc.identifier.uri https://hdl.handle.net/1813/59704 dc.description.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. dc.language.iso en_US dc.rights Attribution 4.0 International * dc.rights.uri https://creativecommons.org/licenses/by/4.0/ * dc.subject Computability dc.subject Hyperarithmetic dc.subject Recursion dc.subject Logic dc.title Decidability in the Hyperdegrees and a Theorem of Hyperarithmetic Analysis dc.type dissertation or thesis thesis.degree.discipline Mathematics thesis.degree.grantor Cornell University thesis.degree.level Doctor of Philosophy thesis.degree.name Ph. D., Mathematics dc.contributor.chair Shore, Richard A. dc.contributor.committeeMember Kozen, Dexter Campbell dc.contributor.committeeMember Nerode, Anil dcterms.license https://hdl.handle.net/1813/59810 dc.identifier.doi https://doi.org/10.7298/X4XW4H27
﻿

### This item appears in the following Collection(s)

Except where otherwise noted, this item's license is described as Attribution 4.0 International