David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jonathan Jenkins Ichikawa
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 66 (2):731-770 (2001)
The following theorems on the structure inside nonrecursive truth-table degrees are established: Dëgtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to the following question of Jockusch: does every truth-table degree contain an infinite antichain of many-one degrees? Some but not all truth-table degrees have a least bounded truth-table degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings: there are Turing degrees (constructed as hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and therefore do not contain any objective set. Furthermore, a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of coenumerable semirecursive sets and one of sets, which are neither enumerable nor coenumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integer as for example nineteen, but it is never an even finite number
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
Webb Miller & D. A. Martin (1968). The Degrees of Hyperimmune Sets. Mathematical Logic Quarterly 14 (7‐12):159-166.
Webb Miller & D. A. Martin (1968). The Degrees of Hyperimmune Sets. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 14 (7-12):159-166.
Richard M. Friedberg & Hartley Rogers (1959). Reducibility and Completeness for Sets of Integers. Mathematical Logic Quarterly 5 (7‐13):117-125.
Richard M. Friedberg & Hartley Rogers (1959). Reducibility and Completeness for Sets of Integers. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
R. G. Downey (1988). Recursively Enumerablem- Andtt-Degrees II: The Distribution of Singular Degrees. [REVIEW] Archive for Mathematical Logic 27 (2):135-147.
Citations of this work BETA
No citations found.
Similar books and articles
Josep Maria Font (2009). Taking Degrees of Truth Seriously. Studia Logica 91 (3):383 - 406.
Guohua Wu (2004). Bi-Isolation in the D.C.E. Degrees. Journal of Symbolic Logic 69 (2):409 - 420.
Peter A. Fejer & Richard A. Shore (1988). Infima of Recursively Enumerable Truth Table Degrees. Notre Dame Journal of Formal Logic 29 (3):420-437.
Rodney G. Downey & Steffen Lempp (1997). Contiguity and Distributivity in the Enumerable Turing Degrees. Journal of Symbolic Logic 62 (4):1215-1240.
Paul Fischer (1986). Pairs Without Infimum in the Recursively Enumerable Weak Truth Table Degrees. Journal of Symbolic Logic 51 (1):117-129.
Peter Cholak, Rod Downey & Stephen Walk (2002). Maximal Contiguous Degrees. Journal of Symbolic Logic 67 (1):409-437.
Klaus Ambos-Spies, André Nies & Richard A. Shore (1992). The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable. Journal of Symbolic Logic 57 (3):864-874.
Johanna N. Y. Franklin (2010). Subclasses of the Weakly Random Reals. Notre Dame Journal of Formal Logic 51 (4):417-426.
Franz Huber (2009). Belief and Degrees of Belief. In F. Huber & C. Schmidt-Petri (eds.), Degrees of Belief. Springer
Added to index2009-01-28
Total downloads25 ( #162,739 of 1,934,425 )
Recent downloads (6 months)4 ( #145,801 of 1,934,425 )
How can I increase my downloads?