- IDEALS Home
- Graduate Theses and Dissertations at Illinois
- Graduate Theses and Dissertations at Illinois
- View Item
Some results on e-genericity and recursively enumerable weak truth table degrees
Bookmark or cite this item:
http://hdl.handle.net/2142/22493
Files in this item
| File | Description | Format |
|---|---|---|
9210749.pdf
(3MB)
|
(no description provided) |
| 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 |
Items in IDEALS are protected by copyright, with all rights reserved, unless otherwise indicated.
This item appears in the following Collection(s)
-
Dissertations and Theses - Mathematics
-
Graduate Theses and Dissertations at Illinois
Graduate Theses and Dissertations at Illinois
Item Statistics
- Total Downloads: 1
- Downloads this Month: 0
- Downloads Today: 0
