IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

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

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/22493

Files in this item

File Description Format
PDF 9210749.pdf (3MB) Restricted to U of Illinois (no description provided) PDF
Title: Some results on e-genericity and recursively enumerable weak truth table degrees
Author(s): Blaylock, Richard Warren
Doctoral Committee Chair(s): Jockusch, C. G., Jr
Department / Program: Mathematics
Discipline: Mathematics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(s): Mathematics
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.
Issue Date: 1991
Type: Text
Language: English
URI: http://hdl.handle.net/2142/22493
Rights Information: Copyright 1991 Blaylock, Richard Warren
Date Available in IDEALS: 2011-05-07
Identifier in Online Catalog: AAI9210749
OCLC Identifier: (UMI)AAI9210749
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 1
  • Downloads this Month: 0
  • Downloads Today: 0

Browse

My Account

Information

Access Key