Sets, Models, And Proofs: Topics In The Theory Of Recursive Functions

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.