RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2016 Volume 55, Number 4, Pages 432–440 (Mi al750)

$\Pi^1_1$-completeness of the computable categoricity problem for projective planes

N. T. Kogabaevab

a Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090 Russia
b Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090 Russia

Abstract: 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, computable dimension, Desarguesian projective plane, Pappian projective plane, projective plane.

UDC: 510.53+514.146

Received: 27.04.2016
Revised: 24.06.2016

DOI: 10.17377/alglog.2016.55.403


 English version:
Algebra and Logic, 2016, 55:4, 283–288

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025