Geodesic
$\Pi^1_1$-completeness of the computable categoricity problem
Algebra i logika, Tome 55 (2016) no. 4, pp. 432-440.

Voir la notice de l'article provenant de la source Math-Net.Ru

Computable presentations for projective planes are studied. We prove that the problem of computable categoricity is $\Pi^1_1$-complete for the following classes of projective planes: Pappian projective planes, Desarguesian projective planes, arbitrary projective planes.
Keywords: computable categoricity, computable structure, Desarguesian projective plane, Pappian projective plane, projective plane.
Mots-clés : computable dimension 
@article{AL_2016_55_4_a2,
     author = {N. T. Kogabaev},
     title = {$\Pi^1_1$-completeness of the computable categoricity problem},
     journal = {Algebra i logika},
     pages = {432--440},
     publisher = {mathdoc},
     volume = {55},
     number = {4},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2016_55_4_a2/}
}
TY  - JOUR
AU  - N. T. Kogabaev
TI  - $\Pi^1_1$-completeness of the computable categoricity problem
JO  - Algebra i logika
PY  - 2016
SP  - 432
EP  - 440
VL  - 55
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2016_55_4_a2/
LA  - ru
ID  - AL_2016_55_4_a2
ER  - 
%0 Journal Article
%A N. T. Kogabaev
%T $\Pi^1_1$-completeness of the computable categoricity problem
%J Algebra i logika
%D 2016
%P 432-440
%V 55
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2016_55_4_a2/
%G ru
%F AL_2016_55_4_a2
N. T. Kogabaev. $\Pi^1_1$-completeness of the computable categoricity problem. Algebra i logika, Tome 55 (2016) no. 4, pp. 432-440. http://geodesic.mathdoc.fr/item/AL_2016_55_4_a2/

[1] R. G. Downey, A. M. Kach, S. Lempp, A. E. M. Lewis-Pye, A. Montalbán, D. D. Turetsky, “The complexity of computable categoricity”, Adv. Math., 268 (2015), 423–466 | DOI | MR | Zbl

[2] 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

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

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

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

[6] A. I. Shirshov, A. A. Nikitin, Algebraicheskaya teoriya proektivnykh ploskostei, Novosibirskii gos. un-t, Novosibirsk, 1987

[7] S. S. Goncharov, Yu. L. Ershov, Konstruktivnye modeli, Sibirskaya shkola algebry i logiki, Nauchnaya kniga, Novosibirsk, 1999

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

[9] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei estestvennykh klassov”, Doklady AN, 464:1 (2015), 12–14 | DOI | MR | Zbl