{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/68183"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/68183","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A Hierarchy of Families of Recursively Enumerable Degrees and A Theorem on Bounding Minimal Pairs","abstract":"This thesis is concerned with the properties of recursivelyenumerable sets--that is, sets which can be listed by Turingmachines--and their Turing degrees. We shall use the abbreviationr.e. to stand for the phrase recursively enumerable.","abstract_html":"This thesis is concerned with the properties of recursivelyenumerable sets--that is, sets which can be listed by Turingmachines--and their Turing degrees. We shall use the abbreviationr.e. to stand for the phrase recursively enumerable.","abstract_has_math":false,"creators":["Welch, Lawrence Vaughn"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-14T13:09:50Z","date_published":"2014-12-14T13:09:50Z","updated_at":"2026-07-22T22:25:58Z","subjects":["Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8127730"],"render_values":[{"text":"(UMI)AAI8127730","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/68183","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Welch, Lawrence Vaughn"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-14T13:09:50Z","1981"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/68183","(UMI)AAI8127730"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis is concerned with the properties of recursivelyenumerable sets--that is, sets which can be listed by Turingmachines--and their Turing degrees. We shall use the abbreviationr.e. to stand for the phrase recursively enumerable.","The thesis begins with the proof of an unpublished theorem of Arslanov which says that if f is a total function recursive in 0'' then there is a recursive function g such that for all e 3, it is established that (ELEM) (PI)(,n) if and only if ind( ) (ELEM) (SIGMA)(,n+1), but for n (LESSTHEQ) 3, no such definitive relationship is found.","Further investigations into the nature of index sets lead to a result rather like Rice's Theorem which says that ind( ) is (SIGMA)(,3)-complete if and only if ind( ) is (SIGMA)(,3) and (NOT=) (SLASHCIRC) and ('c) (NOT=) (SLASHCIRC), where ('c) is the complement of in the r.e. degrees.","The fourth chapter gives some short results on the join of two r.e. degrees, based upon the following simple corollary to Sacks' Splitting Theorem: There is a pair {a,b} of low r.e. degrees, the union of whose lower cones forms a basis for the upper semilattice of r.e. degrees. Furthermore, the degree a cups nontrivially to every r.e. degree above itself.","The final chapters are devoted to the proof of a theorem on bounding minimal pairs. Let W(,e) be a r.e. set, and suppose W(,e)(' )(TBOND)(' )(,T)K, where K is a complete r.e. set. Then we can find, effectively in e, a minimal pair of r.e. sets A(,0) and A(,1), neither of which is recursive in W(,e). The proof of this theorem is based on Sacks' proof of his density theorem and Lachlan's and Yates' proofs of the existence of a minimal pair.","Two corollaries of the theorem are then proved. The first states that if 0 < W(,e) < 0' then there is a minimal pair of r.e. sets A(,0) and A(,1) both of which are incomparable to W(,e). The second corollary states that if is any (PI)(,0) family of r.e. degrees such that 0' (NOT ELEM) , then there is a minimal pair of r.e. sets A(,0) and A(,1), neither of which is recursive in any member of .","Made available in DSpace on 2014-12-14T13:09:50Z (GMT). No. of bitstreams: 1 8127730.pdf: 5594297 bytes, checksum: a2df0156eb671037b287a639a34172f8 (MD5) Previous issue date: 1981","Embargo set by: Seth Robbins for item 68361 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Open Restriction set for Item 68361 on 2018-07-18T14:51:57Z with date null by astein@illinois.edu.","Open","147 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981."]},{"key":"dc:title","label":"Title","values":["A Hierarchy of Families of Recursively Enumerable Degrees and A Theorem on Bounding Minimal Pairs"]}]}],"canonical_facts":{"dc:creator":["Welch, Lawrence Vaughn"],"dc:date":["2014-12-14T13:09:50Z","1981"],"dc:description":["This thesis is concerned with the properties of recursivelyenumerable sets--that is, sets which can be listed by Turingmachines--and their Turing degrees. We shall use the abbreviationr.e. to stand for the phrase recursively enumerable.","The thesis begins with the proof of an unpublished theorem of Arslanov which says that if f is a total function recursive in 0'' then there is a recursive function g such that for all e 3, it is established that (ELEM) (PI)(,n) if and only if ind( ) (ELEM) (SIGMA)(,n+1), but for n (LESSTHEQ) 3, no such definitive relationship is found.","Further investigations into the nature of index sets lead to a result rather like Rice's Theorem which says that ind( ) is (SIGMA)(,3)-complete if and only if ind( ) is (SIGMA)(,3) and (NOT=) (SLASHCIRC) and ('c) (NOT=) (SLASHCIRC), where ('c) is the complement of in the r.e. degrees.","The fourth chapter gives some short results on the join of two r.e. degrees, based upon the following simple corollary to Sacks' Splitting Theorem: There is a pair {a,b} of low r.e. degrees, the union of whose lower cones forms a basis for the upper semilattice of r.e. degrees. Furthermore, the degree a cups nontrivially to every r.e. degree above itself.","The final chapters are devoted to the proof of a theorem on bounding minimal pairs. Let W(,e) be a r.e. set, and suppose W(,e)(' )(TBOND)(' )(,T)K, where K is a complete r.e. set. Then we can find, effectively in e, a minimal pair of r.e. sets A(,0) and A(,1), neither of which is recursive in W(,e). The proof of this theorem is based on Sacks' proof of his density theorem and Lachlan's and Yates' proofs of the existence of a minimal pair.","Two corollaries of the theorem are then proved. The first states that if 0 < W(,e) < 0' then there is a minimal pair of r.e. sets A(,0) and A(,1) both of which are incomparable to W(,e). The second corollary states that if is any (PI)(,0) family of r.e. degrees such that 0' (NOT ELEM) , then there is a minimal pair of r.e. sets A(,0) and A(,1), neither of which is recursive in any member of .","Made available in DSpace on 2014-12-14T13:09:50Z (GMT). No. of bitstreams: 1 8127730.pdf: 5594297 bytes, checksum: a2df0156eb671037b287a639a34172f8 (MD5) Previous issue date: 1981","Embargo set by: Seth Robbins for item 68361 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Open Restriction set for Item 68361 on 2018-07-18T14:51:57Z with date null by astein@illinois.edu.","Open","147 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981."],"dc:identifier":["http://hdl.handle.net/2142/68183","(UMI)AAI8127730"],"dc:language":["eng"],"dc:subject":["Mathematics"],"dc:title":["A Hierarchy of Families of Recursively Enumerable Degrees and A Theorem on Bounding Minimal Pairs"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:58Z"}