Infima of recursively enumerable truth table degrees (Q1114676)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Infima of recursively enumerable truth table degrees |
scientific article |
Statements
Infima of recursively enumerable truth table degrees (English)
0 references
1988
0 references
The following interesting results are obtained: Theorem 1. There are r.e. tt-degrees \(a_ 0\) and \(a_ 1\) such that \(a_ 0\) and \(a_ 1\) form a minimal pair among the r.e. tt-degrees but have a nonzero inf among all tt-degrees. Theorem 2. There are r.e. tt-degrees \(a_ 0\) and \(a_ 1\) such that \(a_ 0\) and \(a_ 1\) have no infimum among the r.e. tt-degrees but have an infimum among all tt-degrees. Theorem 3. There are r.e. tt- degrees \(a_ 0\) and \(a_ 1\) such that \(a_ 0\) and \(a_ 1\) form a minimal pair among the r.e. tt-degrees but have no inf among all tt- degrees. Theorem 4. There are r.e. tt-degrees \(a_ 0\) and \(a_ 1\) such that \(a_ 0\) and \(a_ 1\) have an infimum neither among the r.e. tt- degrees nor among all tt-degrees.
0 references
truth-table degrees
0 references
minimal pair
0 references