Is the partial order of all equations in the signature of magmas a lattice?

Question

$\newcommand\Eq{\mathrm{Eq}}$I asked this question on math stack exchange, here, but there were no comments or answers. So, I am asking it here on mathoverflow. Consider the signature of a single binary operation $*$, and consider the set $\Eq$ of all equations in that signature. I can define a preorder $\geq$ on $\Eq$ by stipulating that $E \geq E'$ precisely when $E$ implies $E'$. I can now consider the partial order obtained by quotienting out the preorder by its standard equivalence relation. My question is, is this partial order a lattice? If not, is it at least a join semilattice or a meet semilattice? If not even that, is it still at least the case that for every pair of elements, either the pair has a least upper bound or a greatest lower bound? I would be very interested to be given a pair of equations such that they have neither a least upper bound nor a greatest lower bound.

Answer 1

Is the partial order of all equations in the signature of magmas a lattice?

No.

If not, is it at least a join semilattice or a meet semilattice?

No.

If not even that, is it still at least the case that for every pair of elements, either the pair has a least upper bound or a greatest lower bound?

No.

I would be very interested to be given a pair of equations such that they have neither a least upper bound nor a greatest lower bound.

Let $\Sigma$ be the set of all magma identities. Preorder $\Sigma$ by stipulating that if $I, J\in\Sigma$, then $I\geq J$ iff $I\vdash J$. Assume also that $I\geq J$ is equivalent to $J\leq I$. Let $A$ denote the Associative Law, $x(yz)=(xy)z$. Let $C$ denote the Commutative Law, $xy=yx$. I will explain why $A$ and $C$ do not have a meet or join in $\langle\Sigma;\leq\rangle$.

Lemma 1. $A\wedge C$ does not exist.

Proof. Assume instead that a greatest lower bound $A\wedge C$ exists, and set $M=A\wedge C$. This means that $A\vdash M$, $C\vdash M$, and, for any identity $I$, if both $A\vdash I$ and $C\vdash I$ hold then $M\vdash I$ also holds.

Let's say that a magma term/word $t$ has weight $\geq n$ if it has $\geq n$ occurrences of variables. Let's say that a magma identity $I: t_1=t_2$ has weight $\geq n$ if both of $t_i$ and $t_2$ have weight $\geq n$. For both terms or identities, say that a weight is equal to $n$ if it is $\geq n$ and not $\geq n-1$. (Write $w(t)=n$ or $w(I)=n$ to indicate this.)

Let's call a magma identity $I$ strongly regular if, for each variable $x$, there are the same number of occurrences of $x$ on both sides of $I$.

The associative law $A$ is strongly regular of weight $3$ and the commutative law $C$ is strongly regular of weight $2$. It follows from the laws of equational deduction (Theorem 14.7 of Burris-Sankappanavar) that if $C\vdash I$, then $I$ is strongly regular and $w(I)\geq 2$, while if $A\vdash I$, then $I$ is strongly regular and $w(I)\geq 3$. We conclude that $M$ is strongly regular of weight at least $3$.

We argue next that the weight of the meet $M$ cannot be $\geq 4$, hence $w(M)=3$. To see this, observe that the magma $\mathbf{P}=\langle \{0,1,2,3\}; \cdot\rangle$ whose operation table is

$$ \begin{array}{|c||c|c|c|c|} \hline \cdot & 0 & 1 & 2 & 3 \\ \hline \hline 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline 2 & 0 & 0 & 0 & 1 \\ \hline 3 & 0 & 0 & 0 & 2 \\ \hline \end{array} $$ satisfies every magma identity $t_1=t_2$ of weight at least $4$. This is because the interpretation of any magma term of weight at least $4$ is constant $0$. Now, if the meet identity $M$ had weight at least $4$, then it would hold in $\mathbf{P}$. But $A\vdash x(yx)=x(yx)$ and $C\vdash x(yx)=x(yx)$, so we must have $M\vdash x(yx)=x(yx)$ if $M$ is truly the meet of $A$ and $C$. Since $\mathbf{P}\models M$ (provided $w(M)\geq 4$) we would have $\mathbf{P}\models x(yx)=x(yx)$. But this is false, as one sees by substituting $x=3=y$. This completes the proof that $w(M)=3$.

Since $w(M)=3$ and $M$ is strongly regular, we must have that $M$ equals $t_1=t_2$ where $t_1$ and $t_2$ both involve three variables. Since $A\vdash M$, the words $t_1$ and $t_2$ become identical if we ignore the placement of parentheses. But since $M$ is nontrivial, $t_1$ and $t_2$ are not identical, so they must differ only in the order of parentheses. That is, $M$ equals $v_1(v_2v_3)=(v_1v_2)v_3$ for some variables $v_1, v_2, v_3\in \{x,y,z\}$. Up to the renaming of variables $M$ must be one of

1. $x(xx)=(xx)x$
2. $x(yx)=(xy)x$
3. $x(xy)=(xx)y$
4. $x(yy)=(xy)y$
5. $x(yz)=(xy)z$

Only the first two choices are consequences of $C$, so we can exclude the others. (The last three choices fail in the commutative magma with universe $\{0,1\}$ whose product has Boolean expression $\neg x\wedge \neg y$.) The first two identities are consequences of both $A$ and $C$, but $x(yx)=(xy)x$ is the stronger identity, hence it is the only viable candidate for the meet identity $M$.

We have reached the conclusion that the only viable candidate for $M$ is $x(yx)=(xy)x$. This identity is a consequence of both $A$ and $C$, but it is not their meet. The identity $$ ((xy)z)(x(yz)) = (x(yz))((xy)z) $$ is also a consequence of both $A$ and $C$, yet it is not a consequence of $x(yx)=(xy)x$. This was proved by user bof here. This shows that the meet of $A$ and $C$ does not exist. \\\

Lemma 2. $A\vee C$ does not exist.

Proof. Assume instead that a least upper bound $A\vee C$ exists, and set $J=A\vee C$. This means that $J\vdash A$, $J\vdash C$, and, for any identity $I$, if both $I\vdash A$ and $I\vdash C$ hold then $I\vdash J$.

I now define the Kinyon-McCune identity. Let $t_n(x) = (x(x(\cdots (xx)\cdots )))$ be a right associated product of $n-1$ variables, all equal to $x$. Let $KM_n$ be the identity $$ ((xy)z)\cdot t_n(xz) = y. $$ Since $t_n$ is an abbreviation of a magma term, this is a magma identity. I explain after the proof why $KM_n$ is a single magma identity that defines the variety of abelian groups of exponent $n$ considered as magmas with group product as the binary operation. Let's accept this claim for now.

Since $KM_n\vdash A$ and $KM_n\vdash C$, we must have $KM_n\vdash J$ for all $n$. This implies that $J$ holds in every finite abelian group. Since free commutative semigroups are residually in the class of finite abelian groups, it follows that $J$ holds in every free commutative semigroup, hence in every commutative semigroup. On the other hand, since $J\vdash A$ and $J\vdash C$, every model of $J$ must be a commutative semigroup. This is enough to prove that the identity $J$ must be a single axiom that defines the class of commutative semigroups. But there is no such axiom, as was proved by user bof here. This shows that there is no identity $J$ that is the join of $A$ and $C$. \\\

Let me say something about the Kinyon-McCune identity.

William McCune discovered that the identity $$ ((xy)z)\cdot u(xz)=y $$ in the signature $\{\textrm{product}, u(x)\}$ defines the class of abelian groups in which $u(x)$ must interpret as $x^{-1}$. His result is Theorem 2 of

William W. McCune,
Single Axioms for Groups and Abelian Groups with Various Operations
Journal of Automated Reasoning 10: 1-13, 1993.

Michael Kinyon noticed that if you choose $u(x) = (x(x(\cdots (xx)\cdots)))$, ($n-1$ $x$'s), then McCune's Identity $((xy)z)\cdot u(xz)=y$ will define a variety of abelian groups satisfying $x^{-1} = u(x) = x^{n-1}$. This shows that $KM_n$ defines some subvariety of the variety of abelian groups of exponent $n$ with a single identity in the language of product alone. But since $KM_n$ holds in any abelian group of exponent $n$, the variety axiomatized by $KM_n$ must be the full variety of all abelian groups of exponent $n$.