The index set of linear orderings that are autostable relative to strong constructivizations

S. S. Goncharov   ; N. A. Bazhenov   ; M. I. Marchuk

Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 15 (2015) no. 3, pp. 51-60

Résumé

We prove that a computable ordinal $\alpha$ is autostable relative to strong constructivizations if and only if $\alpha\omega^{\omega+1}$. We calculate, in a precise way, the complexity of the index set for linear orderings that are autostable relative to strong constructivizations.

Détail

Keywords: computable model, strongly constructivizable model, autostability, autostability relative to strong constructivizations, linear ordering, computable ordinal, index set.

Bibliographie

[1] S. S. Goncharov, J. F. Knight, “Computable structure and non-structure theorems”, Algebra and Logic, 41:6 (2002), 351–373 | DOI | MR | Zbl

[2] S. S. Goncharov, Yu. L. Ershov, Constructive Models, Kluwer Academic/Plenum Press, New York, 2002

[3] Ash C. J., Khight J., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, 144, Elsevier Science, Amsterdam, 2000 | MR | Zbl

[4] A. T. Nurtazin, Computable classes and algebraic criteria autostability, Thes. Cand. Math.-Phys. Degree, Alma-Ata, 1974 (in Russian)

[5] E. B. Fokina, “Index sets of decidable models”, Sib. Mat. J., 48:5 (2007), 939–948 | DOI | MR | Zbl

[6] A. T. Nurtazin, “Strong and weak constructivization and computable families”, Algebra and Logic, 13:3 (1974), 177–184 | DOI | MR | Zbl

[7] S. S. Goncharov, M. I. Marchuk, “Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations”, Algebra and Logic, 54:2 (2015), 108–126 | DOI | Zbl

[8] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of Boolean algebras autostable relative to strong constructivizations”, Sib. Mat. J., 56:3 (2015), 393–404 | DOI | Zbl

[9] S. S. Goncharov, M. I. Marchuk, “Index sets of autostable relative to strong constructivizations constructive models”, J. Math. Sci., 205:3 (2015), 368–388 | DOI | MR

[10] S. S. Goncharov, M. I. Marchuk, “Index sets of constructive models of nontrivial signature autostable relative to strong constructivizations”, Dokl. Math., 91:2 (2015), 158–159 | DOI | DOI | Zbl

[11] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Index sets of autostable relative to strong constructivizations constructive models of natural classes”, Dokl. AN, 464:1 (2015), 12–14 (in Russian) | DOI

[12] Rosenstein J. G., Linear Orderings, Academic Press, New York, 1982 | MR | Zbl

[13] Downey R. G., “Computability Theory and Linear Orderings”, Handbook of Recursive Mathematics, v. 2, eds. Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, Elsevier Sci. B.V., Amsterdam, 1998, 823–976 | MR | Zbl

[14] C. C. Chang, H. K. Keisler, Model Theory, Studies in Logic and the Foundations of Mathematics, North Holland Publishing Company, Amsterdam–N. Y.–Oxford, 1990 | MR | MR | Zbl

[15] A. T. Nurtazin, “Strong and weak constructivization and computable families”, Algebra and Logic, 13:3 (1974), 177–184 | DOI | MR | Zbl

[16] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Company, New York, 1967 | MR | MR | Zbl

[17] Ash C. J., “Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees”, Trans. Am. Math. Soc., 298:2 (1986), 497–514 | DOI | MR | Zbl

[18] Ash C. J., Knight J. F., “Pairs of Recursive Structures”, Ann. Pure Appl. Logic, 46:3 (1990), 211–234 | DOI | MR | Zbl

[19] N. G. Khisamiev, Constructive Ordinal is Strongly Constructivizable, Dep. VINITI, No 1604-79, 1978 (in Russian)

[20] Khoussainov B., Minnes M., “Three Lectures on Automatic Structures”, Logic Colloquium 2007, eds. F. Delon, U. Kohlenbach, P. Maddy, F. Stephan, Cambridge University Press, New York, 2010, 132–176 | DOI | MR | Zbl

[21] Delhommé C., “Automacité des Ordinaux et des Graphes Homogènes”, C.R. Math., Acad. Sci. Paris, 339:1 (2004), 5–10 | DOI | MR | Zbl

[22] A.Ȧ Revenko, “Autostability of automatic presentations of well orders and low rank linear orders”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 8:4 (2008), 78–88 (in Russian)