The \(\Delta_2^0\)-spectrum of a linear order. (English) Zbl 0992.03050
The spectrum \(\text{Spec}(S)\) of an algebraic structure \(S\) is the class of Turing degrees of presentations of \(S\). Slaman and independently Wehner constructed an example of a structure with \(\text{Spec}(S)= {\mathbf D}\setminus \{\mathbf{0}\}\) where D is the class of all Turing degrees. Answering a question of Downey, the author constructs an example of a linear order whose spectrum includes every non-computable \(\Delta_2^0\)-degree.
Reviewer: Shamil Ishmukhametov (Ul’yanovsk)
MSC:
| 03D25 | Recursively (computably) enumerable sets and degrees |
References:
| [1] | Complexity, logic, and recursion theory pp 157– (1997) |
| [2] | DOI: 10.1090/S0002-9939-1994-1203984-4 · doi:10.1090/S0002-9939-1994-1203984-4 |
| [3] | DOI: 10.1090/S0002-9947-1990-0955487-0 · doi:10.1090/S0002-9947-1990-0955487-0 |
| [4] | DOI: 10.1090/S0002-9939-98-04314-7 · Zbl 0906.03044 · doi:10.1090/S0002-9939-98-04314-7 |
| [5] | Recursively enumerable sets and degrees (1987) |
| [6] | DOI: 10.1090/S0002-9939-98-04307-X · Zbl 0894.03017 · doi:10.1090/S0002-9939-98-04307-X |
| [7] | Linear orderings (1982) · Zbl 0488.04002 |
| [8] | Degrees of structures 46 pp 723– (1981) |
| [9] | Recursion theory: Its generalizations and applications pp 52– (1980) |
| [10] | Degrees coded into jumps of orderings 51 pp 1034– (1986) · Zbl 0633.03038 |
| [11] | Computable boolean algebras · Zbl 1197.03038 |
| [12] | DOI: 10.1016/0168-0072(91)90038-N · Zbl 0734.03026 · doi:10.1016/0168-0072(91)90038-N |
| [13] | Proceedings of the American Mathematical Society 114 pp 545– (1992) |
| [14] | Handbook of computable algebra |
| [15] | DOI: 10.1090/S0002-9939-1954-0063995-6 · doi:10.1090/S0002-9939-1954-0063995-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
