Geodesic
On theories of the subsets algebra and the subspaces lattice for finite linear spaces
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 1 (2025), pp. 5-13

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

For infinite linear spaces, in our previous works, we have shown that theories of figures and subspaces are of high undecidability degree. They allow interpreting elementary arithmetic or second-order arithmetic (for infinite figures). For finite linear spaces, such a claim doesn't hold. It is because we can algorithmically enumerate all finite linear spaces and find all formulas with finite models. So, for finite linear spaces, theories of figures and subspaces are in the class $\Pi_1$. It is the class of problems whose complements are recursively enumerable. In the present paper, we prove that these theories are $\Pi_1$-complete, therefore, they are algorithmically undecidable and not recursively axiomatizable.
Keywords: finite algebra, linear space, subset algebra, subspace, algorithmic undecidability, completeness.
Mots-clés : subalgebras lattice 
@article{VTPMK_2025_1_a0,
     author = {S. M. Dudakov},
     title = {On theories of the subsets algebra and the subspaces lattice for finite linear spaces},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {5--13},
     publisher = {mathdoc},
     number = {1},
     year = {2025},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2025_1_a0/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - On theories of the subsets algebra and the subspaces lattice for finite linear spaces
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2025
SP  - 5
EP  - 13
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2025_1_a0/
LA  - ru
ID  - VTPMK_2025_1_a0
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T On theories of the subsets algebra and the subspaces lattice for finite linear spaces
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2025
%P 5-13
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VTPMK_2025_1_a0/
%G ru
%F VTPMK_2025_1_a0
S. M. Dudakov. On theories of the subsets algebra and the subspaces lattice for finite linear spaces. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 1 (2025), pp. 5-13. http://geodesic.mathdoc.fr/item/VTPMK_2025_1_a0/