Back to search

Cornell University

Decidability in the Hyperdegrees and a Theorem of Hyperarithmetic Analysis

Abstract

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 \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 × 4

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
10489800
Dc Identifier Other
ProQuest Submission ID: 10991
ProQuest Publication ID: 10845201

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Barnes, James Samuel. Decidability in the Hyperdegrees and a Theorem of Hyperarithmetic Analysis. Doctor of Philosophy thesis, Cornell University, 2018. https://hdl.handle.net/1813/59704