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.
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
1992
|
| In: |
The journal of symbolic logic
Year: 1992, Jahrgang: 57, Heft: 3, Pages: 864-874 |
| ISSN: | 1943-5886 |
| DOI: | 10.2307/2275436 |
| Online-Zugang: | 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 
|
| Verfasserangaben: | Klaus Ambos-Spies, André Nies, Richard A. Shore |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Elektronische Reproduktion der Druck-Ausgabe 12. März 2014 Gesehen am 26.06.2023 |
| Beschreibung: | Online Resource |
| ISSN: | 1943-5886 |
| DOI: | 10.2307/2275436 |