Density of a final segment of the truth-table degrees (Q790105)

This paper gives a proof that the truth-table degrees above the truth- table degree of the halting problem are dense. This is in contrast to the well known property of Turing degrees that every Turing degree has a minimal cover. Richard Shore had already constructed a first order sentence that is true in the Turing degrees and false in the truth-table degrees, but the main result of this paper gives a simple and explicit example of elementary inequivalence. An essential part of the proof is showing that every truth-table degree above that of the halting problem is the jump of another truth-table degree. Whether the full Friedberg completeness theorem (including cupping) holds for the truth-table degrees is open. Some other results and open questions, concerning truth- table degrees, are stated in the paper.