# Varieties generated by a two element algebra

I have two questions regarding universal algebra, and also its ordered version.

1. If a variety $\mathcal{V}$ is generated by a specific two element algebra $2 = \{0,1\}$, then is that the only subdirectly-irreducible algebra in $\mathcal{V}$?

2. If an ordered variety $\mathcal{V}$ is generated by a specific two element ordered algebra $2$, such that the ordered relation $0 \leq 1$ holds, is that the only subdirectly-irreducible algebra in $\mathcal{V}$?

By an ordered algebra I mean it has a poset as a carrier, the operations being monotone relative to it. By an ordered variety I mean a collection of ordered algebras closed under morphic images (surjective monotone algebra morphisms), embeddings (subalgebras with inherited order) and direct products (ordered pointwise). There is a corresponding inequational system, which is exactly like Birkhoff's but necessarily without symmetry.

Note that in the ordered case a two element algebra needn't be subdirectly irreducible e.g. taking no operations and no inequations yields $\mathsf{Poset}$, but the discrete two element set is not subdirectly irreducible via the surjective monotone map to the $2$-chain.

It would be enough to know that every algebra arises as a subdirect product of $2$'s, where in the ordered case the subdirect embedding is also a poset embedding.

Many thanks for any help.

My first question has been answered negatively below by Emil Jeřábek.

However I would like to add the additional condition that $\mathcal{V}$ is Post-complete. That is, one cannot add any new equation to the equational theory of $2$ without obtaining the inconsistent theory.

Examples are boolean algebras, distributive lattices, posets with top and bottom, vector spaces over $\mathbb{F}_2$.

Regarding the counterexamples below, unary involutive algebras are not Post-complete, since $a(x) = x$ still permits sets where every element is a fixpoint. Similarly, pointed abelian groups of exponent $2$ are not Post-complete, since the equation 0 = 1 yields vector space over $\mathbb{F}_2$.

-
I suspect the answer is yes for 1) and no for 2), but I am unsure. For 1) I would look at Post's classification and see which subvarieties you can clear away by knowing the results for Boolean algebras and for semilattices. Then you can come back with a more specific question. For 2), there is likely a simple example, but I am not seeing it. Gerhard "Someone Invite Jonathan Farley Over" Paseman, 2014.01.16 –  Gerhard Paseman Jan 16 '14 at 18:58
Also, there are situations where Var(A)=SP(A), especially for Boolean algebras. I would be unsurprised if there were a paper classifying those varieties generated by a two element algebra in which Var(A)=SP(A). Gerhard "Ask Me About System Design" Paseman, 2014.01.16 –  Gerhard Paseman Jan 16 '14 at 19:01
@Gerhard: Thanks, I have indeed been looking at Post's lattice of clones. However I am also in somewhat of a rush and was hoping that at least the first result was known (or known to fail) and had a reference. The examples I have checked include boolean algebras, sets, vector spaces of binary field, join-semilattices with or without bottom, distributive lattices, and others. –  Rob Myers Jan 16 '14 at 19:02
Good luck, Rob. My best recommendations are the references contained in Burris and Sankappanavar's book, and McKenzie, McNulty and Taylor's book. You might get lucky with a web search on "2-generated subdirectly irreducible", if what you want is a reference as opposed to a proof. Gerhard "Hope You Find It Soon" Paseman, 2014.01.16 –  Gerhard Paseman Jan 16 '14 at 19:06

Question 1 amounts to asking whether $HSP(2)=ISP(2)$ (i.e., the quasivariety generated by $2$ is a variety), and this can fail.

For instance, the algebra $\langle\{0,1\},\neg\rangle$ generates the variety of involutive unary operations, however nontrivial subdirect products of this algebra are additionally fixpoint-free (that is, the quasivariety generated by the algebra includes a nontrivial quasiidentity $x=\neg x\to x=y$). In particular, the three-element algebra with one fixpoint is another subdirectly irreducible algebra in this variety.

For another example, $\langle\{0,1\},+,0,1\rangle$ generates the variety of pointed abelian groups of exponent $2$, but its nontrivial subdirect products also satisfy $1\ne0$, and the (also two-element, but nonisomorphic) algebra $\langle\{0,1\},+,0,0\rangle$ is subdirecly irreducible in this variety.

I don’t know much about ordered varieties, but I’d expect the situation to get even more complicated.

I think the answer to question 1 is affirmative for Post-complete (i.e., minimal) varieties. I don’t know of any clever argument, so let me outline a proof based on chasing Post’s lattice. Let $\def\2{\mathbf 2}\def\p#1{\langle#1\rangle}\2=\p{2,\dots}$ be a two-element algebra, $C$ its clone of term operations, and $V=HSP(\2)$. I will use the notation from http://en.wikipedia.org/wiki/Post%27s_lattice.

Observe that if $C$ includes $c\le2$ constants, any equation invalid in $\2$ has an invalid substitution instance in $2-c$ variables, hence Post completeness of $V$ only depends on the set of $(2-c)$-ary functions in $C$.

Case 1: All functions in $C$ are affine.

• The varieties of $\p{2,0,1}$, $\p{2,\neg,0}$, and $\p{2,+,1}$ are not Post-complete, as their equational theory has a proper extension by the equation $0=1$. Likewise, the varieties of $\p{2,\neg}$ and $\p{2,\neg,x+y+z}$ are consistent with $x=\neg x$.

• In all other cases, $\2$ generates $V$ as a quasivariety. For $\p{2}$, $\p{2,0}$, and $\p{2,1}$, this is easily checked from the trivial form of equations they allow. For $\p{2,+}$ and its dual $\p{2,\leftrightarrow}$, this follows as every linear space over $\mathbb F_2$ is a direct sum of $1$-dimensional spaces. For $\p{2,x+y+z}$, every equation is equivalent to $x=x$ or to $x=\sum_{i\in I}x_i$, where $I$ is a set of variables distinct from $x$ and from each other, and $|I|$ is odd. If a quasi-identity includes such as equation in the premise, we can substitute the right-hand side for $x$ and eliminate it. In this way, we eventually arrive at an identity equivalent over $V$ to the original quasi-identity.

Case 2: $\2$ is $\p{2,\land}$ with or without some of the constants, or its dual algebra.

Let $A\in V$ and $a\ne b\in A$. W.l.o.g. $a\nleq b$. Then the function $f\colon A\to\2$ mapping all $x\ge a$ to $1$ and $x\ngeq a$ to $0$ is a homomorphism such that $f(a)\ne f(b)$.

Case 3: $C$ includes $\mathrm{maj}(x,y,z)$ or $x\land(y\lor z)$ or its dual $x\lor(y\land z)$.

$V$ is congruence distributive: this is clear for the majority operation. In the case of $x\land(y\lor z)$, we have a sequence of Jónsson terms $x,x\land(y\lor z),x\land z,z\land(x\lor y),z$, that is, the following identities hold: \begin{gather*} x\land(y\lor x)=x\land x=x\land(x\lor y)=x,\\ x=x\land(x\lor z),\\ x\land(z\lor z)=x\land z=z\land(x\lor x),\\ z\land(x\lor z)=z. \end{gather*} It follows that the only subdirectly irreducible algebra in $V$ is $\2$ by Jónsson’s lemma.

As a summary, the only subdirectly irreducible algebra in $V$ is $\2$ unless $\2$ is term-equivalent to one of the five algebras mentioned in the first part of Case 1, in which case $V$ is not Post-complete.

-
Thank you for the information. What about the additional property that the generated variety is Post-complete i.e. an atom in the lattice of varieties for the signature? I would greatly appreciate any pointers. –  Rob Myers Jan 16 '14 at 20:02
And in general, a variety generated by a single subdirectly irreducible algebra can have arbitrarily large additional subdirectly irreducible algebras in it. –  arsmath Jan 16 '14 at 20:18
@Rob Myers: I’m inclined to believe that the answer for Post-complete varieties is positive, but it might require a messy case analysis. –  Emil Jeřábek Jan 17 '14 at 0:04