Back to search

Cornell University

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

Abstract

dc:description.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.

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
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Belanger, David
Chair dc:contributor.chair
  • Shore,Richard A
Committee members dc:contributor.committeemember
  • Constable,Robert Lee
  • Nerode,Anil
  • Moore,Justin Tatch

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
9255173

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

Belanger, David. Sets, Models, And Proofs: Topics In The Theory Of Recursive Functions. Doctor of Philosophy thesis, Cornell University, 2015. https://hdl.handle.net/1813/40909