{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/154"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/154","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"The role of true finiteness in the admissible recursively enumerable degrees","abstract":"When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of alpha-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal alpha is effectively close to omega (where this closeness can be measured by size or by cofinality) then such constructions may be performed in the alpha-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of alpha-r.e. degrees for various classes of admissible ordinals alpha. Together with coding work which shows that for some alpha, the theory of the alpha-r.e. degrees is complicated, we get that for every admissible ordinal alpha, the alpha-r.e. degrees and the classical r.e. degrees are not elementarily equivalent.","abstract_html":"When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of alpha-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal alpha is effectively close to omega (where this closeness can be measured by size or by cofinality) then such constructions may be performed in the alpha-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of alpha-r.e. degrees for various classes of admissible ordinals alpha. Together with coding work which shows that for some alpha, the theory of the alpha-r.e. degrees is complicated, we get that for every admissible ordinal alpha, the alpha-r.e. degrees and the classical r.e. degrees are not elementarily equivalent.","abstract_has_math":false,"creators":["Greenberg, Noam"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2004,"date_issued":"2004-07-16T18:39:00Z","date_published":"2004-07-16T18:39:00Z","updated_at":"2026-11-19T03:14:35Z","subjects":["Admissible Recursion Theory","Recursively Enumerable Degrees","Finite"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475944"],"render_values":[{"text":"6475944","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/154","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/154","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%2F154","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Greenberg, Noam"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2004-07-16T18:39:00Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2004-07-16T18:39:00Z"]},{"key":"dc:date.issued","label":"Date","values":["2004-07-16T18:39:00Z"]},{"key":"dc:relation.isformatof","label":"Dc Relation Isformatof","values":["bibid: 6475944"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Admissible Recursion Theory","Recursively Enumerable Degrees","Finite"]}]},{"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":["6475944"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/154"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"aa0cc2a3-e027-4179-9e7d-2c19187b6a85\"> <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>The role of true finiteness in the admissible recursively enumerable degrees</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2004-07-16T18:39:00Z</PublicationDate> <Authors> <Author> <DisplayName>Greenberg, Noam</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Admissible Recursion Theory</Keyword> <Keyword>Recursively Enumerable Degrees</Keyword> <Keyword>Finite</Keyword> <Abstract>When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of alpha-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal alpha is effectively close to omega (where this closeness can be measured by size or by cofinality) then such constructions may be performed in the alpha-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of alpha-r.e. degrees for various classes of admissible ordinals alpha. Together with coding work which shows that for some alpha, the theory of the alpha-r.e. degrees is complicated, we get that for every admissible ordinal alpha, the alpha-r.e. degrees and the classical r.e. degrees are not elementarily equivalent.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Greenberg, Noam"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of alpha-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal alpha is effectively close to omega (where this closeness can be measured by size or by cofinality) then such constructions may be performed in the alpha-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of alpha-r.e. degrees for various classes of admissible ordinals alpha. Together with coding work which shows that for some alpha, the theory of the alpha-r.e. degrees is complicated, we get that for every admissible ordinal alpha, the alpha-r.e. degrees and the classical r.e. degrees are not elementarily equivalent."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["710115 bytes"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["The role of true finiteness in the admissible recursively enumerable degrees"]},{"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=\"aa0cc2a3-e027-4179-9e7d-2c19187b6a85\"> <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>The role of true finiteness in the admissible recursively enumerable degrees</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2004-07-16T18:39:00Z</PublicationDate> <Authors> <Author> <DisplayName>Greenberg, Noam</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Admissible Recursion Theory</Keyword> <Keyword>Recursively Enumerable Degrees</Keyword> <Keyword>Finite</Keyword> <Abstract>When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of alpha-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal alpha is effectively close to omega (where this closeness can be measured by size or by cofinality) then such constructions may be performed in the alpha-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of alpha-r.e. degrees for various classes of admissible ordinals alpha. Together with coding work which shows that for some alpha, the theory of the alpha-r.e. degrees is complicated, we get that for every admissible ordinal alpha, the alpha-r.e. degrees and the classical r.e. degrees are not elementarily equivalent.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Greenberg, Noam"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:creator":["Greenberg, Noam"],"dc:date.accessioned":["2004-07-16T18:39:00Z"],"dc:date.available":["2004-07-16T18:39:00Z"],"dc:date.issued":["2004-07-16T18:39:00Z"],"dc:description.abstract":["When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of alpha-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal alpha is effectively close to omega (where this closeness can be measured by size or by cofinality) then such constructions may be performed in the alpha-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of alpha-r.e. degrees for various classes of admissible ordinals alpha. Together with coding work which shows that for some alpha, the theory of the alpha-r.e. degrees is complicated, we get that for every admissible ordinal alpha, the alpha-r.e. degrees and the classical r.e. degrees are not elementarily equivalent."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.extent":["710115 bytes"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["6475944"],"dc:identifier.uri":["https://hdl.handle.net/1813/154"],"dc:language.iso":["en_US"],"dc:relation.isformatof":["bibid: 6475944"],"dc:subject":["Admissible Recursion Theory","Recursively Enumerable Degrees","Finite"],"dc:title":["The role of true finiteness in the admissible recursively enumerable degrees"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"]},"updated_at":"2026-11-19T03:14:35Z"}