The Embedding Theorem for Cantor Varieties

L. V. Shabunin

Algebra i logika, Tome 40 (2001) no. 3, pp. 352-369

Résumé

Let $m$ and $n$ be fixed integers, with $1\leqslant m$. A Cantor variety $C_{m,n}$ is a variety of algebras with $m$ $n$-ary and $n$ $m$-ary basic operations which is defined in a signature $\Omega=\{g_1,\dots,g_m,f_1,\dots,f_n\}$ by the identities \begin{gather*} f_i(g_1(x_1,\dots,x_n),\dots,g_m(x_1,\dots,x_n))=x_i, \qquad i=1,\dots,n, \\ g_j(f_1(x_1,\dots,x_m),\dots,f_n(x_1,\dots,x_m))=x_j, \qquad j=1,\dots,m. \end{gather*} We prove the following: (a) every partial $C_{m,n}$-algebra $A$ is isomorphically embeddable in the algebra $G=\langle A; S(A)\rangle$ of $C_{m,n}$; (b) for every finitely presented algebra $G=\langle A; S\rangle$ in $C_{m,n}$, the word problem is decidable; (c) for finitely presented algebras in $C_{m,n}$, the occurrence problem is decidable; (d) $C_{m,n}$ has a hereditarily undecidable elementary theory.

Détail

Keywords: Cantor variety, the word problem, the occurrence problem, elementary theory.