3
$\begingroup$

The finite algebras $(A,*,+)$ that satisfy the identity $(x*y)+(y*z)=(x+y)*(y+z)$ are precisely the algebras such that the one-dimensional cellular automata produced by $*$ and $+$ are commutative cellular automata. To be clear the operations $*,+$ do not necessarily satisfy any associativity or any other well known laws. See the paper Commuting Cellular Automata for details on this identity and its relation to cellular automata (or see my answer here for less details). I want to know if the variety $V$ of algebras that satisfy $(x*y)+(y*z)=(x+y)*(y+z)$ is generated by the collection of all its finite algebras. It suffices to show that the free algebras in $V$ are subdirect products of finite algebras in $V$. If the finite algebras $(A,*,+)$ satisfy other kinds of identities not implies by $(x*y)+(y*z)=(x+y)*(y+z)$, then what is an explicit example of such an identity? If the free algebras in $V$ are subdirect products of finite algebras in $V$, then what is a good explicit example of how to embed the free algebras in $V$ as subdirect products of finite algebras in $V$?

Part of the motivation for this question is that cellular automata are usually over a finite alphabet $A$, so I wonder if finite algebras that satisfy $(A,*,+)$ that satisfy the identity $(x*y)+(y*z)=(x+y)*(y+z)$ satisfy any other identities.

$\endgroup$
8
$\begingroup$

Theorem. If $\mathcal V$ is a variety of finite signature and $\mathcal V$ can be axiomatized by identities of the form $s\approx t$ where $\textit{length}(s)=\textit{length}(t)$, then $\mathcal V$ is generated by its finite members.

(For this theorem, say that $\textit{length}(s)=\textit{length}(t)$ if $s$ and $t$ have the same multiset of variables and the same number of operation symbols.)

Proof. Under the length hypothesis of the theorem, there is a congruence $\theta_n$ on ${\mathbf F}_{\mathcal V}(m)$ which relates two elements iff they are equal or else they can be each represented by terms of length greater than $n$. The signature is finite, so there are finitely many elements of ${\mathbf F}_{\mathcal V}(m)$ represented by terms of length at most $n$, and therefore ${\mathbf F}_{\mathcal V}(m)/\theta_n$ is finite. The intersection of the $\theta_n$'s is trivial, so this yields a representation $$ {\mathbf F}_{\mathcal V}(m)\hookrightarrow \prod_n {\mathbf F}_{\mathcal V}(m)/\theta_n $$ of ${\mathbf F}_{\mathcal V}(m)$ as a subdirect product of finite algebras. \\

Your variety has finite signature, and the defining identity $(x*y)+(y*z)=(x+y)*(y+z)$ has the same multiset of variables on both sides, $\{x, y, y, z\}$, and the same number ($3$) of operation symbols on both sides.

EDIT (8/18/15): The above explains why the finitely generated free algebras in $\mathcal V$ are subdirect products of finite algebras. A question was raised about whether it is necessary to also show that the infinitely generated free algebras are subdirect products of finite algebras. It is not necessary to do this: the infinitely generated free algebras in $\mathcal V$ are subdirect products of finitely generated free algebras in $\mathcal V$.

$\endgroup$
  • $\begingroup$ Thank you for the clarifying edit. Gerhard "Needs A Universal Algebra Brushup" Paseman, 2015.08.28 $\endgroup$ – Gerhard Paseman Aug 29 '15 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.