Some Results in Computability Theory

Doctoral Dissertation

Abstract

We consider the question of universality among computable ω-branching trees. To this end, we construct a computable ω-branching tree TKP whose paths compute the complete diagrams of the countable ω-models of Kripke-Platek set theory (KP). We show that, given a path f through TKP , representing a model M of KP, and another computable ill-founded ω-branching tree T, if f fails to compute a path through
T, then M assigns to T a nonstandard ordinal tree rank. Further, we indicate some circumstances in which, given computable ω-branching trees T0 and T1, a path through TKP helps the paths through T0 compute paths through T1.

In a different line of work, we consider effective forcing notions. In particular, we define a class of effective forcing notions that are similar to versions of Mathias forcing and Cohen forcing defined in the literature, and prove some results about how these notions relate. As a consequence, we see that the generics for an effective version of Mathias forcing compute generics for an effective version of Hechler forcing, and vice-versa. Later, we focus on a notion of Mathias forcing over a countable Turing ideal, defined by Cholak, Dzhafarov, and Soskova. We show that there are nested Turing ideals for which the Mathias generics for the larger ideal do not all compute Mathias generics for the smaller ideal.

Attributes

Attribute NameValues
Author Rose Weisshaar
Contributor Julia D. Knight, Research Director
Degree Level Doctoral Dissertation
Degree Discipline Mathematics
Degree Name Doctor of Philosophy
Banner Code
  • PHD-MATH

Defense Date
  • 2019-06-27

Submission Date 2019-07-05
Record Visibility and Access Public
Content License
Departments and Units
Catalog Record

Files

Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.