A Hierarchy of Families of Recursively Enumerable Degrees and A Theorem on Bounding Minimal Pairs

Welch, Lawrence Vaughn

Permalink

https://hdl.handle.net/2142/68183 Copy

Description

Title

A Hierarchy of Families of Recursively Enumerable Degrees and A Theorem on Bounding Minimal Pairs

Author(s)

Welch, Lawrence Vaughn

Issue Date

1981

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Mathematics

Language

eng

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 .

Graduation Semester

1981

Type of Resource

text

Permalink

http://hdl.handle.net/2142/68183

Owning Collections