The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable
Ambos-Spies, Klaus ; Nies, Andre ; Shore, Richard A.
J. Symbolic Logic, Tome 57 (1992) no. 1, p. 864-874 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We show that the partial order of $\Sigma^0_3$-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.
Publié le : 1992-09-14
Classification:  
@article{1183744045,
     author = {Ambos-Spies, Klaus and Nies, Andre and Shore, Richard A.},
     title = {The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable},
     journal = {J. Symbolic Logic},
     volume = {57},
     number = {1},
     year = {1992},
     pages = { 864-874},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744045}
}

Ambos-Spies, Klaus; Nies, Andre; Shore, Richard A. The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable. J. Symbolic Logic, Tome 57 (1992) no. 1, pp.  864-874. http://gdmltest.u-ga.fr/item/1183744045/