Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
1  
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 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 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 at 19:02
1  
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 at 19:06

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 at 20:02
1  
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 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 at 0:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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