JavaScript is disabled for your browser. Some features of this site may not work without it.
Sets, Models, And Proofs: Topics In The Theory Of Recursive Functions

Author
Belanger, David
Abstract
SETS, MODELS, AND PROOFS: TOPICS IN THE THEORY OF RECURSIVE FUNCTIONS David Roger Belanger, Ph.D. Cornell University We prove results in various areas of recursion theory. First, in joint work with Richard Shore, we prove a new jump-inversion result for ideals of recursively enumerable (r.e.) degrees; this defeats what had seemed to be a promising tack on the automorphism problem for the semilattice R of r.e. degrees. Second, in work spanning two chapters, we calibrate the reverse-mathematical strength of a number of theorems of basic model theory, such as the Ryll-Nardzewski atomic-model theorem, Vaught's no-two-model theorem, Ehrenfeucht's three-model theorem, and the existence theorems for homogeneous and saturated models. Whereas most of these are equivalent over RCA0 to one of RCA0 , WKL0 , ACA0 , as usual, we also uncover model-theoretic statements with exotic complexities such as ¬WKL0 ∨ ACA0 and WKL0 ∨ I[SIGMA]0 . 2 Third, we examine the possible weak truth table (wtt) degree spectra of countable first-order structures. We find several points at which the wtt- and Turingdegree cases differ, notably that the most direct wtt analogue of Knight's dichotomy theorem does not hold. Yet we find weaker analogies between the two, including a new trichotomy theorem for wtt degree spectra in the spirit of Knight's.
Date Issued
2015-08-17Subject
recursion theory; computability theory; reverse mathematics
Committee Chair
Shore,Richard A
Committee Member
Constable,Robert Lee; Nerode,Anil; Moore,Justin Tatch
Degree Discipline
Mathematics
Degree Name
Ph. D., Mathematics
Degree Level
Doctor of Philosophy
Type
dissertation or thesis