Infima of recursively enumerable truth table degrees

DOI10.1305/NDJFL/1093637938MaRDI QIDQ1114676zbMATH OpenOpenAlexFDO

Authors Peter A. Fejer, Richard A. Shore

Publication date 1988

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1305/ndjfl/1093637938

zbMATH Keywords

minimal pairtruth-table degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Review text

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.

Recommendations

• Infima in the recursively enumerable weak truth table degrees
• Structural interactions of the recursively enumerable T- and W-degrees
• Pairs without infimum in the recursively enumerable weak truth table degrees
• Infimum properties differ in the weak truth-table degrees and the Turing degrees
• Relations between table-type degrees

Cited in

(16)

• Infima in the recursively enumerable weak truth table degrees
• Infimum properties differ in the weak truth-table degrees and the Turing degrees
• Interpreting true arithmetic in the theory of the r.e. truth table degrees
• On the structures inside truth-table degrees
• Some results on bounded truth-table degrees
• On Pairs of Recursively Enumerable Degrees
• scientific article; zbMATH DE number 4170891 (Why is no real title available?)
• Wtt-degrees and T-degrees of r.e. sets
• Pairs without infimum in the recursively enumerable weak truth table degrees
• Two Theorems on Truth Table Degrees
• Degree theoretic definitions of the low₂ recursively enumerable sets
• Minimal weak truth table degrees and computably enumerable Turing degrees
• scientific article; zbMATH DE number 3893186 (Why is no real title available?)
• Every incomplete computably enumerable truth-table degree is branching
• Infima in the d.r.e. degrees
• The density of infima in the recursively enumerable degrees

This page was built for publication: Infima of recursively enumerable truth table degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114676)