zbMATH — the first resource for mathematics

Index sets for classes of high rank structures. (English) Zbl 1145.03021
The authors prove that the index set of the class of all structures of non-computable Scott rank is $$\Sigma_1^1$$-complete; the index set of the class of structures of Scott rank $$\omega^{CK}_1$$ is $$\Pi_2^0$$-complete relative to Klenee’s $${\mathcal O}$$; and the index set of the class of structures of Scott rank $$\omega^{CK}_1+1$$ is $$\Sigma_1^0$$-complete relative to $${\mathcal O}$$.

MSC:
 03D45 Theory of numerations, effectively presented structures 03C57 Computable structure theory, computable model theory
Full Text:
References:
 [1] Admissible sets and structures: An approach to definability theory (1975) · Zbl 0316.02047 [2] Proceedings of the North Texas Logic Conference, October, 2004 [3] DOI: 10.1016/0168-0072(90)90004-L · Zbl 0712.03020 [4] DOI: 10.1002/malq.200310066 · Zbl 1035.03017 [5] The theory of models pp 329– (1965) [6] Higher recursion theory (1990) · Zbl 0716.03043 [7] Theory of recursive functions and effective comput ability (1967) [8] DOI: 10.1016/0003-4843(74)90017-5 · Zbl 0301.02050 [9] An example concerning Scott heights 46 pp 301– (1981) [10] Journal of Mathematical Logic [11] Model theory for infinitary logic (1971) [12] DOI: 10.1023/A:1021758312697 [13] DOI: 10.1090/S0002-9947-1968-0244049-7 [14] relations and paths through 69 pp 585– (2004) [15] Trees of Scott rank and computable approximability 71 pp 283– (2006) [16] DOI: 10.1007/s10469-006-0029-0 · Zbl 1164.03325 [17] Computable structures and the hyperarithmetical hierarchy (2000) · Zbl 0960.03001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.