University of Notre Dame
Browse
- No file added yet -

Some Results in Computability Theory

Download (559.25 kB)
thesis
posted on 2019-07-05, 00:00 authored by Rose Weisshaar

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.

History

Date Modified

2019-08-30

Defense Date

2019-06-27

CIP Code

  • 27.0101

Research Director(s)

Julia D. Knight

Degree

  • Doctor of Philosophy

Degree Level

  • Doctoral Dissertation

Alternate Identifier

1112065013

Library Record

5187112

OCLC Number

1112065013

Program Name

  • Mathematics

Usage metrics

    Dissertations

    Categories

    No categories selected

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC