Computable trees of Scott rank \(\omega_1^{CK}\), and computable approximation. (English) Zbl 1112.03039

In [“An example concerning Scott heights”, J. Symb. Log. 46, 301–318 (1981; Zbl 0501.03018)], M. Makkai produced an arithmetical structure of Scott rank \(\omega_{1}^{CK}\). Knight and Young later constructed computable structures of rank \(\omega_{1}^{CK}\). In this paper, the authors show that there are computable trees of Scott rank \(\omega_{1}^{CK}\). The paper also presents an example of a computable tree of rank \(\omega_{1}^{CK}\) which is strongly computably approximable. This is the first example of a structure of Scott rank \(\omega_{1}^{CK}\) for which strong computable approximability is known. This example is related to the following open problem: Whether all structures of noncomputable Scott rank are strongly computably approximable [S. S. Goncharov and J. F. Knight, “Computable structure and non-structure theorems”, Algebra Logika 41, No. 6, 639–681 (2002); translation in Algebra Logic 41, No. 6, 351–373 (2002; Zbl 1034.03044)].


03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
Full Text: DOI arXiv


[1] Computable Structures and the Hyperarithmetical Hierarchy (2000) · Zbl 0960.03001
[2] Infinitary logic and admissible sets 34 pp 226– (1969)
[3] Mixed systems 59 pp 1383– (1994)
[4] DOI: 10.1016/0168-0072(90)90004-L · Zbl 0712.03020
[5] The Theory of Models pp 329– (1965)
[6] Higher Recursion Theory (1990) · Zbl 0716.03043
[7] Theory of Recursive Functions and Effective Computability (1967) · Zbl 0183.01401
[8] Model-Theoretic Logics 45 pp 612– (1980)
[9] DOI: 10.1016/0003-4843(74)90017-5 · Zbl 0301.02050
[10] Handbook of Recursive Mathematics pp 311– (1998) · Zbl 0930.03037
[11] Journal of Mathematical Logic
[12] An example concerning Scott heights 46 pp 301– (1981)
[13] DOI: 10.1090/S0002-9947-1968-0244049-7
[14] DOI: 10.1023/A:1021758312697
[15] {\(\Pi\)}1 1 relations and paths through O 69 pp 585– (2004)
[16] DOI: 10.1016/S0168-0072(94)90009-4 · Zbl 0819.03024
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.