| Izvestiya: Mathematics |
|
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper) Problems of algorithmic decidability and axiomatizability of finite subset algebra for binary operations S. M. Dudakovab a Tver State University b HSE University, Moscow
Bibliographic databases:
   § 1. IntroductionIn mathematical logic, one of the central and actively studied problems is to construct new structures from existing ones and to investigate their algorithmic properties. For example, the classical result of such a kind is the construction of a multiplicative arithmetic of the natural numbers (the Skolem arithmetic) as the direct sum of infinite instances of the additive arithmetic (the Presburger arithmetic). This allows one to verify the algorithmic decidability of the Skolem arith- metic (see [1] and [2]). Another method for construction of new algebras is based on an extension of their operations from individual elements of the original algebra to their subsets. A typical example is the extension of the concatenation operation from words to languages (the concatenation of languages is the set of words obtained as concatenations of words from original languages). Other mathematical assertions may also be formulated in terms of these notions. For example, if the addition of natural numbers is extended to sets of natural numbers, then the binary Goldbach problem can be formulated as $P+P=E$, where $P$ is the set of all odd prime numbers, and $E$ is the set of all even numbers starting from $6$. In a similar way one can describe some NP-complete problems of complexity theory (see [3]). Thus, the investigation of new algebras constructed from subsets of existing algebras is an interesting problem in its own, which can be used as a tool for other problems. This is why subset algebras have been studied since the middle of the 20th century. The classical work here is [4] on semigroup subsets. The algebra of singletons (one-element subsets) is, evidently, isomorphic to an original one. So, the relevant problem here is to consider greater cardinality subsets, which form a class closed under operations of the original algebra. For example, this can be the class of finite subsets. In the case of languages, the important example is the class of regular languages (see [5] and [6]). For Abelian groups, we can consider the classes of finite subgroups, of all subgroups, etc. In the last case, we arrive to the lattice of subgroups, which is important in the study of the structure of the group itself (see [7], for example). Earlier, we have proved that algorithmic properties of a subset algebra can be the same as those of the original algebra or differ from these properties (they can be more involved or more simple). For example, in the two previously mentioned cases, for the word concatenation and for the natural number addition, finite subsets (of words or of numbers, correspondingly) form an algebra, whose theory is algorithmically equivalent to the first-order arithmetic (see [8]). On the other hand, there are examples of finite subset algebras with decidable theories. If we consider the maximum binary operation on natural numbers, the finite subset algebra is automatic. This can be easily shown — is enough to encode a finite subset by a string in the alphabet $\{0, 1\}$ (the $i$th symbol of the string is $1$ if and only if the number $i$ belongs to the subset). Other examples are given at the end of the paper. It is also possible to find a finite subset algebra with algorithmically decidable theory, while the theory of the original algebra can have an arbitrarily high degree of undecidability (see [10]). This calls for the problem of finding natural classes of algebras for which the theories of subset algebras can be uniformly described. One of the most studied classes here is the the class of Abelian groups. This class is a part of many other important classes (of groups, of monoids, of rings), and hence, its investigation can provide new results for other classes. In our previous papers, it was proved that there are some cases when the algebra of finite subsets of an Abelian group admits an interpretation of the first-order arithmetic. This holds if such a group has an element of infinite order (see [11]) or if there are elements of arbitrarily large finite orders (see [12]). The compactness theorem cannot be applied here because the theories of subset algebras can differ, while the original algebras are elementary equivalent. It is worth noting that interpretations are constructed differently in the two above cases. In the first case, there is an infinite cyclic subgroup, and the interpretation really uses its elements only. In the second case, there is an additional difficulty associated with transition to cyclic subgroups of higher orders as the number of interpreted natural number increases, because the interpretation of a natural number $n$ is based on consideration of some $(n+1)$-element subset of some cyclic subgroup, which is a part of the cyclic subgroup, whose order is $\geqslant n+1$. So, for Abelian groups, the one case is not covered — in this case, all elements of the groups are of limited orders (this is the case of finite exponent Abelian groups). Hence, to prove an ultimate result for the theory of finite subsets of an arbitrary infinite Abelian group, we should verify interpretability of the first-order arithmetic in such systems. Here, no methods from [11] and [12] can be used for this purpose, because, in the considered case, all cyclic subgroups are of limited order. In the present paper, the required result is obtained by using a principally different method of interpretation. In addition, this result is also capable of describing some more general theories of this kind — namely, the theories of finite subsets for arbitrary infinite groups, monoids, semigroups, and arbitrary groupoids of general kind. Another corollary of our results is that the classes of the mentioned algebras have theories that have no recursive axiomatization. An auxiliary result, which we also prove here, is a variant of the “downward” Löwenheim–Skolem theorem for arbitrary finite subset algebras. Finally, the results obtained can be used to establish that the theories of the subalgebra lattices are undecidable and have no recursive axiomatization if the entire Abelian groups has finite exponent. The same conclusion is also obtained for the theories of the subalgebra lattice class, where the original class can be the class of Abelian groups, of all groups, of monoids, or of semigroups. § 2. Definitions and basic propertiesAn arbitrary $n$-ary function $f$ on a set $A$ can be extended to arbitrary subsets of $A$ as follows:
$$
\begin{equation*}
f(X_1, \dots, X_n)=\{f(a_1, \dots, a_n)\colon a_1\in X_1, \dots, a_n\in X_n\}.
\end{equation*}
\notag
$$
In this case, it is clear that if the sets $X_1, \dots, X_n$ are finite, then so is the set $f(X_1, \dots, X_n)$. Definition 1. Let $\mathfrak{A}$ be an arbitrary algebra (that is, a structure in a language without relations). By $\exp\mathfrak{A}$, we will mean the algebra whose domain is the set of all finite non-empty subsets of $A$, and each function of the language is defined as above for these subsets. First, we note that if, in place of the algebra $\exp\mathfrak{A}$ of all finite subsets, we consider the algebra $\exp^\varnothing\mathfrak{A}$ of all finite non-empty subsets including the empty set, then the expressive power of the theory of the algebra $\exp^\varnothing\mathfrak{A}$ remains the same in interesting cases, because the empty set is definable by any binary operation, and the value of any function is empty whenever any argument of this function is empty. Lemma 1. Let the language of the algebra $\mathfrak{A}$ contain at least one function $f$ of arity $\geqslant 2$, then the empty set $\varnothing$ is definable in the algebra $\exp^\varnothing\mathfrak{A}$, Proof. From the definition it is immediate that $f(\varnothing, Y, \dots, Y)=\varnothing$.
On the other hand, if $f(X, Y, \dots, Y)\,{=}\,X$ for all $Y$, then $\varnothing\,{=}\,f(X, \varnothing, \dots, \varnothing)\,{=}\, X$ for $Y=\varnothing$, proving the lemma. It is clear that if an original function $f$ is a binary associative (respectively, commutative) operation in an algebra $\mathfrak{A}$, then its extension in the algebra $\exp\mathfrak{A}$ is also associative (respectively, commutative). So, if $\mathfrak{A}$ is a (commutative) semigroup, then $\exp\mathfrak{A}$ is also a (commutative) semigroup. We also note that the algebra $\exp\mathfrak{A}$ inherits the identity element from the algebra $\mathfrak{A}$ if this algebra has such an element. Lemma 2. Let “$+$” be an arbitrary binary operation in the algebra $\mathfrak{A}$ which has a (unique) identity element $0$. Then, in the algebra $\exp\mathfrak{A}$, we define the (unique) identity element $\{0\}$ for “$+$”, Vice versa, if in the algebra $\exp\mathfrak{A}$ for “$+$” there exists a (unique) identity element, then it is $\{0\}$, where $0$ is the identity element in $\mathfrak{A}$. Proof. For $\{0\}$, we have by definition (and, similarly, for another order of arguments). Another value for $X$ is impossible because the identity element is unique.
Now, let $X$ be the identity element in the algebra $\exp\mathfrak{A}$. If we suppose that $X$ contains at least two elements of $\mathfrak{A}$, that is, $X=\{a, b, \dots\}$, then, for $Y= \{a\}$, from the equality $\{a\}+X=\{a\}$, it follows that $a+b=a$. Similarly, for $Y= \{b\}$, from the equality $X+\{b\}=\{b\}$, we obtain $a+b=b$, thus, $a=b$. Therefore, $X$ contains exactly one element, which must be the identity element in $\mathfrak{A}$, because, in the algebra $\exp\mathfrak{A}$ the singletons form a subalgebra isomorphic to $\mathfrak{A}$. This proves the lemma. § 3. Definability in theories of finite figuresLet $\mathfrak{L}$ be an infinite linear space over a field of finite characteristic $p$, and $0$ be the identity element of $\mathfrak{L}$. Then $\mathfrak{L}$ is an infinite-dimensional linear space over the prime finite field $\operatorname{GF}(p)$. We will consider the algebra $\exp\mathfrak{L}$ of finite sets (figures) in the space $\mathfrak{L}$ with addition, and consider the theory of the algebra $\exp\mathfrak{L}$. Lemma 3. In the theory of the algebra $\exp\mathfrak{L}$, the property “to be a subspace of $\mathfrak{L}$ ” is definable, Proof. Recall that a subspace $X$ is an arbitrary subset of $\mathfrak{L}$ that is closed under addition and multiplication by elements of the field. In each prime finite field, every element is a multiple sum of the unity. Therefore, it is enough to require the first condition. This proves the lemma. For brevity, by uppercase letters in the middle of the alphabet $I, J, K, L, M, N, O$, possibly, with indices, we will denote subspaces of $\mathfrak{L}$, and so we will not write, for example, $\operatorname{Subspace}(L)$. The following lemmas follow immediately from the properties of linear subspaces. Lemma 4. In the theory of the algebra $\exp\mathfrak{L}$, the inclusion relation is definable for subspaces, Lemma 5. In the theory of the algebra $\exp\mathfrak{L}$, the intersection of subspaces is definable, Lemma 6. In the theory of the algebra $\exp\mathfrak{L}$, the class of one-dimensional subspaces is definable, A subspace is one-dimensional if and only if it is minimal among non-zero-dimensional subspaces. If two subspaces $L$ and $M$ have empty intersection (the only common point is the zero element), then their sum $L+M$ is direct; that is, every element of $L+M$ has a unique decomposition into the sum of elements from $L$ and $M$. We denote this relation by $\mathrel{\bot}$, Our further analysis depends primarily on formulas describing epimorphisms of linear subspaces in $\mathfrak{L}$,
$$
\begin{equation*}
\begin{aligned} \, \Phi_L(L, O, M) &\equiv (\forall\, L_1\subseteq L) (\operatorname{Dim}_1(L_1)\to (\exists\, O_1\subseteq O)(\operatorname{Dim}_1(O_1) \land O_1\subseteq L_1+M)); \\ \Phi_O(L, O, M) &\equiv (\forall\, O_1\subseteq O) (\operatorname{Dim}_1(O_1)\to (\exists\, L_1\subseteq L) (\operatorname{Dim}_1(L_1) \land O_1\subseteq L_1+M)); \\ \Phi_M(L, O, M) &\equiv (\forall\, M_1\subseteq M) (\operatorname{Dim}_1(M_1) \\ &\qquad\to (\exists\, O_1\subseteq O) (\operatorname{Dim}_1(O_1) \land O_1\mathrel{\bot} L\land O_1\subseteq L+M_1)). \end{aligned}
\end{equation*}
\notag
$$
Lemma 7. Given subspaces $L$, $O$, and $M$, the formula is true if and only if the subspaces $L$ and $M$ are non-intersecting and there exists an epimorphism $h\colon L\to M$ such that $O=\{x+h(x)\colon x\in L\}$. This epimorphism $h$ is uniquely defined from the subspaces $L$, $O$, $M$, and, vice versa, $L, O, M$ are uniquely defined from $h$. Proof. Let $\operatorname{Epi}(L, O, M)$ be true.
Consider an arbitrary vector $x\in L$, and find a vector $u\in O$ such that $u=x+z$ for some $z\in M$. We set $h(x)=z$. We first claim that such $u$ and $z$ do exist. Since $0+0\in O$, we have $h(0)=0$. For $x\neq 0$, consider the one-dimensional subspace $L_1=\langle x\rangle$ generated by $x$. We choose $O_1\subseteq O$ from the formula $\Phi_L$, and consider a non-zero $u'\in O_1$. We have $O_1\subseteq L_1+M$, and hence $u'=\alpha x+z'$ for some $\alpha\in \operatorname{GF}(p)$ and $z'\in M$. Since $O\mathrel{\bot} M$, we have $\alpha x\neq 0$, that is, $\alpha\neq 0$ and $u=x+z$ for $u=\alpha^{-1} u'\in O_1$, $z=\alpha^{-1} z'\in M$, the result required. Now we claim that $h(x)$ is uniquely defined. If $x+z_1, x+ z_2\in O$ and $z_1, z_2\in M$, then, for the difference, we have $(x+z_1)-(x+z_2)=z_1-z_2\in O\cap M$. But since $O\mathrel{\bot} M$, it follows that $z_1-z_2=0$ and $z_1=z_2$. We next need to show that $h$ is surjective. Consider a non-zero $z\in M$ and the one-dimensional subspace $M_1=\langle z\rangle$ generated by $z$. Let $O_1\subseteq O$ be a subspace from $\Phi_M$, and consider a non-zero vector $u'\in O_1$. We have $u'=x'+\alpha z$ for some $\alpha\in \operatorname{GF}(p)$ and $x'\in L$. Since $O_1\mathrel{\bot} L$, we have $\alpha z\neq 0$, $\alpha\neq 0$, and $u=x+z$ for $u=\alpha^{-1} u'\in O_1$ and $x=\alpha^{-1} x'\in L$. Therefore, $h(x)=z$. We now show that the function $h$ is linear. Since the field $\operatorname{GF}(p)$ is prime and finite, it is enough to prove that $h(x+y)=h(x)+h(y)$. From $x+h(x),y+h(y)\in O$, it follows that $(x+h(x))+(y+h(y))=(x+y)+(h(x)+h(y))\in O$, and hence $h(x+y)=h(x)+h(y)$. Now let $h\colon L\to M$ be an epimorphism, $L$ and $M$ be disjoint. We set $O=\{x+h(x)\colon x\in L\}$. Hence $L\mathrel{\bot} M$ and $O\mathrel{\bot} M$. This is indeed so, because from $z\in M\cap O$ we have $z=h(x)=y+h(y)$ for some $x, y\in L$. We next have $0=(y+h(y))-h(x)=y+h(y-x)$. But $h(y-x)\in M$ and $L\mathrel{\bot} M$. Hence $y=h(y-x)=0$ and $z=y+h(y)=0$. For each $L_1\subseteq L$, we take $O_1=\{x+h(x)\colon x\in L_1\}\subseteq L_1+M$. Hence $\Phi_L(L, O, M)$ is true. For each $M_1\subseteq M$, consider $x\in L$ such that $h(x)\in M_1$ and $h(x)\neq 0$. In this case, $M_1$ consists of all $\alpha h(x)$ for $\alpha\in\operatorname{GF}(p)$. Hence $O_1=\{\alpha(x+h(x))\colon \alpha\in\operatorname{GF}(p)\}\subseteq L+M_1$. Therefore, $\Phi_M(L, O, M)$ is true. If $O_1\subseteq O$ and $x+h(x)\in O_1$ for $x\in L$, $x\neq 0$, then $O_1$ consists of $\alpha (x+h(x))$ for $\alpha\in\operatorname{GF}(p)$. Hence $O_1\subseteq \langle x\rangle +M$, and $\Phi_O(L, O, M)$ is also true. The last thing we need to prove is that no other $O$ satisfies $\operatorname{Epi}(L, O, M)$. From the first part of the proof and the truth of $\operatorname{Epi}(L, O, M)$ it follows that $x+h(x)\in O$ for all $x\in L$. Consider any non-zero $u\in O$ and $O_1=\langle u\rangle$. Since $\Phi_O$ is true, we get $O_1\subseteq L_1+M$ for some $L_1\subseteq L$. This means that the subspace $O_1$ consists of $\alpha (x+z)$ for $\alpha\in\operatorname{GF}(p)$, where $x\in L_1$ and $z\in M$ are fixed. Thus, $u=\alpha x+\alpha z$ for $\alpha\neq 0$, and, for the vector $v=\alpha x+ h(\alpha x)\in O$, we have $u-v=\alpha z-h(\alpha x)\in M\cap O$. Since $O\mathrel{\bot} M$, we have $u-v=0$ and $u=v=\alpha x+h(\alpha x)$. Therefore, all elements of $O$ are of the form $x+h(x)$ for $x\in L$. This proves the lemma. Proof. If $h(x)=0$, then $x+h(x)=x\in L\cap O$. On the other hand, if $x\in L\cap O$, then $x=y+h(y)$ for some $y\in L$, hence $(x-y)-h(y)\in L$. Since $x-y\in L$, $h(y)\in M$, and $L\mathrel{\bot} M$, we have $h(y)=0$ and $x=y$, Therefore, $h(x)=0$. This proves the corollary. Under an additional condition we get an analogous formula for isomorphisms. Lemma 8. Given subspaces $L$, $O$, and $M$, the formula is true if and only if the subspaces $L$ and $M$ are non-intersecting, and there exists an isomorphism $h\colon L\leftrightarrow M$ such that $O=\{x+h(x)\colon x\in L\}$. This isomorphism $h$ is uniquely defined from $L, O, M$, and vice versa, $L, O, M$ are uniquely defined from $h$. Proof. All we need to add to the proof of Lemma 7 is that, for every $z\in M$, there exists at most one $x\in L$ such that $x+z\in O$. If $x_1+z, x_2+z\in O$, then $(x_1+z)-(x_2+z)=x_1-x_2\in O\cap L$. From $L\mathrel{\bot} O$, we get $x_1-x_2=0$ and $x_1=x_2$. This proves the lemma. Since our space $\mathfrak{L}$ is infinite-dimensional, and all considered subspaces are finite-dimensional, we can define arbitrary epimorphisms $h\colon L\to K$ of subspaces. For this purpose, we need to take a subspace $M$ that does not intersect both $L$ and $K$, an epimorphism $f\colon L\to M$, and an isomorphism $g\colon M\to K$ such that $h(x)=g(f(x))$. In what follows, we will identify the homomorphism $h\colon L\to K$ with the triple $h=(O_f, M, O_g)$. Of course, this triple is not unique, but we do not require this. Lemma 9. In the theory of the algebra $\exp \mathfrak{L}$, the formula says that $h=(O_f, M, O_g)$ is an epimorphism from a finite-dimensional subspace $L$ onto $K$. In this case, $\operatorname{ker} h = L\cap O_f$. Analogously, we can verify the existence of an isomorphism between two arbitrary subspaces, that is, they have the same dimension. Lemma 10. In the theory of the algebra $\exp \mathfrak{L}$, there exist the formula which means that finite-dimensional subspaces $L$ and $N$ have the same dimension. Note that if $h\colon L\to K$, $h=(O_f, M, O_g)$ is a homomorphism, then we can restrict it to corresponding subsets. It allows us to define an image of a subspace $J=h(I)\subseteq K$. Lemma 11. Let $h=(O_f, M, O_g)$ be an epimorphism from a subspace $L$ onto a subspace $K$. Then the formula is true in $\exp\mathfrak{L}$ if and only if $J\subseteq K$ is the image of $I\subseteq L$. Here, $h'=(O'_f, M', O'_g)$. Let us recall that an endomorphism of a subspace $L$ is nilpotent if there is a natural number $n$ such that $h^n(L)=\{0\}$. Lemma 12. In the theory of the algebra $\exp \mathfrak{L}$, there exists a formula which means that $h=(O_f, M, O_g)$ is a nilpotent endomorphism of a finite-dimensional subspace $L$. Proof. Consider the decreasing sequence of subspaces Since $L$ is finite-dimensional, we will eventually get $h^n(L)=h^{n+1}(L)$ for some $n$.
If $\operatorname{Nil}(L, h)$ holds, then $I=h^n(L)=\{0\}$ is immediate for $I=h^n(L)$. If $\operatorname{Nil}(L, h)$ is false, then $h(I)=I$ is true for some $I\neq\{0\}$. By induction on $m$, we can show that $I\subseteq h^m(L)$ for all natural $m$. Therefore, $h$ is not nilpotent. This proves the lemma. A subspace $I\subseteq L$ is called $h$-invariant for an endomorphism $h$ if $h(I)\subseteq I$. An $h$-invariant subspace $I\subseteq L$ is called $h$-cyclic if the subspace $I$ has a (cyclic) basis of the form $h^0(x)=x$, $h^1(x)$, $\dots$, $h^{n-1}(x)$ for some vector $x\in I$ and some natural $n$. In the case of a nilpotent endomorphism $h$, the condition $h^{n}(x)=0$ is satisfied automatically (see [13]). Lemma 13. In the theory of the algebra $\exp \mathfrak{L}$, there exists the formula Proof. The first part of the formula says that $h$ is a nilpotent endomorphism and $I$ is an $h$-invariant subspace.
Suppose that the implication is true. This implication means that, under the action of $h$, the dimension of any $h$-invariant subspace $J\subseteq I$, $J\ne \{0\}$, is decreased by one. Thus, in the sequence of subspaces
$$
\begin{equation*}
I\supsetneqq h(I)\supsetneqq h^2(I)\supsetneqq\cdots\supsetneqq h^n(I)=\{0\}
\end{equation*}
\notag
$$
the dimension of each subspace is one less than that of the previous subspace. As a result, the dimension of $I$ is $n$. Consider an arbitrary vector $x\in I\setminus h(I)$. By induction, it is easy to show that $ h^m(x)\in h^{m}(I)\setminus h^{m+1}(I)$ for $m=0, \dots, n-1$. Thus, the vectors $ h^0(x)=x$, $ h^1(x)$, $\dots$, $ h^{n-1}(x)$ form an $h$-cyclic basis.
Conversely, let $I$ be an $h$-cyclic subspace. Then, given some $h$-cyclic basis $e_n= h^0(x)=x$, $e_{n-1}= h^1(x)$, $\dots$, $e_1= h^{n-1}(x)$, the $I$-restriction of the endomorphism $h$ is represented by the matrix which has the form of a cyclic cell:
$$
\begin{equation}
\begin{pmatrix} 0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\ \end{pmatrix}.
\end{equation}
\tag{3.1}
$$
In this case, any $h$-invariant subspace $J$ has a basis $e_1, \dots, e_m$ for some $m$. Indeed, in $J$ we take $x=\sum_{i=1}^m \alpha_i e_i$, $\alpha_m\neq 0$, and let $m$ be the largest among all such $x$. Then $ h^j(x)=\sum_{i=j+1}^m \alpha_i e_{i-j}\in J$. By the backward induction on $j$, we see that all $e_1, \dots, e_m$ belong to $J$. Hence they form a basis for $J$.
Therefore, $ h(J)$ has the basis $e_1, \dots, e_{m-1}$, that is, the dimension of $ h(J)$ is one less than that of $J$. This proves the lemma. Lemma 14. In the theory of the algebra $\exp \mathfrak{L}$, there exists the formula which means that, given a nilpotent endomorphism $h$ of a finite-dimensional subspace $L$, the subspace $I\subseteq L$ is a maximal $h$-cyclic subspace. We finally recall (see [13]) that each finite-dimension space equipped with an endomorphism can be decomposed into the direct sum of maximal cyclic subspaces. The dimensions of these subspaces are defined uniquely by the endomorphism, and the subspaces correspond to cyclic cells of the endomorphism matrix in a suitable basis. § 4. Algorithmic properties of finite figure theoryNow we have all the ingredients to prove results on the undecidability degree of the theory of the algebra $\exp\mathfrak{L}$. The main task here is to define the squaring of natural numbers. Lemma 15. In the theory of the algebra $\exp \mathfrak{L}$, there is a formula $\operatorname{Square}(L, K)$, which means that, given finite-dimension subspaces $L$ and $K$, the dimension of $L$ is the squared dimension of $K$. Proof. Let a formula $\operatorname{Square}(L, K)$ say that
(i) on the subspace $L$, there exists a nilpotent endomorphism $h$: $\operatorname{Nil}(L, h)$; (ii) each maximal $h$-cyclic subspaces of $L$ has the same dimension as $K$, that is, $(\forall\, N)(\operatorname{Max}(L, h, N)\to \operatorname{EqDim}(N, K))$; (iii) the kernel $J=\operatorname{ker} h$ of the endomorphism $h$ has the same dimension as $K$: $(\exists\, J)(\operatorname{ker} h=J\land \operatorname{EqDim}(J, K))$. We claim that the formula $\operatorname{Square}(L, K)$ is true if and only if the dimension of $L$ is the squared dimension of $K$. Let the formula $\operatorname{Square}(L, K)$ be true, and the subspace $K$ be $n$-dimensional. We can decompose the subspace $L$ into the direct sum of maximal $h$-cyclic subspaces: $L=N_1\oplus \dots\oplus N_m$. By (ii), the dimensions of each of these subspaces is $n$. Note that each intersection of $N_i$ with the kernel $J$ of $h$ is one-dimensional. Indeed, since $h(J)=\{0\}$, we have $h(N_i\cap J)=\{0\}$. Hence $N_i\cap J$ is an $h$-invariant subspace of $N_i$. But if we consider the endomorphism $h$ on the $h$-cyclic subspace $N_i$ and take any $h$-invariant subspace of $N_i$, except $\{0\}$, then the image of this subspace is one less than that of the subspace itself (Lemma 13). So, if $h(N_i\cap J)$ is zero-dimensional, then the subspace $N_i\cap J$ is either zero- or one-dimensional. If we suppose that $N_i\cap J=\{0\}$, then $J$ is not a kernel of $h$, that is, in $N_i$ there exists a vector $x\neq 0$ such that $h(x)=0$, and we can add this $x$ to $J$. Therefore, $N_i\cap J$ is one-dimensional, $m=n$, and so the dimension of $L$ is $n^2$. Conversely, let $L$ be $n^2$-dimensional, and $K$ be $n$-dimensional. The subspace $L$ can be represented as the direct sum $N_1\oplus \dots\oplus N_n$ of $n$-dimensional subspaces $N_i$. Consider an endomorphism $h$ that on each $N_i$ is defined by the cyclic cell (3.1). Hence $h$ is nilpotent, and each maximal $h$-cyclic subspace is $n$-dimensional. The kernel of $h$ is the direct sum of the corresponding one-dimensional subspaces of $J_i\subseteq N_i$, and so the kernel is also $n$-dimensional. Therefore, the formula $\operatorname{Square}(L, K)$ is true. This proves the lemma. Theorem 1. In the theory of the algebra $\exp\mathfrak{L}$, the first-order arithmetic can be interpreted. Proof. Let us define an interpretation $\iota$ as follows. The domain of the interpretation $\iota$ is the set of all finite subspaces, so it is defined by the formula $\operatorname{Subspace}$. Any natural number $n$ is interpreted by an $n$-dimensional subspace. To interpret the first-order arithmetic, it is enough to interpret the equality relation and the addition and squaring operations on the domain.
The equality is defined by the formula $\operatorname{EqDim}$, that is, $\iota(a=b)$ is $\operatorname{EqDim}(a, b)$. The addition is interpreted as the direct sum of subspaces, because, in this case, the dimensions are added: $\iota(a+b=c)$ is
$$
\begin{equation*}
(\exists\, a', b')(a'\mathrel{\bot} b'\land \operatorname{EqDim}(a, a')\land \operatorname{EqDim}(b, b')\land c=a'+b').
\end{equation*}
\notag
$$
And finally, to interpret the squaring of numbers, we defined the formula $\operatorname{Square}$, that is, $\iota(a^2=c)$ is $\operatorname{Square}(c, a)$. This proves the theorem. So, we have a lower bound for the degree of undecidability for the theory of the algebra $\exp\mathfrak{L}$. Now let us show that the upper bound is the same. Theorem 2. Let $\mathfrak{L}$ be a countable linear space over a prime finite field $\operatorname{GF}(p)$. Then the theory of the algebra $\exp\mathfrak{L}$ can be interpreted in the first-order arithmetic. Proof. Let $\mathfrak{L}$ be a countable linear space over a prime finite field $\operatorname{GF}(p)$, and $\varepsilon=\{e_i\colon i\in\omega\}$ be its countable basis. Each vector $x\in\mathfrak{L}$ can be expanded in the basis $\varepsilon$, that is, $x=\sum_i \alpha_i e_i$, where only finitely many coefficients $\alpha_i$ are non-zero (this observation is important for us). The coefficients $\alpha_i$ can be considered as digits of the base-$p$ numeral system, and so the tuple of $\alpha_i$ corresponds to the base-$p$ representation of some natural number $t_x$. This mapping between vectors $x$ and natural numbers $t_x$ is one-one. In this case, the addition of vectors $x+y$ corresponds to the digit-wise addition of the base-$p$ representations of $t_x$ and $t_y$. The last operation can be defined in the first-order arithmetic; we denote it by $+_p$.
To encode finite subsets of vectors, we can use the canonical numeration of finite subsets of natural numbers, for example. In this case, the numerical code of a finite set $S$ of vectors is For this numeration, it is well known that the relation $x\in S$ can be expressed in the first-order arithmetic by some formula $\operatorname{In}(t_x, N_S)$. Hence the addition of finite subsets $A+B=C$ in $\exp \mathfrak{L}$ can be interpreted by the arithmetical formula This proves the theorem.In Theorem 2, it is possible to omit the countability condition of $\mathfrak{L}$. The theory of the algebra $\exp\mathfrak{L}$ is not countably categorical, unlike the theory of the linear space $\mathfrak{L}$ itself. This means that the “downward” Löwenheim–Skolem theorem cannot be used immediately because a countable elementary substructure of $\exp\mathfrak{L}$ may be not of the form $\exp\mathfrak{L}_0$ for any space $\mathfrak{L}_0$. Therefore, to continue, we need a special variant of the Löwenheim–Skolem theorem. Theorem 3. If $\mathfrak{A}$ is an infinite algebra with countable language $\Sigma$, then there exists a countable elementary subalgebra $\mathfrak{C}\prec \mathfrak{A}$ such that the (countable) subalgebra $\exp\mathfrak{C}$ is also elementary, that is, $\exp\mathfrak{C}\prec \exp\mathfrak{A}$. Proof. We expand the algebra $\exp\mathfrak{A}$ to the structure $\exp'\mathfrak{A}$ by using the binary relation $E$. For this relation, $E(x, Y)$ is true if and only if $x$ is a singleton and $x$ is a subset of $Y$.
So, the formula $D(x)\equiv E(x, x)$ distinguishes in $\exp'\mathfrak{A}$ the substructure $\mathfrak{D}'$ of all singletons. Hence if the algebra $\mathfrak{D}$ is the restriction of $\mathfrak{D}'$ to the original language $\Sigma$, then $\mathfrak{D}$ is isomorphic to $\mathfrak{A}$. We also note that, for all $Y, Y'\in \exp'\mathfrak{A}$, the equality $Y=Y'$ holds if and only if $E(x, Y)$ is equivalent to $E(x, Y')$ for each $x$ such that $D(x)$ is true. By the Löwenheim–Skolem theorem, there exists a countable elementary substructure $\exp'_0\mathfrak{A}$ of $\exp'\mathfrak{A}$. By elementarity, the formula $D(x)$ distinguishes some substructure $\mathfrak{D}'_0$ of $\exp'_0\mathfrak{A}$, and if $\mathfrak{D}_0$ is the restriction of $\mathfrak{D}'_0$ to the original language $\Sigma$, then $\mathfrak{D}_0$ is an elementary subalgebra of $\mathfrak{D}$. Thus, $\mathfrak{D}_0$ is isomorphic to some countable elementary subalgebra $\mathfrak{C}\prec\mathfrak{A}$. This algebra $\mathfrak{C}$ consists of $a$’s such that $\{a\}\in\mathfrak{D}_0$. It is remain to prove that the algebra $\exp\mathfrak{C}$ is equal to $\exp_0\mathfrak{A}$, where $\exp_0\mathfrak{A}$ is the restriction of $\exp'_0\mathfrak{A}$ to the language $\Sigma$. To this end, we consider the formula $\operatorname{Frechet}$ that says that: (i) there exists a unique $Z$ such that $E(X, Z)$ is false for all $X$,
$$
\begin{equation*}
(\exists\, Z)((\forall\, X)\lnot E(X, Z)\land (\forall\, Z')((\forall\, X)\lnot E(X, Z')\to Z'=Z));
\end{equation*}
\notag
$$
(ii) for each $Y$ and each $x$ for which $D(x)$ is true, there exists $U$ such that the formula $E(V, U)$ holds if and only if either $V=x$ or $E(V, Y)$ holds,
$$
\begin{equation*}
(\forall\, Y, x)(D(x)\to (\exists\, U)(\forall\, V)(E(V, U)\leftrightarrow (V=x\lor E(V, Y)))).
\end{equation*}
\notag
$$
In other words, the formula $\operatorname{Frechet}$ says that there exists a (unique) empty set, and we can augment each arbitrary set $Y$ with an arbitrary element $x$. Evidently, in the structure $\exp'\mathfrak{A}$, the formula $\operatorname{Frechet}$ is true, and hence this is true in the elementary substructure $\exp'_0\mathfrak{A}$. By induction on $n$, from the formula $\operatorname{Frechet}$, it follows that $\exp'_0\mathfrak{A}$ contains all $n$-element subsets of $\mathfrak{C}$. Hence $\exp\mathfrak{C}\subseteq \exp_0\mathfrak{A}$. Now let us assume that $\exp\mathfrak{C}\neq \exp_0\mathfrak{A}$. Hence $\exp'_0\mathfrak{A}$ contains some $Y$ such that $Y$ is not a finite subset of $\mathfrak{C}$. Since the structure $\exp'_0\mathfrak{A}$ is a substructure of $\exp'\mathfrak{A}$ consisting of finite subsets of $\mathfrak{A}\supseteq\mathfrak{C}$, it follows that $Y$ contains some element $x\in\mathfrak{A}\setminus\mathfrak{C}$. Hence the structure $\exp'_0\mathfrak{A}$ satisfies the formula that says that there exist unequal $Y$ and $Y'$ such that, for all $x$, for which $D(x)$ is true, $E(x, Y)$ holds if and only if $E(x, Y')$ holds. An instance of such $Y'$ is the intersection of $Y$ with $\mathfrak{C}$. So, this formula is true in $\exp'\mathfrak{A}$, but this is impossible. Therefore, $\exp\mathfrak{C}=\exp_0\mathfrak{A}\prec\exp\mathfrak{A}$. This proves the theorem. Corollary 2. Let $\mathfrak{L}$ be an infinite linear space over a prime finite field $\operatorname{GF}(p)$. Then the theory of the algebra $\exp\mathfrak{L}$ can be interpreted in the first-order arithmetic. Proof. We take a countable infinite subspace $\mathfrak{L}_0$ of the space $\mathfrak{L}$ such that $\mathfrak{L}_0\prec\mathfrak{L}$ and $\exp\mathfrak{L}_0\prec\exp\mathfrak{L}$. The theories of the algebras $\exp\mathfrak{L}_0$ and $\exp\mathfrak{L}$ are equal, and the first one can be interpreted in the first-order arithmetic. This proves the corollary. Corollary 3. Let $\mathfrak{L}$ be an infinite linear space over a prime finite field $\operatorname{GF}(p)$. Then the theory of the algebra $\exp\mathfrak{L}$ is algorithmically equivalent to the first-order arithmetic. § 5. Abelian groups of finite exponent and other algebrasWe now employ the results for linear spaces from the previous section for algebras of a more general kind. Let us recall that the exponent of an additive group is the least positive number $m$ such that $ma=0$ for all group elements. Here, we use the standard notation $ma$ for the multiple sum: $a+\dots+a$ ($m$ times). Lemma 16. Let $\mathfrak{A}$ be an arbitrary group. In the theory of the algebra $\exp\mathfrak{A}$, singletons $\{x\}$ can be distinguished; they are exactly the invertible elements of the algebra $\exp\mathfrak{A}$, Proof. For $\{a\}$, the inverse element is $\{-a\}$. If $a\neq b$, then any set of the form $\{a, b, \dots\}$ has no inverse element: $\{a, b, \dots\}+\{c, \dots\}=\{a+c, b+c, \dots\}\neq \{0\}$, because $a+c\neq b+c$. This proves the lemma. Theorem 4. Let $\mathfrak{A}$ be an infinite Abelian group of finite exponent $m$. Then (i) $\mathfrak{A}$ contains a subalgebra $\mathfrak{L}$, which is an infinite-dimensional linear space over some prime finite field $\operatorname{GF}(p)$; (ii) the set $\exp\mathfrak{L}$ is definable in the theory of $\exp\mathfrak{A}$. Proof. By the Prüfer theorems (see [14]), the infinite Abelian group $\mathfrak{A}$ of finite exponent contains an infinite $p$-subgroup for some prime $p$. Further, this subgroup can be decomposed into the direct sum of an infinite amount of cyclic $p$-subgroups. Every cyclic $p$-subgroup has an element of order $p$. Thus, in the group $\mathfrak{A}$, there are infinitely many elements of order $p$. These elements, together with zero, form the linear space $\mathfrak{L}$ over the field $\operatorname{GF}(p)$. So, we have only to define $\exp\mathfrak{L}$ in the system $\exp\mathfrak{A}$.
For each finite set $X\in\exp\mathfrak{A}$, we can define the subgroup $\langle X\rangle$ generated by $X$. This subgroup is also a finite set, because the exponent is finite,
$$
\begin{equation*}
\langle X\rangle = Y\equiv Y+Y=Y\land X+Y=Y\land (\forall\, Z)(X+Z=Z\to Y+Z=Z).
\end{equation*}
\notag
$$
Here, the formula $Y+Y=Y$ means that $Y$ is a subgroup; the formula $X+Y=Y$ means that $X\subseteq Y$; and the last part of the formula means that $Y$ is the least among such subgroups.
As above, $\{0\}$ is the (unique) identity element of $\exp\mathfrak{A}$ and is definable in a similar way. Recall that all non-identity elements of the subgroup $Y=\langle X\rangle$ are of order $p$ if and only if so are all non-identity elements of $X$ itself. The elements of $\exp\mathfrak{L}$ (that is, finite subsets of $\mathfrak{A}$ which consist of elements of order $p$) can be distinguished by the formula This proves the theorem.As a corollary we find that the theory of the algebra $\exp\mathfrak{A}$ is algorithmically equivalent to the first-order arithmetic. Theorem 5. Let $\mathfrak{A}$ be an infinite Abelian group of finite exponent $m$. Then the theory of the algebra $\exp\mathfrak{A}$ is algorithmically equivalent to the first-order arithmetic. Proof. From Theorems 4 and 1, it follows that the first-order arithmetic can be interpreted in the theory of $\exp\mathfrak{A}$.
To prove the converse result, we note that by Theorem 3 it is enough to prove this claim for countable groups only. Recall that by the Prüfer theorems (see [14]) the group $\mathfrak{A}$ can be decomposed into the direct sum of cyclic groups, whose orders are divisors of $m$. Combining these direct summands in a suitable way, we obtain $\mathfrak{A}\,{=}\,\mathfrak{A}_1\oplus\dots\oplus\mathfrak{A}_\ell$, where $\mathfrak{A}_i$ is the direct sum of cyclic groups of some fixed order $m_i$. As in the proof of Theorem 2, every $x_i\in \mathfrak{A}_i$ can be encoded by a natural number $t_{x_i}$ in the base-$m_i$ numeral system. Thus, each element $x\in\mathfrak{A}$, $x=x_1+\dots+x_\ell$, can be uniquely encoded by the tuple $(t_{x_1}, \dots, t_{x_\ell})$. We next use some one-one encoding of $\ell$-tuples in the first-order arithmetic $\nu\colon\omega^\ell\to \omega$; so $x$ is encoded by the natural number $s_x=\nu(t_{x_1}, \dots, t_{x_\ell})$. The further argument proceeds as in the proof of Theorem 2, where instead of adding digits from the individual numbers, we add digits from the elements of tuples: $x+y$ corresponds to where $\nu_i$ is the inverse function to $\nu$, which, given the number of a tuple, returns the $i$th element of this tuple. This proves the theorem.Using the results of [11] and [12], we have the following comprehensive theorem on Abelian groups. Theorem 6. Let $\mathfrak{A}$ be an arbitrary infinite Abelian group. Then the theory of the algebra $\exp\mathfrak{A}$ admits an interpretation of the first-order arithmetic. Proof. If $\mathfrak{A}$ has an element of infinite order, then we use Corollary 16 in [11]. If, in the torsion group $\mathfrak{A}$, there are elements of arbitrarily large orders, then we use Theorem 1 in [12]. If the orders of elements in $\mathfrak{A}$ are limited, we use the previous theorem. This proves Theorem 6. Recall that, for an arbitrary Abelian group $\mathfrak{A}$, the upper bound from Theorem 5 can be incorrect, because the theory of the original group $\mathfrak{A}$ can have a higher degree of undecidability than the first-order arithmetic. We can use the previous theorems to prove another result on the theories of classes, which consist of algebras of the kind $\exp\mathfrak{A}$. This is possible because the class of linear spaces over a fixed prime finite field can be described by finitely many formulas. Definition 2. Let $K$ be any class of algebras. By $\exp K$ we denote the class of all algebras of the form $\exp\mathfrak{A}$ for $\mathfrak{A}\in K$. Let us establish some properties of the algebra $\exp\mathfrak{A}$, where $\mathfrak{A}$ is an arbitrary commutative monoid. Note that, in this case, the set $\{0\}$ is again the identity element of the algebra $\exp\mathfrak{A}$, and it is definable by Lemma 2. We continue to use “$+$” for the binary operation. Lemma 17. Let $\mathfrak{A}$ be an arbitrary commutative monoid. Then the formula holds in $\exp\mathfrak{A}$ if and only if $X=\{a\}$, $Y=\{0, a\}$ for some $a\in \mathfrak{A}$ such that $a\neq 0$, $a+a=0$. Proof. If $X=\{a\}$, $Y=\{0, a\}$ for such an $a$, then the formula $\operatorname{Pair}(X, Y)$ is clearly true. The last implication holds, because
Conversely, let the formula $\operatorname{Pair}(X, Y)$ be true. If we assume that $X$ contains at least two elements $X=\{a, a', \dots\}$, then $X+X=\{0\}$ means that $a+a=0=a'+a$. If we add $a$ to the last equality, then we have Hence $X$ contains exactly one element $a$, and we have $a+a=0$, $a\neq 0$.Next, for $Z=\{0, a\}$, we have $X+Z=Z$ and $Z+Z=Z$. The last implication implies that $Y+Z=Z$. Since $0\in Z$, we have $Y\subseteq Y+Z$ and $Y\subseteq \{0, a\}$. The equality $X+Y=Y$ is not satisfied in the cases $Y=\{0\}$, $Y=\{a\}$, the empty set is excluded (see Lemma 1), and, therefore, $Y= \{0, a\}$. This proves the lemma. Lemma 18. Let $\mathfrak{A}$ be an arbitrary commutative monoid. Then the formula holds in $\exp\mathfrak{A}$ if and only if the monoid $\mathfrak{A}$ is an Abelian group of exponent $2$. Proof. Let $\mathfrak{A}$ be an Abelian group of exponent $2$. Then every finite subset $X\subseteq\mathfrak{A}$ can be extended to a finite subgroup $U$. Further, $V+V=V$ implies that $V$ is a finite subgroup of the same exponent. It is well known (see [15]) that if $V\neq\{0\}$, then such a group $V$ can be decomposed into the direct sum of a cyclic subgroup $Y$ of order 2 and another subgroup $Z$, where $Z$ can be trivial.
Now, let $\exp\mathfrak{A}$ satisfy the formula $\Phi_2$. We choose an arbitrary singleton $X$, and construct $U=Z_0$ from the first line of $\Phi_2$. Let $V=Z_0$. Then $Z_0=Y_1+Z_1$, where $Y_1$ and $Z_1$ are values of variables $Y$ and $Z$, respectively, in the second line of $\Phi_2$. In this case, $Y_1$ is a cyclic group of order 2 by the previous lemma. For $V=Z_1$, the same argument shows that $Z_1=Y_2+Z_2$; for $V=Z_2$, we obtain $Z_2=Y_3+Z_3$, etc. Since every $Y_i$ contains 0, we have $Y_i+Z_i\supseteq Z_i$; hence, $Z_i\subseteq Z_{i-1}$ and $Z_i\neq Z_{i-1}$. Thus, $Z_i$, $i=0, 1, 2, \dots$, form a properly decreasing sequence, which cannot be infinite due by the finiteness of $Z_0$. This implies that we eventually have $Z_{m}=\{0\}$ and $Z_0=Y_1+\dots+Y_{m}$ for some $m$. Each of the subgroups $Y_1, \dots, Y_m$ is of order 2. Therefore, $U=Z_0$ is a group of exponent 2. As $0\in U$, we have $X+U\supseteq X$. Therefore, the unique element of the singleton $X$ is either the identity element or is of order 2. This proves the lemma. Theorem 7. Let $K$ be the class $\mathrm{Ab}$ of all Abelian groups (the class $\mathrm{Gr}$ of all groups, the class $\mathrm{Mn}$ of all monoids, the class $\mathrm{Sg}$ of all semigroups, the class $\mathrm{Gd}$ of all groupoids, respectively). Then the first-order arithmetic can be algorithmically reduced to the theory of the class $\exp K$. Proof. Let $\mathfrak{A}_2$ be an infinite Abelian group of exponent 2, that is, an infinite-dimensional linear space over the prime finite field $\operatorname{GF}(2)$. Hence, by Theorem 1, the theory of the algebra $\exp\mathfrak{A}_2$ admits an interpretation of the first-order arithmetic.
Consider the class of all Abelian groups $\mathrm{Ab}$. The theory of $\exp\mathfrak{A}_2$ is the set of all consequences of the formula $\Phi_2$ (see Lemma 18) in the theory of $\exp \mathrm{Ab}$. In other words, the theory of $\exp\mathfrak{A}_2$ is reduced to the theory of $\exp \mathrm{Ab}$ by the function $f(\Psi)=(\Phi_2\to\Psi)$. Consider the class of all groups $\mathrm{Gr}$. In this case, the theory of the class $\exp \mathrm{Ab}$ is the set of all consequences of the following formula in the theory of the class $\exp \mathrm{Gr}$; the formula $\Phi_c$ describes the commutativity. Hence the function $f(\Psi)=(\Phi_c\to\Psi)$ reduces the theory of $\exp \mathrm{Ab}$ to the theory of $\exp \mathrm{Gr}$.To distinguish algebras of the form $\exp \mathfrak{A}_2$ in the class $\exp \mathrm{Mn}$, it is enough (this follows from Lemma 18) to use the conjunction $\Phi_c\land\Phi_2$. So, the function $f(\Psi)=((\Phi_c\land\Phi_2)\to\Psi)$ reduces the theory of $\exp \mathfrak{A}_2$ to the theory of $\exp \mathrm{Mn}$. In the class $\exp \mathrm{Sg}$, we can distinguish the class $\exp \mathrm{Mn}$ by the existence of the identity element (see Lemma 2):
$$
\begin{equation*}
\Phi_z\equiv (\exists\, Z)(\forall\, X)(X+Z=X\land Z+X=X).
\end{equation*}
\notag
$$
Correspondingly, to reduce the theory of $\exp \mathrm{Mn}$ to the theory of $\exp \mathrm{Sg}$, the function $f(\Psi)=(\Phi_z\to\Psi)$ can be used.
And finally, in the class $\exp \mathrm{Gd}$, the class $\exp \mathrm{Sg}$ can be distinguished by the associativity formula
$$
\begin{equation*}
\Phi_a=(\forall\, X)(\forall\, Y)(\forall\, Z)(X+Y)+Z=X+(Y+Z).
\end{equation*}
\notag
$$
This means that the theory of $\exp \mathrm{Sg}$ can be reduced to the theory of $\exp \mathrm{Gd}$ by the function $f(\Psi)=(\Phi_a\to\Psi)$. Theorem 7 is proved. The next result is also a corollary to the above results. Theorem 8. Let $K$ be the class $\mathrm{Ab}$ of all Abelian groups (the class $\mathrm{Gr}$ of all groups, the class $\mathrm{Mn}$ of all monoids, the class $\mathrm{Sg}$ of all semigroups, the class $\mathrm{Gd}$ of all groupoids, respectively). Then the theory of the class $\exp K$ has no recurvice axiomatization. Proof. If a theory is recursive axiomatizable, then it is recursive enumerable itself. But the theory of $\exp K$ allows interpreting the first-order arithmetic; such a theory is not recursive enumerable (see [16]). This proves the theorem.
§ 6. Lattices of associative subalgebrasRecall that, for any algebra $\mathfrak{A}$, its subalgebras form the lattice with operations $\operatorname{inf}(\mathfrak{B}, \mathfrak{C})=\mathfrak{B}\cap\mathfrak{C}$ and $\operatorname{sup}(\mathfrak{B}, \mathfrak{C})=\langle\mathfrak{B}, \mathfrak{C}\rangle$. Let us denote this lattice by $\operatorname{lat}\mathfrak{A}$. Here, $\langle\mathfrak{B}, \mathfrak{C}\rangle$ is the subalgebra generated by all elements of $\mathfrak{B}$ and $\mathfrak{C}$. For example, for additive Abelian groups (and, consequently, for linear spaces), this subalgebra is the usual sum, $\operatorname{sup}(\mathfrak{B}, \mathfrak{C})=\mathfrak{B}+\mathfrak{C}$. Note that, given an infinite linear space $\mathfrak{L}$ over a field of finite characteristic, we use only finite subspaces of $\mathfrak{L}$ when we construct the interpretation of the first-order arithmetic in the theory of $\exp\mathfrak{L}$ (see Theorem 1 and the preceding lemmas). To define the identity element in $\exp\mathfrak{L}$ (see Lemma 2), for values of $Y$, it is enough to use only finite subspaces too because there is $\{0\}$ among them. So, we have the following result. Theorem 9. Let $\mathfrak{L}$ be an infinite linear space over a prime finite field. Then the theory of the lattice of finite subspaces admits an interpretation of the first-order arithmetic. To generalize the last theorem to the theory of all subspaces, it is enough to distinguish finite subspaces from all others. Theorem 10. Let $\mathfrak{L}$ be an infinite linear space over a prime finite field. Then the first-order arithmetic can be interpreted in the theory $\operatorname{lat}\mathfrak{L}$ of the lattice of finite subspaces of $\mathfrak{L}$. Proof. Note that, in the formulas that define homomorphisms for linear subspaces of $\mathfrak{L}$ (see Lemmas 7 and 8), the finiteness of subspaces is never used. Thus, the formulas from these lemmas remain correct for arbitrary subspaces. Hence, we can define the infiniteness of a subspace $L$ by the formula $\operatorname{Infin}(L)$, which says the following:
(i) in $L$ there are pairwise disjoint subspaces $I, J, K$, $K\neq\{0\}$, such that $I\mathrel{\bot} J$, $I\mathrel{\bot} K$, $K\mathrel{\bot} J$, $K\neq \{0\}$; (ii) $I$ is isomorphic to both $J$ and $J+K$, that is, $\operatorname{Iso}(I, J)$, $\operatorname{Iso}(I, J+K)$. It is clear that this is not so for finite, and, therefore, for finite-dimensional subspaces: if $K\neq\{0\}$ does not intersect $J$, then $J$ and $K+J$ are not isomorphic. And, vice versa, if $L$ is infinite (and infinite-dimensional), then we can take three pairwise disjoint subspaces: countable-infinite-dimensional $I$ and $J$, and one-dimensional $K$. In this case, $I$ is isomorphic to both $J$ and $J+K$. Therefore, the formula $\lnot \operatorname{Infin}(L)$ distinguishes finite subspaces from other ones, and these subspaces can be used to interpret the first-order arithmetic. This proves the theorem. Like the results of the previous section, this theorem can be carried over to arbitrary Abelian groups of finite exponent. Theorem 11. If $\mathfrak{A}$ is an Abelian group of finite exponent, then the first-order arithmetic can be interpreted in the lattice of finite subgroups /all subgroups of $\mathfrak{A}$. Proof. As already noticed in the proof of Theorem 4, in the Abelian group $\mathfrak{A}$ there exists an infinite subgroup $\mathfrak{L}$ of exponent $p$ for some prime $p$. This subgroup $\mathfrak{L}$ is a linear space over the prime finite field $\operatorname{GF}(p)$. The subgroups of $\mathfrak{L}$ also have the exponent $p$, and so it is enough to distinguish such subgroups among all subgroups of $\mathfrak{A}$.
Each Abelian group $L$ of exponent $p$ is the direct sum of subgroups of the form $\mathbb{Z} _p$. Let us fix such a subgroup $L_0$. Then all other such subgroups $L$ can be distinguished by the formula $\operatorname{Sum}(L, L_0)$, that says that each subgroup $K\subseteq L+L_0$ of length of at least 2 has at least three proper non-trivial subgroups. Recall that the length $n$ of an algebra $\mathfrak{B}$ is the greatest length of a decreasing subalgebra sequence $\mathfrak{B}_0\supsetneqq \mathfrak{B}_1\supsetneqq \mathfrak{B}_2\supsetneqq\cdots \supsetneqq \mathfrak{B}_n$. For the direct sums of at least two subgroups of the form $\mathbb{Z} _p$, the formula $\operatorname{Sum}(L, L_0)$ is true trivially: there are at least three proper non-trivial subgroups, they are generated by $(1, 0)$, $(1, 1)$, and $(0, 1)$, respectively. Conversely, if $L$ is not the direct sum of $\mathbb{Z} _p$, then two cases are possible. In the first case, $L$ is not a $p$-subgroup. In this case, $L$ includes a subgroup of the form $\mathbb{Z} _q$ for some prime $q\neq p$. Hence $\mathbb{Z} _q+L_0\subseteq L+L_0$ has only two proper non-trivial subgroups. In the second case, $L$ is a $p$-subgroup, and hence it has a subgroup of the form $\mathbb{Z} _{p^2}$. But the group $\mathbb{Z} _{p^2}$ contains only one proper non-trivial subgroup. Therefore, in both cases, the formula $\operatorname{Sum}(L, L_0)$ is false. So, it remains to show how to distinguish a suitable $L_0$. If $m$ is the exponent of our group, then, for any prime divisor $q$ of $m$, the amount of $q$-subgroups is infinite or is equal to some $M_q$. Let $M$ be the greatest of all such $M_q$. Hence, to find a suitable $L_0$, it is enough to require that the number of $L$’s satisfying $\operatorname{Sum}(L, L_0)$ should not exceed $M$. Therefore, we proved that the formula $\operatorname{Sum}$ distinguishes the subspaces of $\mathfrak{L}$ among all/finite subgroups of $\mathfrak{A}$. So, by Theorem 10, we can interpret the first-order arithmetic. This proves the theorem. In contrast to the results of § 5 (Theorem 6), Theorem 11 cannot be be generalized to arbitrary Abelian groups. Example 1. The additive Abelian group $\mathbb{Z} $ of integer numbers has an element of infinite order. Its subgroups are of the form $k\mathbb{Z} $, the lattice $\operatorname{lat}\mathbb{Z} $ of these groups is isomorphic to the set of natural numbers with the least common multiple operations for $\operatorname{inf}$ and the greatest common divisor operations for $\operatorname{sup}$ for corresponding $k$. The theory for this algebra is a part of the Skolem arithmetic, and hence is algorithmically decidable (see [1]). The Abelian group of all roots of unity has elements of arbitrarily large finite order. The finite subgroups of this group consist of all $k$th roots of unity, and their lattice is isomorphic to the same set of natural numbers with lcm and gcd operations for the corresponding $k$. Therefore, in this case, the theory of the lattice of finite subgroups is also decidable. The last thing we consider is the class of subalgebra lattices. Definition 3. Let $K$ be an arbitrary class of algebras. By $\operatorname{lat} K$ we denote the class of all lattices of the form $\operatorname{lat}\mathfrak{A}$, $\mathfrak{A}\in K$. Theorem 12. Let $K$ be the class $\mathrm{Ab}$ of all Abelian groups (the class $\mathrm{Gr}$ of all groups, the class $\mathrm{Mn}$ of all monoids, the class $\mathrm{Sg}$ of all semigroups, respectively). Then the first-order arithmetic is algorithmically reducible to the theory of the class $\operatorname{lat} K$. Hence the theory of the class $\operatorname{lat} K$ is algorithmically undecidable and has no recursive axiomatization. Proof. Consider the formula $\Phi$, which says that:
(i) the lattice has the least element $E$; (ii) each subalgebra, except $E$, has an atom (that is, a minimal subalgebra among those that differ from $E$); (iii) each subalgebra of length 2 has exactly three proper non-trivial subalgebras; (iv) if $N_1$ and $N_2$ are different atoms, then $\langle N_1, N_2\rangle$ is of length $2$; (v) if $L\supsetneqq K$ and $K\neq E$, then there exists $N\subseteq L$ such that $N$ and $K$ are non-comparable. We claim that the formula $\Phi$ is true in the lattice $\operatorname{lat} \mathfrak{A}$ if and only if $\mathfrak{A}$ is an Abelian group $\mathfrak{A}_2$ of exponent $2$. In other words, the function $f(\Psi)=(\Phi\to \Psi)$ reduces the theory of the class $\operatorname{lat} K$ to the theory of lattices of the form $\operatorname{lat} \mathfrak{A}_2$, that is, linear spaces over the field $\operatorname{GF}(2)$. For $\mathfrak{A}_2$, all the conditions are satisfied. Let us take $\{0\}$ as $E$. The subgroups of length 2 are of the form $\mathbb{Z} _2+\mathbb{Z} _2$, they have exactly three proper non-trivial subgroups mentioned in the proof of Theorem 11. Conditions (ii) and (iv) hold trivially. For (v), it is enough to take $x\in L\setminus K$ and construct a one-dimension subspace $N=\langle x\rangle$. Now, let $\mathfrak{A}$ satisfy $\Phi$. First, note that no element of $\mathfrak{A}$ generates an infinite subalgebra. Indeed, such a subalgebra should be isomorphic to the additive group of integer numbers (the monoid of natural numbers, the semigroup of positive integer numbers, respectively). But these subalgebras have no atoms, which contradicts (ii). Next, for $a\in\mathfrak{A}$, we note that if $\langle a\rangle$ is a group, then this group should be trivial or of prime order $p$. To prove it, let us suppose that the order of $\langle a\rangle$ is $p^m$ for $m > 1$. This means that there is a cyclic subgroup of order $p^2$; such a group has length 2 and has exactly one proper non-trivial subgroup. But this contradicts (iii). Another case is where the order of $\langle a\rangle$ has two different prime divisors $p$ and $q$. Hence there exists a cyclic subgroup of order $qp$. This subgroup has length 2 and has exactly two proper non-trivial subgroups. But this again contradicts (iii). Another preliminary remark is worth making. If $\mathfrak{A}$ is a monoid and if its subalgebras $\langle a\rangle$ and $\langle b\rangle$ are non-comparable groups, then both of them are of order 2. We have already proved that their orders are prime. By (iv) and (iii), the group $\langle a, b\rangle$ has exactly three proper non-trivial subgroups: $\langle a\rangle$ and $\langle b\rangle$, the third one is $\langle a+ b\rangle$. To prove the last, we note that $\langle a+ b\rangle$ is not equal to $\langle a\rangle$ and $\langle b\rangle$. If we suppose that $\langle a+ b\rangle$ is equal to $\langle a, b\rangle$, then $\langle a, b\rangle$ is a non-simple cyclic group. We have proved that it is impossible. For the same reason, $\langle 2a+b\rangle$ is not equal to $\langle a, b\rangle$. Hence $\langle 2a+b\rangle$ is the trivial group $E$ or is equal to $\langle a\rangle$, $\langle b\rangle$, or $\langle a+b\rangle$. In the first two cases, we get $b\in\langle a\rangle$, which contradicts the choice of $b$. In the last case, we obtain $2a+b=a+(a+b)\in \langle a+b\rangle$, that is, $a\in \langle a+b\rangle$, which contradicts the above. Therefore, the only possible case is $2a+b\in \langle b\rangle$, $2a\in \langle b\rangle$, which is possible only if $2a=0$. By symmetricity, $2b=0$. Now, consider the classes $\mathrm{Gr}$ and $\mathrm{Ab}$. For $a\in\mathfrak{A}$, all $\langle a\rangle$ are groups; we have already proved that all $\langle a\rangle$ have prime order, and, consequently, are non-comparable. Thus, all non-identity elements are of order 2. This is well known to imply commutativity. Therefore, $\mathfrak{A}$ is an Abelian group of exponent 2. Consider the class $\mathrm{Sg}$. If $a\in E$, then $E=\langle a\rangle=\{a, 2a, \dots, ma, \dots, na\}$ and $(n+1)a=ma$. Since $E'=\{ma, \dots, na\}\subseteq E$ is a semigroup, we have $E'=E$ and $(n+1)a=a$. In this case, $na+na=na$, and $\{na\}$ is also a semigroup. Therefore, $E$ is a singleton (we denote by $0$ the only element of $E$). For every $a\in \mathfrak{A}$, we get $\langle a\rangle=\{a, 2a, \dots, ma, \dots, na\}$, $(n+1)a=ma$. If $m\geqslant 2$, then, for $L=\langle a\rangle$ and $K=\{2a, \dots, ma, \dots, na\}$, we have a contradiction to (v). Thus, $m=1$. Since $E\subseteq\langle a\rangle$, we have $ka=0$ for some $k=1, \dots, n$. Further, since $0+0=0$, it follows that $(k+1)a=ka+a=0+a=0+0+a=ka+ka+a=(2k+1)a$. This means that $n$ is a divisor of $k$ and $n=k$. Finally, we obtain $0+a=(n+1)a=a$ and $a+0=(n+1)a=a$. Hence $0$ is the identity element, $ka=0$, and hence $a$ is invertible. Therefore, $\mathfrak{A}$ is a group; since all its elements are of finite order. Hence an arbitrary subsemigroup is a subgroup. Consider now the last class $\mathrm{Mn}$. In this case, it is clear that $E=\{0\}$. Our first goal is to show that any $a\in \mathfrak{A}$ is an idempotent or generates a subgroup. Otherwise, we would get $\langle a\rangle=\{0, a, 2a, \dots, ma, \dots, na\}$, $(n+1)a=ma$, $n\geqslant 2$, and $m\geqslant 1$. If $m\geqslant 2$, then, for $L=\langle a\rangle$ and $K=\{0, 2a, \dots, ma, \dots, na\}$, we have a contradiction to (v). If $m=1$, then let $d$ be the greatest proper divisor of $n$. Thus, $n=pd$ for some prime $p$, and, for $L=\{0, da, 2da, \dots, pda\}$ and $K=\{0, pda\}$, we again have a contradiction to (v). Let us suppose that $a\neq 0$ is an idempotent: $2a=a$. By considering all possible cases, we will show that all of them contradict $\Phi$. 1) There exist infinitely many $b$’s such that $\langle b\rangle$ is a group. According to the above, all such $b$’s are of order 2. We also have $a+b\neq b$, since otherwise from $a+b=b$ we would get $a=a+0=a+2b=(a+b)+b=2b=0$. 1a) If $a+b=b+a=a$, then $\langle a, b\rangle=\{0, a, b\}$, and $\langle a, b\rangle$ has exactly two proper non-trivial subalgebras; this contradicts (iii). 1b) If $a+b\neq a$ and $a+b$ is an idempotent, then $\langle a, b\rangle=\{0, a, b, a+b, \dots\}$ is of length $\geqslant 3 $: $\langle a, b\rangle\supsetneqq \{0, a, a+b\}\supsetneqq \{0, a\}\supsetneqq E$, which contradicts (iv). The set $\{0, a, a+b\}$ is a subalgebra, because $(a+b)+(a+b)=a+b$ and $(a+b)+a=(a+b)+a+2b=(a+b)+(a+b)+b=(a+b)+b=a+2b=a$. 1c) If $a+b\neq a$ and $2(a+b)=0$, then $(a+b)+(a+b)=0$ implies $a+b+a=b$, $a+b+a=a+b$, and $a+b=b$, which is impossible by the above. The cases for $b+a\neq a$ are dealt with similarly. 2) There are finitely many $b$’s such that $\langle b\rangle$ is a group. In this case, we can take idempotents $a$ and $c$ such that $a+c$ and $c+a$ are also idempotents. 2a) If $a+c,c+a\in\{a, c\}$, then, similarly to case 1a), $\langle a, c\rangle$ has exactly two proper non-trivial subalgebras; this contradicts (iii). 2b) If $a+c\notin\{a, c\}$, then $\langle a, c\rangle=\{0, a, c, a+c, a+c+a, \dots\}$ has the length $\geqslant 3$: $\langle a, c\rangle\supsetneqq \{0, a, a+c, a+c+a\}\supsetneqq \{0, a\}\supsetneqq E$; this contradicts (iv). The set $\{0, a, a+c, a+c+a\}$ is a subalgebra different from $\langle a, c\rangle$, since from $a+c+a=c$ we would obtain $a+c=a+c+a+c=c+c=c$. The case $c+a\notin\{a, c\}$ is considered similarly. So, we have proved that $\mathfrak{A}$ has no idempotents, except $0$. In addition, $\mathfrak{A}$ is a group, and any submonoid is a subgroup due to the finiteness of order. This proves the theorem. § 7. ConclusionsFor many natural classes $K$ of algebras, we have proved that theories of the classes $\exp K$ have the degree of algorithmic undecidability not smaller than that for the first-order arithmetic. But, according to the introduction, there are cases when the theory of the algebra $\exp \mathfrak{A}$ is decidable. Therefore, it is interesting to find classes of such algebras as wide as possible. For axiomatizability, we have the analogous problem: do there exist natural enough classes $K$ such that the classes $\exp K$ admits a finite or recursive axiomatization? In [17], for unary one-one functions, conditions were found under which the algebras $\mathfrak{A}$ and $\exp\mathfrak{A}$ are elementary equivalent, and, even, isomorphic. The same question is also natural for groupoids. The last question is about lattices of subgroups for Abelian groups of finite exponent. We have proved that their theories admit an interpretation of the first-order arithmetic. Can we strengthen this result and prove that such theories admit an interpretation of the second-order arithmetic? And vice versa, does the second-order arithmetic admit an interpretation of the theory of subgroup lattices for Abelian groups of finite exponent? 
Citation in format AMSBIB
\Bibitem{Dud25} |
|
||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|