University of Illinois Urbana-Champaign

Some results on e-genericity and recursively enumerable weak truth table degrees

Blaylock, Richard Warren

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/22493

Description

Title
Some results on e-genericity and recursively enumerable weak truth table degrees
Author(s)
Blaylock, Richard Warren
Issue Date
1991
Doctoral Committee Chair(s)
Jockusch, Carl G., Jr.
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
  • In this manuscript we explore two topics in recursion theory and their interaction.
  • The first topic is e-genericity, a notion of genericity for recursively enumerable (r.e.) sets introduced by C. G. Jockusch, Jr. The second is weak truth table reducibility (w-reducibility), a strong reducibility (i.e., stronger than the most general Turing reducibility) first introduced by Friedberg and Rogers. In Chapter 1 we give a brief introduction to these topics and establish the relevant terminology and notation.
  • In Chapter 2 we give some closure and non-closure properties for the classes of e-generic sets and degrees, which are predicted by analogous results for previous notions of genericity. For example, the e-generic sets are not closed under union, intersection, or join, but on the other hand if the join $A \oplus B$ of two sets is e-generic, then so are $A,B, A \cup B$, and $A \cap B$.
  • In Chapter 3 we investigate the structure of the weak truth table degrees (w-degrees) inside an e-generic Turing degree. Here we show that e-generic Turing degrees are highly noncontiguous in the sense that they contain no greatest and no least r.e. w-degree.
  • Finally in Chapter 4 we obtain some results on the ordering of the r.e. w-degrees in general. The main result is the existence of a nontrivial r.e. w-degree a which has a greatest lower bound with every r.e. w-degree b. We also show that these nontrivial completely cappable degrees can neither be low nor promptly simple.
Type of Resource
text
Permalink
http://hdl.handle.net/2142/22493
Copyright and License Information
Copyright 1991 Blaylock, Richard Warren

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mathematics