Density of a final segment of the truth-table degrees
type: Item
instance of: scholarly article
title: Density of a final segment of the truth-table degrees
zbMATH Open document ID: 0534.03018
author: Jeanleah Mohrherr
published in: Pacific Journal of Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 3847372
zbMATH Keywords: truth table degrees
zbMATH Keywords: minimal cover
zbMATH Keywords: jump theorem
zbMATH Keywords: halting problem
MaRDI profile type: Publication
full work available at URL: pjm.1984.115.409
OpenAlex ID: W2091909693
DOI: 10.2140/PJM.1984.115.409
description: scientific article; zbMATH DE number 3847372