The theory of the recursively enumerable weak truth-table degrees is undecidable
We show that the partial order of -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.
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
1992
|
| In: |
The journal of symbolic logic
Year: 1992, Volume: 57, Issue: 3, Pages: 864-874 |
| ISSN: | 1943-5886 |
| DOI: | 10.2307/2275436 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.2307/2275436 Verlag, lizenzpflichtig, Volltext: https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/theory-of-the-recursively-enumerable-weak-truthtable-degrees-is-undecidable/9AF374E0E3D43BFEB21D61EED2B9D110 
|
| Author Notes: | Klaus Ambos-Spies, André Nies, Richard A. Shore |
| Summary: | We show that the partial order of -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. |
|---|---|
| Item Description: | Elektronische Reproduktion der Druck-Ausgabe 12. März 2014 Gesehen am 26.06.2023 |
| Physical Description: | Online Resource |
| ISSN: | 1943-5886 |
| DOI: | 10.2307/2275436 |