Search

Studying the elementary properties of free projective planes of finite rank, we prove that for m > n, an arbitrary ∀∃∀-formula Φ(ȳ) and a tuple ū of elements of the free projective plane $$\mathfrak{F}_{n}$$ if Φ(ū) holds on the plane $$\mathfrak{F}_{m}$$ then Φ(ū) holds on the plane $$\mathfrak{F}_{n}$$ too. This implies the coincidence of the ∀∃-theories of free projective planes of different finite ranks.

Studying computable representations of projective planes, we prove that the isomorphism problem in the class of free projective planes of finite rank is an m-complete Δ03-set within the class.

Computable presentations for projective planes are studied. We prove that the problem of computable categoricity is ∏ 1 1 -complete for the following classes of projective planes: Pappian projective planes, Desarguesian projective planes, arbitrary projective planes.

We prove that the theory of Pappian projective planes is complete with respect to degree spectra of automorphically nontrivial structures, effective dimensions, degree spectra of relations, categoricity spectra, and automorphism spectra. Therefore, for every natural n ≥ 2, there exists a computable Pappian projective plane with computable dimension n.

We study computable presentations for projective planes. We show that the isomorphism problem is Σ 1 1 complete for Pappian projective planes, Desarguesian projective planes, and arbitrary projective planes. Bibliography: 11 titles.

We study automatic presentations of projective planes and prove that no freely generated projective plane has any automatic presentations. Every desarguesian (pappian) projective plane is shown to be automatically presentable if and only if it is finite.

Computable presentations of projective planes are studied. Based on an interpretation of a class of fields (associative skew fields) within a class of Pappusian (Desarguesian) projective planes, it is proved that the question whether there exists a computable presentation for a Pappusian (Desarguesian) projective plane reduces to asking if there exists a computable presentation for a corresponding field (associative skew field). It is stated that the computable dimension of a Pappusian (Desarguesian) projective plane coincides with that of a corresponding field (associative skew field).

Elementary theories of projective planes are studied. The class of symmetric irreflexive graphs is proved to be relatively elementarily definable in the class of projective planes. Therefore, the theory of projective planes is hereditarily undecidable.

Computable projective planes are investigated. It is stated that a free projective plane of countable rank in some inessential expansion is unbounded. This implies that such a plane has infinite computable dimension. The class of all computable projective planes is proved to be noncomputable (up to computable isomorphism).

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ 1 1 -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ 3 0 -complete.

We study computable trees with distinguished initial subtree (briefly, I-trees). It is proved that all I-trees of infinite height are computably categorical, and moreover, they all have effectively infinite computable dimension.

Constructive Boolean algebras with distinguished ideals (we call them I-algebras in what follows) are studied. It is proved that a class of all constructive I-algebras is strongly computable, that is, the class of constructive I-algebras contains a principal computable numbering.