Infima in the Recursively Enumerable Weak Truth Table Degrees

, &
Notre Dame Journal of Formal Logic 38 (3):406-418 (1997)
  Copy   BIBTEX

Abstract

We show that for every nontrivial r.e. wtt-degree a, there are r.e. wtt-degrees b and c incomparable to a such that the infimum of a and b exists but the infimum of a and c fails to exist. This shows in particular that there are no strongly noncappable r.e. wtt-degrees, in contrast to the situation in the r.e. Turing degrees

Categories

Keywords

Reprint years

DOI

10.1305/ndjfl/1039700747

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,752

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices.Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman - 1996 - Journal of Symbolic Logic 61 (3):880-905.
Infima of recursively enumerable truth table degrees.Peter A. Fejer & Richard A. Shore - 1988 - Notre Dame Journal of Formal Logic 29 (3):420-437.
Pairs without infimum in the recursively enumerable weak truth table degrees.Paul Fischer - 1986 - Journal of Symbolic Logic 51 (1):117-129.
On the structures inside truth-table degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
The theory of the recursively enumerable weak truth-table degrees is undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.
Complementation in the Turing degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
Decomposition and infima in the computably enumerable degrees.Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (2):551-579.
The role of true finiteness in the admissible recursively enumerable degrees.Noam Greenberg - 2005 - Bulletin of Symbolic Logic 11 (3):398-410.
On recursive enumerability with finite repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
Recursively enumerable m- and tt-degrees. I: The quantity of m- degrees.R. G. Downey - 1989 - Journal of Symbolic Logic 54 (2):553-567.
A limit on relative genericity in the recursively enumerable sets.Steffen Lempp & Theodore A. Slaman - 1989 - Journal of Symbolic Logic 54 (2):376-395.
On the orbits of hyperhypersimple sets.Wolfgang Maass - 1984 - Journal of Symbolic Logic 49 (1):51-62.
The existential theory of the poset of R.e. Degrees with a predicate for single jump reducibility.Steffen Lempp & Manuel Lerman - 1992 - Journal of Symbolic Logic 57 (3):1120-1130.

Analytics

Added to PP
2010-08-24

Downloads
46 (#344,354)

6 months
12 (#210,071)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
A minimal pair of recursively enumerable degrees.C. E. M. Yates - 1966 - Journal of Symbolic Logic 31 (2):159-168.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
Wtt-degrees and t-degrees of R.e. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.

View all 10 references / Add more references