|
Mathematical Logic, Algebra, Number Theory and Discrete Mathematics
On theories of the subsets algebra and the subspaces lattice for finite linear spaces
S. M. Dudakovab a HSE University, Moscow
b Tver State University, Tver
Abstract:
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, subalgebras lattice, algorithmic undecidability, completeness.
Received: 02.02.2025 Revised: 25.02.2025
Citation:
S. M. Dudakov, “On theories of the subsets algebra and the subspaces lattice for finite linear spaces”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2025, no. 1, 5–13
Linking options:
https://www.mathnet.ru/eng/vtpmk728 https://www.mathnet.ru/eng/vtpmk/y2025/i1/p5
|
Statistics & downloads: |
Abstract page: | 52 | Full-text PDF : | 19 | References: | 5 |
|