Files in this item
Files  Description  Format 

application/pdf 8127730.pdf (6MB)  (no description provided) 
Description
Title:  A Hierarchy of Families of Recursively Enumerable Degrees and A Theorem on Bounding Minimal Pairs 
Author(s):  Welch, Lawrence Vaughn 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
Abstract:  This thesis is concerned with the properties of recursivelyenumerable setsthat is, sets which can be listed by Turingmachinesand 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 . 
Issue Date:  1981 
Type:  Text 
Language:  English 
Description:  147 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1981. 
URI:  http://hdl.handle.net/2142/68183 
Other Identifier(s):  (UMI)AAI8127730 
Date Available in IDEALS:  20141214 
Date Deposited:  1981 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois