Freely generated projective planes with finite computable dimension

N. T. Kogabaev

Algebra i logika, Tome 55 (2016) no. 6, pp. 704-737.

Résumé

It is proved that for every natural $n\ge1$, there exists a computable freely generated projective plane with computable dimension $n$. It is stated that the class of freely generated projective planes is complete with respect to degree spectra of automorphically nontrivial structures, effective dimensions, expansions by constants, and degree spectra of relations.

Détail

Keywords: degree spectra of automorphically nontrivial structures, expansions by constants, and degree spectra of relations.
Mots-clés : effective dimensions

Bibliographie

[1] N. T. Kogabaev, “Klass proektivnykh ploskostei nevychislim”, Algebra i logika, 47:4 (2008), 428–455 | MR | Zbl

[2] S. S. Goncharov, “Problema chisla neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 19:6 (1980), 621–639 | MR

[3] S. S. Goncharov, A. V. Molokov, N. S. Romanovskii, “Nilpotentnye gruppy konechnoi algoritmicheskoi razmernosti”, Sib. matem. zh., 30:1 (1989), 82–88 | MR | Zbl

[4] B. Khoussainov, R. A. Shore, “Computable isomorphisms, degree spectra of relations, and Scott families”, Ann. Pure Appl. Logic, 93:1–3 (1998), 153–193 | DOI | MR | Zbl

[5] P. Cholak, S. Goncharov, B. Khoussainov, R. A. Shore, “Computably categorical structures and expansions by constants”, J. Symb. Log., 64:1 (1999), 13–37 | DOI | MR | Zbl

[6] B. M. Khusainov, R. A. Shor, “O reshenii problemy Goncharova–Esha i problemy spektra v teorii vychislimykh modelei”, Dokl. RAN, 371:1 (2000), 30–31 | MR | Zbl

[7] R. Miller, B. Poonen, H. Schoutens, A. Shlapentokh, A computable functor from graphs to fields, submitted, arXiv: 1510.07322

[8] L. Richter, “Degrees of structures”, J. Symb. Log., 46:4 (1981), 723–731 | DOI | MR | Zbl

[9] J. F. Knight, “Degrees coded in jumps of orderings”, J. Symb. Log., 51:4 (1986), 1034–1042 | DOI | MR | Zbl

[10] T. A. Slaman, “Relative to any nonrecursive set”, Proc. Am. Math. Soc., 126:7 (1998), 2117–2122 | DOI | MR | Zbl

[11] S. Wehner, “Enumeration, countable structure and Turing degrees”, Proc. Am. Math. Soc., 126:7 (1998), 2131–2139 | DOI | MR | Zbl

[12] I. Sh. Kalimullin, “Spektry stepenei nekotorykh algebraicheskikh struktur”, Algebra i logika, 46:6 (2007), 729–744 | MR | Zbl

[13] A. Frolov, I. Kalimullin, V. Harizanov, O. Kudinov, R. Miller, “Spectra of highn and non-lown degrees”, J. Log. Comput., 22:4 (2012), 755–777 | DOI | MR | Zbl

[14] V. S. Harizanov, “Uncountable degree spectra”, Ann. Pure Appl. Logic, 54:3 (1991), 255–263 | DOI | MR | Zbl

[15] V. S. Harizanov, “Some effects of Ash-Nerode and other decidability conditions on degree spectra”, Ann. Pure Appl. Logic, 55:1 (1991), 51–65 | DOI | MR | Zbl

[16] V. S. Harizanov, “The possible Turing degree of the nonzero member in a two element degree spectrum”, Ann. Pure Appl. Logic, 60:1 (1993), 1–30 | DOI | MR | Zbl

[17] D. R. Hirschfeldt, “Degree spectra of relations on structures of finite computable dimension”, Ann. Pure Appl. Logic, 115:1–3 (2002), 233–277 | DOI | MR | Zbl

[18] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Ann. Pure Appl. Logic, 115:1–3 (2002), 71–113 | DOI | MR | Zbl

[19] N. T. Kogabaev, “Teoriya proektivnykh ploskostei polna otnositelno spektrov stepenei i effektivnykh razmernostei”, Algebra i logika, 54:5 (2015), 599–627 | MR | Zbl

[20] A. I. Shirshov, A. A. Nikitin, “K teorii proektivnykh ploskostei”, Algebra i logika, 20:3 (1981), 330–356 | MR | Zbl

[21] D. R. Hughes, F. C. Piper, Projective planes, Grad. Texts Math., 6, Springer-Verlag, New York–Heidelberg–Berlin, 1973 | MR | Zbl

[22] N. T. Kogabaev, “Nerazreshimost teorii proektivnykh ploskostei”, Algebra i logika, 49:1 (2010), 3–17 | MR | Zbl

[23] A. A. Nikitin, “O svobodno porozhdënnykh proektivnykh ploskostyakh”, Algebra i logika, 22:1 (1983), 61–77 | MR