Files in this item



application/pdf8127730.pdf (6MB)
(no description provided)PDF


Title:A Hierarchy of Families of Recursively Enumerable Degrees and A Theorem on Bounding Minimal Pairs
Author(s):Welch, Lawrence Vaughn
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
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.
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
Description:147 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981.
Other Identifier(s):(UMI)AAI8127730
Date Available in IDEALS:2014-12-14
Date Deposited:1981

This item appears in the following Collection(s)

Item Statistics