{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/40909"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/40909","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"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.","abstract_html":"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&#x27;s no-two-model theorem, Ehrenfeucht&#x27;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&#x27;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&#x27;s.","abstract_has_math":false,"creators":["Belanger, David"],"institution":"Cornell University","degree_name":"Ph. D., Mathematics","degree_level":"Doctor of Philosophy","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":["Shore,Richard A"],"committee_members":["Constable,Robert Lee","Nerode,Anil","Moore,Justin Tatch"],"year":2015,"date_issued":"2015-08-17","date_published":"2015-08-17","updated_at":"2026-11-19T03:18:46Z","subjects":["recursion theory","computability theory","reverse mathematics"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["9255173"],"render_values":[{"text":"9255173","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/40909","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/40909","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F40909","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.chair","label":"Chair","values":["Shore,Richard A"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Constable,Robert Lee","Nerode,Anil","Moore,Justin Tatch"]},{"key":"dc:creator","label":"Author","values":["Belanger, David"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2015-10-15T18:01:09Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2015-10-15T18:01:09Z"]},{"key":"dc:date.issued","label":"Date","values":["2015-08-17"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Mathematics"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["recursion theory","computability theory","reverse mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["9255173"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/40909"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"9f605bf5-562a-4724-8cdf-3416bcc28ec7\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Sets, Models, And Proofs: Topics In The Theory Of Recursive Functions</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2015-08-17</PublicationDate> <Authors> <Author> <DisplayName>Belanger, David</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>recursion theory</Keyword> <Keyword>computability theory</Keyword> <Keyword>reverse mathematics</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Belanger, David"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Sets, Models, And Proofs: Topics In The Theory Of Recursive Functions"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"9f605bf5-562a-4724-8cdf-3416bcc28ec7\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Sets, Models, And Proofs: Topics In The Theory Of Recursive Functions</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2015-08-17</PublicationDate> <Authors> <Author> <DisplayName>Belanger, David</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>recursion theory</Keyword> <Keyword>computability theory</Keyword> <Keyword>reverse mathematics</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Belanger, David"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:contributor.chair":["Shore,Richard A"],"dc:contributor.committeemember":["Constable,Robert Lee","Nerode,Anil","Moore,Justin Tatch"],"dc:creator":["Belanger, David"],"dc:date.accessioned":["2015-10-15T18:01:09Z"],"dc:date.available":["2015-10-15T18:01:09Z"],"dc:date.issued":["2015-08-17"],"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."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["9255173"],"dc:identifier.uri":["https://hdl.handle.net/1813/40909"],"dc:language.iso":["en_US"],"dc:subject":["recursion theory","computability theory","reverse mathematics"],"dc:title":["Sets, Models, And Proofs: Topics In The Theory Of Recursive Functions"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Mathematics"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-11-19T03:18:46Z"}