Cornell University
Decidability in the Hyperdegrees and a Theorem of Hyperarithmetic Analysis
Abstract
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 \Sigma2 theory of the hyperdegrees as an upper-semilattice is decidable, as is the \Sigma2 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.
Degree
thesis:*- Name thesis:degree_name
- Ph. D., Mathematics
- Level thesis:degree_level
- Doctor of Philosophy
- Discipline thesis:degree_discipline
- Mathematics
- Grantor
- Cornell University
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Barnes, James Samuel
- Chair dc:contributor.chair
-
- Shore, Richard A.
- Committee members dc:contributor.committeemember
-
- Kozen, Dexter Campbell
- Nerode, Anil
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 10489800
- Dc Identifier Other
-
ProQuest Submission ID: 10991
ProQuest Publication ID: 10845201