Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
The Computable Dimension of Free Projective Planes

Edit abstract data

Speaker: Nurlan Kogabaev
Slot: Wed, 17:10-17:30, Room 24 (col. 3)


Shirshov (cf.\,\cite{ShirshovNikitin}) suggested to treat projective
planes as partial algebraic systems. In the framework of this
approach a \emph{projective plane} is a structure $\langle
A,(A^0,{}^0\!A),\cdot\rangle$ with a disjunction of $A$ into two
subsets $A^0\cup{}^0\!A=A$,
$A^0\cap{}^0\!A=\emptyset$ and commutative partial operation
``$\cdot$'' which satisfy the following properties:


$a{\cdot}b$ is defined iff $a{\neq}b$ and $a,b\in A^0$ (or
$a,b\in{}^0\!A$) with the product $a{\cdot}b\in{}^0\!A$
($a{\cdot}b\in A^0$ respectively);

for all $a,b,c\in A$ if $a{\cdot}b$, $a{\cdot}c$,
$(a{\cdot}b){\cdot}(a{\cdot}c)$ are defined, then

there exist distinct $a,b,c,d\in A$ such that products $a{\cdot}b$,
$b{\cdot}c$, $c{\cdot}d$, $d{\cdot}a$ are defined and pairwise


From the results of \cite{ShirshovNikitin} it follows that any
countable free projective plane has a computable presentation.

In the present paper we investigate the question of possible
computable dimension of free projective planes and the existence
problem of computable list for the class of all projective planes (up
to computable isomorphism).

We prove that every countable free projective plane has computable
dimension $1$ or $\omega$. Furthermore, such a plane is computably
categorical if and only if it has finite rank. We also prove that the
class of all projective planes is not computable (up to computable


{\itshape A.I.Shirshov, A.A.Nikitin}, On the theory of projective
planes, Algebra and Logic, vol.~20 (1981), no.~3, pp.~330--356.

websites: Arnold Beckmann 2008-05-19 Valid HTML 4.01! Valid CSS!