Show simple item record

dc.contributor.authorBarnes, James Samuel
dc.date.accessioned2018-10-23T13:35:05Z
dc.date.available2018-10-23T13:35:05Z
dc.date.issued2018-08-30
dc.identifier.otherBarnes_cornellgrad_0058F_10991
dc.identifier.otherhttp://dissertations.umi.com/cornellgrad:10991
dc.identifier.otherbibid: 10489800
dc.identifier.urihttps://hdl.handle.net/1813/59704
dc.description.abstractIn 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.isoen_US
dc.rightsAttribution 4.0 International*
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/*
dc.subjectComputability
dc.subjectHyperarithmetic
dc.subjectRecursion
dc.subjectLogic
dc.titleDecidability in the Hyperdegrees and a Theorem of Hyperarithmetic Analysis
dc.typedissertation or thesis
thesis.degree.disciplineMathematics
thesis.degree.grantorCornell University
thesis.degree.levelDoctor of Philosophy
thesis.degree.namePh. D., Mathematics
dc.contributor.chairShore, Richard A.
dc.contributor.committeeMemberKozen, Dexter Campbell
dc.contributor.committeeMemberNerode, Anil
dcterms.licensehttps://hdl.handle.net/1813/59810
dc.identifier.doihttps://doi.org/10.7298/X4XW4H27


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

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

Statistics