Structure theorems for idempotent residuated lattices

Abstract

In this paper we study structural properties of residuated lattices that are idempotent as monoids. We provide descriptions of the totally ordered members of this class and obtain counting theorems for the number of finite algebras in various subclasses. We also establish the finite embeddability property for certain varieties generated by classes of residuated lattices that are conservative in the sense that monoid multiplication always yields one of its arguments. We then make use of a more symmetric version of Raftery’s characterization theorem for totally ordered commutative idempotent residuated lattices to prove that the variety generated by this class has the amalgamation property. Finally, we address an open problem in the literature by giving an example of a noncommutative variety of idempotent residuated lattices that has the amalgamation property.

1 Introduction

A residuated lattice is an algebraic structure $\mathbf{A}=\langle A,\wedge ,\vee ,\cdot ,{\backslash },{/},{\mathrm e}\rangle$ of type $\langle 2,2,2,2,2,0 \rangle$ such that $\langle A,\wedge ,\vee \rangle$ is a lattice, $\langle A,\cdot ,{\mathrm e}\rangle$ is a monoid, and ${\backslash },{/}$ are left and right residuals, respectively, of $\cdot$ in the underlying lattice order, i.e., $b \le a {\backslash }c \iff a \cdot b \le c \iff a \le c {/}b$  for all $a,b,c\in A$. Such structures provide algebraic semantics for substructural logics, as well as encompassing well-studied classes of algebras such as lattice-ordered groups and lattices of ideals of rings with product and division operators (see, e.g., [3, 9, 12, 19]).

A residuated lattice $\mathbf {A}$ is called idempotent if $a \cdot a=a$ for all $a\in A$. Structural properties of idempotent residuated lattices have been studied quite widely in the literature (see, e.g., [4,5,6, 8, 11, 15, 20, 21]), notably for Brouwerian algebras, where the product coincides with the meet, and odd Sugihara monoids, where the product is commutative and the map $x \mapsto x {\backslash }{\mathrm e}$ is an involution. The monoidal structure of any idempotent residuated lattice $\mathbf {A}$ is a unital band and the relation on A defined by $a\sqsubseteq b\, :\Longleftrightarrow \, a\cdot b=a$ is a preorder that we call the monoidal preorder of $\mathbf {A}$; if the product of $\mathbf {A}$ is also commutative, then $\langle A,\cdot ,{\mathrm e}\rangle$ is a unital meet-semilattice with order $\sqsubseteq$ and greatest element ${\mathrm e}$. When $\mathbf {A}$ is totally ordered—that is, $\mathbf {A}$ is a residuated chain—the product has the further property that $a\cdot b \in \{a,b\}$ for all $a,b\in A$; we call residuated lattices satisfying this condition conservative, noting that semigroups with this property are called quasitrivial (see, e.g., [7]).

The aim of this paper is to obtain structural descriptions of various classes of idempotent residuated chains, recalling that such classes generate varieties of semilinear residuated lattices, also referred to in the literature as representable residuated lattices (see, e.g., [21]). In Section 3, we make use of a description, first given in [22], of finite commutative idempotent residuated chains (Theorem 3.1) to prove that there are $2^{n-2}$ such algebras of size $n\ge 2$ (Theorem 3.2). We then establish a more symmetric version of Raftery’s characterization theorem [21] for commutative idempotent residuated chains (Theorem 3.5), obtaining also as a corollary (as in [21]) that the variety of semilinear commutative idempotent residuated lattices is locally finite.

In Section 4, we provide a description of finite idempotent residuated chains (Theorem 4.3) and show (Theorem 4.4, proved independently in [7]) that the number $\mathbf {I}(n)$ of such algebras of size $n\ge 2$ satisfies the recurrence formula $\mathbf {I}(2) = 1$, $\mathbf {I}(3) = 2$, $\mathbf {I}(n+2) = 2\mathbf {I}(n) + 2\mathbf {I}(n+1)$, yielding

$$\begin{aligned} \mathbf {I}(n) = \frac{\big (1+\sqrt{3}\,\big )^n - \big (1-\sqrt{3}\,\big )^n}{2\sqrt{3}}. \end{aligned}$$

In Section 5, we prove that if a variety is generated by a class of conservative residuated lattices defined relative to the variety of residuated lattices by a set of positive universal formulas over the language $\{\vee , \cdot , {\mathrm e}\}$, then it has the finite embeddability property (Theorem 5.1). In particular, this is the case for the variety of semilinear idempotent residuated lattices, which is shown to be not locally finite. We then give a description of finite conservative commutative residuated lattices (Theorem 5.5) and prove (Theorem 5.6) that the number of such algebras with $n\ge 1$ elements is the $(n-1)$th Catalan number

$$\begin{aligned} \mathbf {C}(n) = \frac{1}{n}\left( {\begin{array}{c}2(n-1)\\ n-1\end{array}}\right) . \end{aligned}$$

Finally, in Section 6, we use Theorem 3.5 and a theorem for amalgamation in varieties of residuated lattices from [18] to prove that the variety of semilinear commutative idempotent residuated lattices has the amalgamation property (Theorem 6.6). We also solve an open problem in the literature (see, e.g., [18]) by giving an example of a noncommutative variety of residuated lattices (generated by a four element residuated chain) that has the amalgamation property (Theorem 6.8).

2 Preliminaries

In this section, we establish some basic properties for idempotent residuated lattices. Recall first that the cone of a residuated lattice $\mathbf{A}$ is the union of its positive cone$\mathord {\uparrow }{\mathrm e}$ and negative cone$\mathord {\downarrow }{\mathrm e}$, and that $\mathbf{A}$ is conical if $A = \mathord {\uparrow }{\mathrm e}\cup \mathord {\downarrow }{\mathrm e}$. An element of a conical residuated lattice is said to have positive sign if it belongs to the positive cone, and negative sign otherwise. From now on, we also denote the product of elements a, b in a monoid by ab.

Lemma 2.1

(Cf. [22, Lem. 2.1]). For any idempotent residuated lattice $\mathbf {A}$ and $x,y \in A$:

• (i) $x\wedge y\le xy\le x\vee y$.

• (ii) If ${\mathrm e}\le xy$, then $xy = x\vee y$.

• (iii) If $xy\le {\mathrm e}$, then $xy = x\wedge y$.

• (iv) If $x,y \in \mathord {\uparrow }{\mathrm e}$, then $xy=x\vee y$, and, if $x,y \in \mathord {\downarrow }{\mathrm e}$, then $xy=x\wedge y$.

• (v) $\langle \mathord {\downarrow }{\mathrm e},\wedge ,\vee ,\Rightarrow ,{\mathrm e}\rangle$ is a Brouwerian algebra, where $x\Rightarrow y :=(x{\backslash }y)\wedge {\mathrm e}$.

Proof

(i) $x\wedge y = (x\wedge y)(x\wedge y) \le xy \le (x\vee y)(x\vee y) = x\vee y$.

(ii) If ${\mathrm e}\le xy$, then $y \le xyy = xy$ and $x \le xxy = xy$. So $x\vee y \le xy \le x\vee y$.

(iii) If $xy\le {\mathrm e}$, then $xy = xyy \le y$ and $xy = xxy \le x$. So $x\wedge y \le xy \le x\wedge y$.

(iv) Follows immediately from (ii) and (iii).

(v) Note that in any residuated lattice $xz\le y\iff z\le x{\backslash }y$, and if $z\le {\mathrm e}$, then $z\le x{\backslash }y \iff z\le (x{\backslash }y)\wedge {\mathrm e}=x\Rightarrow y$. So $x\wedge z\le y\iff z\le x\Rightarrow y$ holds in $\mathord {\downarrow }{\mathrm e}$, and $\langle \mathord {\downarrow }{\mathrm e},\wedge ,\vee ,\Rightarrow ,{\mathrm e}\rangle$ is a Brouwerian algebra.$\square$

For any idempotent residuated lattice $\mathbf{A}$, we define the following useful binary relation on A:

$$\begin{aligned} x\sqsubseteq y\ :\Longleftrightarrow \ xy = x. \end{aligned}$$

The next lemma justifies us in calling $\sqsubseteq$ the monoidal preorder of $\mathbf {A}$.

Lemma 2.2

For any idempotent residuated lattice $\mathbf{A}$, the relation $\sqsubseteq$ is a preorder on A with greatest element ${\mathrm e}$, where if $\mathbf{A}$ has a least element, this is also the least element of $\sqsubseteq$. Moreover, for any $x,y\in A$:

• (i) If ${\mathrm e}\le x,y$, then $x\le y \iff y\sqsubseteq x$.

• (ii) If $x, y\le {\mathrm e}$, then $x\le y \iff x\sqsubseteq y$.

Proof

The reflexivity and transitivity of $\sqsubseteq$ follow from the idempotence and associativity of the product of $\mathbf{A}$, respectively. So $\sqsubseteq$ is a preorder. Since ${\mathrm e}$ is the unit of the product, it is the greatest element of $\sqsubseteq$, and if $\mathbf{A}$ has a least element $\bot$, it is an annihilator of the product and the least element of $\sqsubseteq$.

For (i), if ${\mathrm e}\le x,y \in A$, then, using Lemma 2.1 (iv),

$$\begin{aligned} x\le y \iff y\vee x = y \iff yx = y \iff y\sqsubseteq x. \end{aligned}$$

The proof of (ii) is analogous. $\square$

A residuated lattice $\mathbf {A}$ is commutative if $ab = ba$ for all $a,b\in A$; in this case, also $a{\backslash }b = b {/}a$ for all $a,b \in A$ and we drop one division operator from the signature, writing $a \rightarrow b$ for $a {\backslash }b$. The next result then follows directly from Lemma 2.2, and justifies us in calling the monoidal preorder of a commutative idempotent residuated chain its monoidal order.

Corollary 2.3

The monoidal preorder $\sqsubseteq$ of any commutative idempotent residuated lattice $\mathbf {A}$ is a meet-semilattice order with greatest element ${\mathrm e}$; if $\mathbf {A}$ is totally ordered, then $\langle A,\cdot ,{\mathrm e}\rangle$ is a totally ordered upper-bounded meet-semilattice.

Recall from the introduction that a residuated lattice $\mathbf {A}$ is conservative if $ab \in \{a,b\}$ for all $a,b\in A$; in particular, a commutative idempotent residuated lattice is conservative if and only if its monoidal preorder is total. Observe also that the monoidal preorder of a conservative idempotent residuated lattice determines its product: that is, if $x\sqsubseteq y$, then $xy = x$ by definition; otherwise, $xy = y$. The next lemma shows that this is the case in particular for any idempotent residuated chain.

Lemma 2.4

Every idempotent residuated chain $\mathbf {A}$ is conservative and its monoidal preorder therefore determines its product.

Proof

Let $x,y\in A$. Then either ${\mathrm e}\le xy$ or $xy\le {\mathrm e}$, and hence, by Lemma 2.1, either $xy=x\vee y$ or $xy =x\wedge y$. Since $\mathbf{A}$ is totally ordered, $xy\in \{x,y\}$. $\square$

The converse does not hold; every conservative residuated lattice is idempotent, but might not be totally ordered. This is the case, however, for the elements belonging to its cone.

Lemma 2.5

If $\mathbf{A}$ is a conservative residuated lattice, then $\langle \mathord {\downarrow }{\mathrm e}\cup \mathord {\uparrow }{\mathrm e},\le \rangle$ is a chain.

Proof

By Lemma 2.1, $xy=x\wedge y$ for any x, y in the negative cone of $\mathbf {A}$, and therefore conservativity implies that $x\wedge y=x$ or $x\wedge y=y$, so $\langle \mathord {\downarrow }{\mathrm e},\le \rangle$ is a chain. The argument for the positive cone is symmetrical. $\square$

Example 2.6

The variety $\mathsf {OSM}$ of odd Sugihara monoids consists of semilinear commutative idempotent residuated lattices satisfying $(x\rightarrow {\mathrm e})\rightarrow {\mathrm e}\approx x$, and is generated as a quasivariety (proved in [8]) by the algebra

$$\begin{aligned} \mathbf{Z} = \langle {{\mathbb {Z}}},\wedge ,\vee ,\cdot ,\rightarrow ,0\rangle , \end{aligned}$$

where $\cdot$ is the meet operation of the total order

$$\begin{aligned} \dots \prec -3 \prec 3 \prec -2 \prec 2 \prec -1 \prec 1 \prec 0, \end{aligned}$$

and, by calculation,

$$\begin{aligned} x\cdot y = {\left\{ \begin{array}{ll} x \wedge y &{}\quad \text {if } x \le -y,\\ x \vee y &{}\quad \text {if } x> -y,\\ \end{array}\right. } \quad \text {and}\quad x\rightarrow y = {\left\{ \begin{array}{ll} (-x)\vee y &{}\quad \text {if } x \le y,\\ (-x)\wedge y &{}\quad \text {if } x>y.\\ \end{array}\right. } \end{aligned}$$

Fig. 1

Varieties of idempotent residuated latices

Let us denote the varieties of idempotent and commutative idempotent residuated lattices by $\mathsf {IdRL}$ and $\mathsf {CIdRL}$, respectively, and the corresponding semilinear varieties generated by their totally ordered members by $\mathsf {SemIdRL}$ and $\mathsf {SemCIdRL}$. The class of conservative residuated lattices is not closed under products (e.g., the two element residuated chain $\mathbf {2}$ is conservative, but not the product $\mathbf {2}\times \mathbf {2}$) and hence does not form a variety. However, it is defined relative to residuated lattices by a positive universal formula and is therefore a positive universal class. Let us denote the varieties generated by the classes of conservative and commutative conservative residuated lattices by $\mathsf {CsRL}$ and $\mathsf {CCsRL}$, respectively, noting that the latter is axiomatized relative to the variety of commutative residuated lattices (via a method described in [9]) by the equation (with $s\leftrightarrow t := (s \rightarrow t) \wedge (t\rightarrow s)$)

$$\begin{aligned} {\mathrm e}\approx ((xy \leftrightarrow x) \wedge {\mathrm e}) \vee ((xy\leftrightarrow y)\wedge {\mathrm e}). \end{aligned}$$

Inclusions between the mentioned varieties are displayed in Figure 1, and Table 1 summarizes which of these varieties are locally finite (LF), have the finite embeddability property (FEP), or have the amalgamation property (AP), where the superscripts denote where these results were first proved and ‘?’ denotes that the problem is still open. Note that amalgamation for ${\mathsf {CIdRL}}$ is a consequence of Craig interpolation for the corresponding logic (proved in [13]) and a general theory relating these two properties (see, e.g., [9, 18]).

Table 1 Properties of varieties of idempotent residuated latices

3 Commutative idempotent residuated chains

In this section, we study the structure of commutative idempotent residuated chains. First, we identify properties of the monoidal order of these algebras and show that in the finite setting they yield a complete structural description (cf. [22, Proposition 4.2 and Corollary 4.3]).

Let $\mathbf {C} = \langle C,\le \rangle$ be any chain. We say that a total order $\sqsubseteq$ on C with greatest element ${\mathrm e}$ is compatible with $\mathbf {C}$ if

• 1. whenever $\mathbf {C}$ has a least element $\bot$, also $\langle C,\sqsubseteq \rangle$ has least element $\bot$;

• 2. for all $x,y\in C$, if ${\mathrm e}\le x,y$, then $x\le y \iff y\sqsubseteq x$;

• 3. for all $x,y\in C$, if $x, y\le {\mathrm e}$, then $x\le y \iff x\sqsubseteq y$.

Theorem 3.1

• (a) The monoidal order $\sqsubseteq$ of any commutative idempotent residuated chain $\mathbf {A}$ is total and compatible with $\langle A,\le \rangle$.

• (b) For any chain $\mathbf {C}=\langle C,\le \rangle$ and compatible total order $\sqsubseteq$ on $\mathbf {C}$, the algebra $\langle C,\wedge ,\vee ,\cdot ,{\mathrm e}\rangle$ is a commutative idempotent totally ordered monoid, where

  $$\begin{aligned} x\cdot y = {\left\{ \begin{array}{ll} x &{}\quad \text {if } x\sqsubseteq y,\\ y &{}\quad \text {otherwise}. \end{array}\right. } \end{aligned}$$

  Moreover, if $\mathbf {C}$ is finite, then $\cdot$ has a (uniquely determined) residual $\rightarrow$ and $\langle C,\wedge ,\vee ,\cdot ,\rightarrow ,{\mathrm e}\rangle$ is a commutative idempotent residuated chain.

Proof

Part (a) follows from Lemmas 2.2 and 2.4, and Corollary 2.3. For part (b), notice that the defined product is associative, commutative, and idempotent as $x\cdot y$ is the $\sqsubseteq$-meet of x and y for all $x,y\in C$. The element ${\mathrm e}$ is the identity, because it is the greatest element of $\sqsubseteq$. In order to check that $x(y\vee z) = xy\vee xz$ for all $x,y,z\in C$, we may assume without loss of generality that $y\le z$ and prove that $xz = xy\vee xz$, i.e., $xy\le xz$.

We consider the following cases:

• If ${\mathrm e}\le x,y,z$, then the product is just the $\le$-join of x, y, z, and hence the equation holds. Similarly, if $x,y,z\le {\mathrm e}$, then the product is the $\le$-meet of x, y, z, and the equation holds by distributivity.

• If $x\le {\mathrm e}\le y\le z$, then $z\sqsubseteq y$, by compatibility. If $x\sqsubseteq z\sqsubseteq y$, then $xy = x = xz$; if $z\sqsubseteq x\sqsubseteq y$, then $xy = x\le z = xz$; if $z\sqsubseteq y\sqsubseteq x$, then $xy = y\le z = xz$.

• If $x\le y\le {\mathrm e}\le z$, then $x\sqsubseteq y$, by compatibility. If $x\sqsubseteq y\sqsubseteq z$, then $xy = x = xz$; if $x\sqsubseteq z\sqsubseteq y$, then $xy = x = xz$; if $z\sqsubseteq x\sqsubseteq y$, then $xy = x \le z = xz$.

• If $y\le x\le {\mathrm e}\le z$ then $y\sqsubseteq x$, by compatibility. If $y\sqsubseteq x\sqsubseteq z$, then $xy = y \le z = xz$; if $y\sqsubseteq z\sqsubseteq x$, then $xy = y \le z = xz$; if $z\sqsubseteq y\sqsubseteq x$, then $xy = y \le z = xz$.

• If $y\le {\mathrm e}\le x\le z$, then $z\sqsubseteq x$, by compatibility. If $z\sqsubseteq x\sqsubseteq y$, then $xy = x \le z = xz$; if $z\sqsubseteq y\sqsubseteq x$, then $xy = y\le z = xz$; if $y\sqsubseteq z\sqsubseteq x$, then $xy = y \le z = xz$.

• If $y\le {\mathrm e}\le z\le x$, then $x\sqsubseteq z$, by compatibility. If $x\sqsubseteq z\sqsubseteq y$, then $xy = x = xz$; if $x\sqsubseteq y\sqsubseteq z$, then $xy = x = xz$; if $y\sqsubseteq x\sqsubseteq z$, then $xy = y\le x = xz$.

• If $y\le z\le {\mathrm e}\le x$, then $y\sqsubseteq z$, by compatibility. If $y\sqsubseteq z\sqsubseteq x$, then $xy = y\le z =xz$; if $y\sqsubseteq x\sqsubseteq z$, then $xy = y\le x = xz$; if $x\sqsubseteq y\sqsubseteq z$, then $xy = x = xz$.

In the case that $\mathbf{C}$ is finite, it has a least element $\bot$ and, by compatibility, this is also the least element of $\langle C, \sqsubseteq \rangle$. That is, $x \bot = \bot = \bot x$ for all $x \in C$. Since $\mathbf{C}$ also satisfies $x(y\vee z) = xy\vee xz$ for all $x,y,z\in C$, it follows immediately that the product is residuated. $\square$

As a consequence of this theorem, counting the commutative idempotent residuated chains of size $n\ge 2$, up to isomorphism, amounts to counting the different compatible total orders $\sqsubseteq$ on a chain of size n.

Theorem 3.2

There are $2^{n-2}$ commutative idempotent residuated chains of size $n\ge 2$.

Proof

We determine the number of compatible orderings on a fixed chain $\langle C,\le \rangle$ of size n. The choice of the greatest element ${\mathrm e}$ of $\sqsubseteq$ is arbitrary, except that it cannot be the least element. Hence there are $n-1$ choices for ${\mathrm e}$. For each choice, consider the interval $({\mathrm e},\top ] = \{x\in C : {\mathrm e}< x\le \top \}$ with k elements, and $(\bot ,{\mathrm e}) = \{x\in C : \bot< x < {\mathrm e}\}$ with $n-2-k$ elements.

Because of the compatibility conditions, the elements of $({\mathrm e},\top ]$ appear in the chain $\langle C,\sqsubseteq \rangle$ in the opposite order, while the elements of $(\bot ,{\mathrm e})$ appear in the same order. As the positions for ${\mathrm e}$ and $\bot$ are fixed in $\langle C,\sqsubseteq \rangle$, all we need to determine is the number of ways of interlayering two sequences of k and $n-2-k$ elements. But this is completely determined by the k places that the elements $(e,\top ]$ occupy in the resulting sequence of $n-2$ elements. So there are $\left( {\begin{array}{c}n-2\\ k\end{array}}\right)$ possibilities, and the number of compatible monoidal structures is

$$\begin{aligned} \sum _{k=0}^{n-2}\left( {\begin{array}{c}n-2\\ k\end{array}}\right) = 2^{n-2}. \end{aligned}$$

$\square$

We now provide a more symmetric version of a representation theorem of Raftery [21] that describes the structure of all commutative idempotent residuated chains, not just the finite ones. Instead of dividing just the negative cone of such an algebra into a family of (possibly empty) intervals indexed by the positive elements, as is the case in [21], both negative and positive cones are divided into families of nonempty intervals with greatest elements that together form a subalgebra.

Recall first (see, e.g., [9]) that for any residuated lattice $\mathbf{A}$ and $a\in A$, the map $\gamma _a :A\rightarrow A$ mapping x to $(a{/}x){\backslash }a$ is a closure operator on $\langle A, \le \rangle$ satisfying $y\cdot \gamma _a(x) \le \gamma _a(y\cdot x)$. Moreover, when $\mathbf {A}$ is commutative, the map $\gamma _a$ is a nucleus on $\langle A, \le \rangle$ and the algebra $\mathbf{A}_{\gamma _a}=\langle A_{\gamma _a},\wedge ,\vee _{\gamma _a},\cdot _{\gamma _a},\rightarrow ,\gamma _a({\mathrm e})\rangle$ with $A_{\gamma _a} = \{\gamma _a(b) : b \in A\}$, $b \vee _{\gamma _a} c = \gamma _a(b \vee c)$, and $b \cdot _{\gamma _a} c = \gamma _a(bc)$ is always a commutative residuated lattice. The next result concerns the particular case when $\mathbf{A}$ is a commutative idempotent residuated chain and $a = {\mathrm e}$. For convenience, we define ${\sim }x = x \rightarrow {\mathrm e}$.

Lemma 3.3

If $\mathbf{A}$ is a commutative idempotent residuated chain, then $\mathbf{A}_{\gamma _{\mathrm e}}$ is a subalgebra of $\mathbf{A}$, that we call its skeleton. Moreover, any homomorphism between commutative idempotent residuated chains restricts to a homomorphism between their skeletons.

Proof

Clearly, meets and residuals in $\mathbf{A}_{\gamma _e}$ agree with those in $\mathbf{A}$. Also $\gamma _{\mathrm e}({\mathrm e}) = {\sim }{\sim }{\mathrm e}= {\mathrm e}$. Moreover, for all $x,y\in A_{\gamma _{\mathrm e}}$, if $xy = x$, then $x\cdot _{\gamma _{\mathrm e}}y=\gamma _{\mathrm e}(xy) = \gamma _{\mathrm e}(x) = x$, and, similarly, if $xy = y$, then $x\cdot _{\gamma _{\mathrm e}}y = y$. Finally, since $\mathbf{A}$ is totally ordered, for all $x,y\in A_{\gamma _{\mathrm e}}$, either $x\vee y = x$ or $x\vee y = y$. In the first case, $x\vee _{\gamma _{\mathrm e}} y = \gamma _{\mathrm e}(x\vee y) = \gamma _{\mathrm e}(x) = x$, and in the second case, analogously, $x\vee _{\gamma _{\mathrm e}} y = y$. Hence $\mathbf{A}_{\gamma _{\mathrm e}}$ is a subalgebra of $\mathbf {A}$.

Finally, let $f:\mathbf{A}\rightarrow \mathbf{B}$ be any homomorphism between commutative idempotent residuated chains. For each $c\in A_{\gamma _{\mathrm e}}$, since $c = {\sim }{\sim }c$, also $f(c) = f({\sim }{\sim }c) = {\sim }{\sim }f(c) \in B_{\gamma _{\mathrm e}}$. $\square$

Proposition 3.4

For any commutative idempotent residuated chain $\mathbf{A}$:

• (a) $\mathbf{A}_{\gamma _{\mathrm e}}$ is a totally ordered odd Sugihara monoid.

• (b) For each $c\in A_{\gamma _{\mathrm e}}$, the set $A_c = \{x\in A : \gamma _{\mathrm e}(x)=c\}$ is an interval of $\mathbf{A}$ with greatest element c.

• (c) For all $x,y\in A$,

  • (i) If $x,y\in A_c$ for some $c\in A_{\gamma _{\mathrm e}}$ with $c\le {\mathrm e}$, then $xy = x\wedge y$.

  • (ii) If $x,y\in A_c$ for some $c\in A_{\gamma _{\mathrm e}}$ with ${\mathrm e}< c$, then $xy = x\vee y$.

  • (iii) If $x\in A_c, y\in A_{d}$ for some $c\ne d\in A_{\gamma _{\mathrm e}}$, then $xy=x \iff cd=c$.

• (d) For all $x,y\in A$ with $x\in A_c$ for some $c\in A_{\gamma _{\mathrm e}}$,

  $$\begin{aligned} x\rightarrow y = {\left\{ \begin{array}{ll} {\sim }c \vee y &{}\quad \text {if } x\le y,\\ {\sim }c \wedge y &{}\quad \text {if } y < x. \end{array}\right. } \end{aligned}$$

Proof

(a) $\mathbf{A}_{\gamma _{\mathrm e}}$ is a subalgebra of $\mathbf{A}$, and hence also a commutative idempotent residuated chain. But ${\sim }$ is an involution on $\mathbf{A}_{\gamma _{\mathrm e}}$ with fixpoint ${\mathrm e}$, so $\mathbf{A}_{\gamma _{\mathrm e}}$ is a totally ordered odd Sugihara monoid.

(b) Given $c\in A_{\gamma _{\mathrm e}}$ and $x\in A_c$, by definition, $x\le \gamma _{\mathrm e}(x) = c = \gamma _{\mathrm e}(c)$. Also, given $x,y\in A$ such that $x\in A_c$ and $x\le y \le c$, we have $c=\gamma _{\mathrm e}(x)\le \gamma _{\mathrm e}(y) \le \gamma _{\mathrm e}(c) = c$, and hence $\gamma _{\mathrm e}(y) = c$. That is, $y\in A_c$.

(c) Part (i) is immediate, since $x,y\in A_c$ and $c\le {\mathrm e}$ imply $xy\le {\mathrm e}$, and therefore $xy=x\wedge y$, by Lemma 2.1.(ii). For (ii), notice that ${\mathrm e}\in A_{\gamma _{\mathrm e}}$ and hence $x,y\in A_c$ and ${\mathrm e}<c$ imply that ${\mathrm e}<x,y$, and therefore $xy=x\vee y$, by Lemma 2.1.(ii). To prove (iii), we distinguish four cases. Assume that $\gamma _{\mathrm e}(x)=c\ne d=\gamma _{\mathrm e}(y)$ and, without loss of generality, $x<y$. If $x<y\le {\mathrm e}$, then $c =\gamma _{\mathrm e}(x) <\gamma _{\mathrm e}(y) = d\le {\mathrm e}$, and hence both $xy=x$ and $cd=c$. If ${\mathrm e}< x< y$, then ${\mathrm e}<c=\gamma _{\mathrm e}(x)<\gamma _{\mathrm e}(y)=d$, and both $xy = y$ and $cd = d$. If $x\le {\mathrm e}< y$ and $xy=x$, then $cd=\gamma _{\mathrm e}(x)\gamma _{\mathrm e}(y) \le \gamma _{\mathrm e}(xy) = \gamma _{\mathrm e}(x) = c\le {\mathrm e}$, so $cd = c$. Finally, if $x\le {\mathrm e}< y$ and $xy=y$, notice that ${\mathrm e}<y\le \gamma _{\mathrm e}(y)$, and therefore $y\gamma _{\mathrm e}(y) = y\vee \gamma _{\mathrm e}(y) = \gamma _{\mathrm e}(y)$. Hence

$$\begin{aligned} \gamma _{\mathrm e}(y) = y\gamma _{\mathrm e}(y) = xy\gamma _{\mathrm e}(y) = x\gamma _{\mathrm e}(y)\le \gamma _{\mathrm e}(x)\gamma _{\mathrm e}(y)\le \gamma _{\mathrm e}(xy)=\gamma _{\mathrm e}(y), \end{aligned}$$

yielding $cd=d$.

(d) We begin by showing that

$$\begin{aligned} x\rightarrow x = {\left\{ \begin{array}{ll}x &{}\quad \text {if } {\mathrm e}\le x,\\ {\sim }c &{}\quad \text {if } x\le {\mathrm e},\end{array}\right. } \end{aligned}$$

and hence, in both cases, $x\rightarrow x = {\sim }c\vee x$. Suppose first that $x\le {\mathrm e}$. Then $x\rightarrow x\le x\rightarrow {\mathrm e}$ and $c \le {\mathrm e}$. So $c({\sim }c) = c$ and, by part (c), $x(x\rightarrow {\mathrm e}) = x$, yielding $x\rightarrow {\mathrm e}\le x\rightarrow x$. Hence, $x\rightarrow x = x\rightarrow {\mathrm e}= {\sim }c$. Also, $x\le {\mathrm e}\le {\sim }c$, so ${\sim }c\vee x = {\sim }c$. Suppose next that ${\mathrm e}\le x$. Then $x\le a \in A$ implies $xa = a$, so $x\rightarrow x = x$. Also, ${\sim }c \le {\mathrm e}\le x$, so ${\sim }c\vee x = x$.

Now suppose that $x\le y$. Then

$$\begin{aligned} x({\sim }c \vee y) = x({\sim }c) \vee xy = x(x\rightarrow {\mathrm e})\vee xy \le x \vee y^2 = x \vee y = y. \end{aligned}$$

Hence ${\sim }c \vee y \le x\rightarrow y$. To establish equality, consider ${\sim }c \vee y< a \in A$. If $xa =x$, then $a\le x\rightarrow x = {\sim }c\vee x \le {\sim }c\vee y < a$, a contradiction. So $xa = a$. That is, $y < a = xa$, and $x\rightarrow y <a$.

Suppose finally that $y < x$. If $y < a \in A$, then $xa = x$ or $xa = a$, and, in both cases, $y< xa$. So $x\rightarrow y \le y$. We show that also $x\rightarrow y \le {\sim }c$. If $x\le {\mathrm e}$, this is clear because $x\rightarrow y \le x\rightarrow x = {\sim }c$. If ${\mathrm e}< x$ and $a \in A$ satisfies ${\sim }c < a$ and $xa = a$, then ${\mathrm e}\le a$ and $x \vee a = xa = a$; that is $y < x\le a$. So $x\rightarrow y \le {\sim }c$. Hence we have shown that $x\rightarrow y \le {\sim }c\wedge y$. Let us prove the other inequality. If $x\le {\mathrm e}$, then $y\le {\mathrm e}$ and $x({\sim }c\wedge y) \le xy = x \wedge y= y$ and ${\sim }c\wedge y \le x\rightarrow y$. Suppose that ${\mathrm e}\le x$ and hence $x({\sim }c) = {\sim }c \le {\mathrm e}$. If $y\le {\sim }c$, then $xy =y$ and $x({\sim }c\wedge y) \le xy = y$. If ${\sim }c \le y$, then $x({\sim }c\wedge y) \le x({\sim }c) ={\sim }c\le y$. Hence, in both cases, ${\sim }c\wedge y \le x\rightarrow y$.$\square$

Now let $\mathbf{S}$ be any totally ordered odd Sugihara monoid and let ${\mathcal {X}} = \{\langle X_c,\le _c\rangle : c\in S\}$ be a family of (disjoint) chains such that each $c\in S$ is the greatest element of $X_c$. We define for all $a,b \in S$ with $x\in X_{a}$ and $y\in X_{b}$,

$$\begin{aligned} x\preceq y\ \,:\Longleftrightarrow \, \ a < b\,\ \text { or }\,\ (a=b\, \text { and }\, x\le _{a} y). \end{aligned}$$

Then $\preceq$ is a total order on

$$\begin{aligned} S \otimes {\mathcal {X}} := \bigcup \{X_c : c \in S\}. \end{aligned}$$

We let $\wedge$ and $\vee$ be the meet and join operations for $\preceq$ and define the algebra

$$\begin{aligned} \mathbf {S} \otimes {\mathcal {X}} := \langle S \otimes {\mathcal {X}},\wedge ,\vee ,\cdot ,\rightarrow ,{\mathrm e}\rangle , \end{aligned}$$

where for $a,b \in S$ and $x\in X_{a},y\in X_{b}$,

$$\begin{aligned} x\cdot y = {\left\{ \begin{array}{ll} x \wedge y &{}\quad \text {if } a=b\le {\mathrm e},\\ x \vee y &{}\quad \text {if } {\mathrm e}<a=b,\\ x &{}\quad \text {if } a \ne b \text { and }ab=a,\\ y &{}\quad \text {if } a \ne b \text { and }ab=b,\\ \end{array}\right. } \quad \text { and }\quad x\rightarrow y = {\left\{ \begin{array}{ll} {\sim }a \vee y &{}\quad \text {if } x\le y,\\ {\sim }a \wedge y &{}\quad \text {if } y < x. \end{array}\right. } \end{aligned}$$

Theorem 3.5

(Cf. [21]). Let $\mathbf{S}$ be any totally ordered odd Sugihara monoid and let ${\mathcal {X}} = \{\langle X_c,\le _c\rangle : c\in S\}$ be a family of (disjoint) chains such that each $c\in S$ is the greatest element of $X_c$. Then $\mathbf {S} \otimes {\mathcal {X}}$ is a commutative idempotent residuated chain satisfying $\mathbf{S} = (\mathbf {S} \otimes {\mathcal {X}})_{\gamma _{\mathrm e}}$ and $(S \otimes {\mathcal {X}})_c = X_c$ for each $c\in S$. Moreover, every commutative idempotent residuated chain has this form.

Proof

The product on $\mathbf {S} \otimes {\mathcal {X}}$ is clearly commutative and conservative (and therefore idempotent), and extends the product of $\mathbf{S}$. Hence it suffices to check the following:

(a) The product is associative. For $x\in X_{a}$, $y\in X_{b}$, and $z\in X_{c}$, there are four cases:

• $a=b=c$. Then the product is either meet or join, both of which are associative operations.

• $a = b\ne c$. Either $ac=bc=a=b$ and $(xy)z = xy = x(yz)$, or $ac=bc=c$ and $(xy)z = z = xz = x(yz)$.

• $a = c \ne b$. This case is analogous to the previous case.

• a, b, c are distinct. In this case, both (xy)z and x(yz) are x, y, or z depending on whether $(ab)c = a(bc)$ is a, b, or c, respectively.

(b) ${\mathrm e}$is the unit of the product. Consider $x\in X_c$. Recall that ${\mathrm e}$ is the greatest element of the chain $\langle X_{\mathrm e},\le _{\mathrm e}\rangle$. Hence, if $c={\mathrm e}$, then ${\mathrm e}x = {\mathrm e}\wedge x = x$, and if $c\ne {\mathrm e}$, then ${\mathrm e}x = x$ since ${\mathrm e}c = c$.

(c) The product is monotone. Consider $x\in X_{a}$, $y\in X_{b}$, and $z\in X_{c}$ such that $y\preceq z$. First, if $b=c$, then $y\le _{b} z$, and we can distinguish the following cases: if ${\mathrm e}< a=b$, then $xy = x\vee y \le _{b} x\vee z = xz$; if $a=b\le {\mathrm e}$, then $xy = x\wedge y \le _{b} x\wedge z = xz$; if $a\ne b$ and $ab=a$, then $xy = x = xz$; if $a\ne b$ and $ab = b$, then $xy =y\le _{b} z = xz$. In all these cases, $xy\preceq xz$.

On the other hand, if $b < c$, then we have the following cases:

• a, b, c are distinct. If $ab = a$ and $ac = a$, then $xy = x =xz$. If $ab = a$ and $ac = c$, then it is easy to check that the only possibilities are $a\le b \le {\mathrm e}\le c$, $b\le {\mathrm e}\le a\le c$, or ${\mathrm e}\le b\le a\le c$, and in all three cases $a\le c$. So $xy = x\in X_{a}$ and $xz = z\in X_{c}$, yielding $xy\preceq xz$. Finally, if $ab=b$, then the monotonicity of the product of $\mathbf{S}$ yields $ac=c$, and hence $xy=y \preceq z = xz$.

• $a = b$. If ${\mathrm e}< a$, then ${\mathrm e}< c$ and so $ac = c$. Hence $xy\in X_{b}$ and $xz = z\in X_{c}$, so $xy\preceq xz$. If $a\le {\mathrm e}$, then $xy = x\wedge y \preceq xz$, by conservativity and the assumption that $y\preceq z$.

• $a = c$. If $a\le {\mathrm e}$, then $b < c=a\le {\mathrm e}$ and so $ab = b$. Hence $xy = y\in X_{b}$ and $xz\in X_{c}$, and therefore $xy\le xz$. If ${\mathrm e}< a$, then $xy \preceq x\vee z = xz$, by the conservativity and the assumption that $y\preceq z$.

(d) $xy\le x \iff y\le x\rightarrow x$ for all $x,y\in A$. Suppose that $x\in X_c$. If $x\le {\mathrm e}$, then $c\le {\mathrm e}\le {\sim }c$ and ${x\rightarrow x} = {\sim }c \vee x = {\sim }c$; it follows that $c({\sim }c) = c$ and $x(x\rightarrow x) = x({\sim }c) = x$. If ${\mathrm e}< x$, then ${\mathrm e}< c$, and so ${\sim }c\le {\mathrm e}\le x$. Hence $x\rightarrow x = {\sim }c \vee x = x$, so $x(x\rightarrow x) = xx = x$. In any case, $x(x\rightarrow x) = x$, and, by part (c), if $y\le x\rightarrow x$, then $xy \le x(x\rightarrow x) = x$.

Now, if $y\in X_{c'}$ is such that ${\sim }c \vee x < y$, we can distinguish again the following cases: If $x\le {\mathrm e}$, then ${\mathrm e}\le {\sim }c \le c'$, so $cc' = c'$, and therefore $x < y = xy$. If ${\mathrm e}< x$, then ${\mathrm e}< c \le c'$, so $cc' = c'$. So if $c=c'$, then $x < y = x\vee y =xy$, and if $c\ne c'$, then $x < y = xy$. We have proved that $xy\le x$ implies $y\le x\rightarrow x$.

(e) The residuation property. Let $x\in X_c$ be an arbitrary element of A and consider the following cases:

• $x\le y$. Given that the order is total, either $x({\sim }c \vee y) = x({\sim }c)$ or $x({\sim }c \vee y) = xy$. In both cases, $x({\sim }c \vee y)\le y$. Now, if ${\sim }c \vee y < z$, then ${\sim }c \vee x < z$, that is, $x\rightarrow x < z$, so $xz\ne x$, by part (d). Hence $y < z = xz$. It follows that $xz\le y \iff z\le x\rightarrow y$.

• $y < x$. First, if $x\le {\mathrm e}$, we have $y\le {\mathrm e}$, and therefore by part (c), $x({\sim }c\wedge y) \le xy = x\wedge y = y$. On the other hand, if ${\mathrm e}< x$, then $x({\sim }c) = {\sim }c \le {\mathrm e}$. If $y\le {\sim }c$, then $xy =y$ and, as before, $x({\sim }c\wedge y) \le xy = y$. Finally, if ${\sim }c \le y$, then $x({\sim }c\wedge y) \le x({\sim }c) ={\sim }c\le y$. In either case, $x({\sim }c\wedge y) \le y$. Hence, by part (c), $z\le x\rightarrow y$ implies $xz\le y$. Suppose now that ${\sim }c\wedge y < z$. If $y\le {\sim }c$, then $y = {\sim }c\wedge y <z$, and by conservativity, $y < xz$. On the other hand, if ${\sim }c < y$, then ${\sim }c = {\sim }c \wedge y <z$. Notice that if $x\le {\mathrm e}$, then $y< x \le {\mathrm e}\le {\sim }c < y$, which is impossible. So ${\mathrm e}<x$ and ${\sim }c\le {\mathrm e}$. Hence $xz = z$ implies $x\le z\le c$. By conservativity, $y < xz$. Hence also $xz \le y$ implies $z\le x\rightarrow y$. $\square$

The preceding theorem can be used (as in [21]) to prove the following local finiteness result.

Corollary 3.6

([21]). The variety of semilinear commutative idempotent residuated lattices is locally finite.

Proof

We recall first the following well-known criterion for local finiteness (see [21] for a proof): a variety ${\mathsf {V}}$ of finite type is locally finite if there exists a function $f :{\mathbb {N}} \rightarrow {\mathbb {N}}$ such that for all $n\in {\mathbb {N}}$, every n-generated subdirectly irreducible algebra in ${\mathsf {V}}$ has at most f(n) elements.

Consider any commutative idempotent residuated chain $\mathbf{A}$ and $Y\subseteq A$. By Theorem 3.5, $\mathbf{A}$ decomposes into a totally ordered odd Sugihara monoid $\mathbf{S}$ and a family of chains $\{\langle X_c,\le _c\rangle : c\in S\}$. Let

$$\begin{aligned} S' = \{\gamma _{\mathrm e}(a) : a\in Y\} \cup \{{\sim }\gamma _{\mathrm e}(a) : a\in Y\} \cup \{{\mathrm e}\}. \end{aligned}$$

Notice that $S'$ forms a subuniverse of $\mathbf{S}$. Consider also for each $c \in S'$, the set $X'_c = (X_c \cap Y) \cup \{c\}$ totally ordered by the restriction $\le _c'$ of $\le _c$. It is easy to check that the commutative idempotent residuated chain constructed from $S'$ and the family $\{\langle X'_c,\le _c\rangle : c\in S'\}$ is a subalgebra $\mathbf{A}'$ of $\mathbf{A}$ containing Y. Moreover, if $|Y|=n$, then $|S'| \le 2n+1$ and $|X_c'| \le n$ for each $c\in S'$. Hence $|A'| \le (2n+1)n$. The result now follows directly using the criterion. $\square$

4 Idempotent residuated chains

We turn our attention now to the more general case of idempotent residuated chains. Since the monoidal preorder of such an algebra $\mathbf{A}$ is not a partial order in general, we define for $x,y \in A$,

We also say that $x\in A$ is central if it commutes with every other element of $\mathbf{A}$, i.e., $xy = yx$ for all $y\in A$. The following lemma describes the properties of elements of $\mathbf {A}$ that are central and non-central (cf. [5, Proposition 3.1]).

Lemma 4.1

For any idempotent residuated chain $\mathbf{A}$, if two elements do not commute, then they have different signs. Moreover, for each $x\in A$, there are three distinct possibilities:

• (1) x is central and for all $y\in A$, either $x\sqsubseteq y$ or $y\sqsubseteq x$, and .

• (2) x is not central, there is a unique $y\in A$ such that x and y do not commute, and .

• (3) x is not central, there is a unique $y\in A$ such that x and y do not commute, and $x\parallel y$.

Proof

By Lemma 2.1, elements in the positive cone commute with each other and the same is true of elements in the negative cone. Hence, if $xy \ne yx$, then x and y must have different signs.

We now consider any $x\in A$. Suppose first that x is central. Then for all $y\in A$, either $xy = x$ and then $x\sqsubseteq y$, or $xy = y$ and then $yx=xy=y$, that is, $y\sqsubseteq x$. Also, if , then $x = xy = yx = y$. So (1) holds. Suppose now that x is not central. Then there exists $y \in A$ such that $xy\ne yx$. Moreover, since $\mathbf {A}$ is conservative, $xy=x$ or $xy = y$. We consider these two cases separately:

• $xy = x$. Then $yx = y$, so $x\sqsubseteq y$ and $y\sqsubseteq x$, i.e., . If $z \in A$ is another element that does not commute with x, then again and, by the transitivity of , also . Since y and z both have different signs to x, they have the same sign and $y=z$. So (2) holds. Moreover, in this case, there is no $z\in A$ such that $x\parallel z$. If this were the case, then y and z would have the same sign and either $z\le y$ and $z = xz \le xy = x = zx \le yx = y$, or $y \le z$ and $y = yx \le zx = x = xy \le xz = z$, contradicting the fact that x has a different sign to both z and y.

• $xy = y$. Then also $yx= x$, i.e., $x\parallel y$. If $z \in A$ is another element such that $x\parallel z$, then $xz = z$ and $zx = x$. Notice that

  $$\begin{aligned} y = xy = yxy = yzxy = yxzxy = xzxy = xzy = zy. \end{aligned}$$

  Since y and z have the same sign, they commute, and hence $y = yz$, that is, $y\sqsubseteq z$. By a symmetrical argument, , and since y and z have the same sign, $y=z$. So (3) holds. $\square$

Following this last lemma, let us fix for any element a of an idempotent residuated chain $\mathbf{A}$, the element $a^\sharp$ to be a, if a is central, and otherwise, the only element of $\mathbf{A}$ that does not commute with a. Notice that in both cases $(a^\sharp )^\sharp = a$. If a is not central, we call $\{a,a^\sharp \}$ a noncommuting pair.

Lemma 4.2

For any idempotent residuated chain $\mathbf{A}$, $a\in A$, and $x\in A\setminus \{a,a^\sharp \}$,

$$\begin{aligned} a\sqsubseteq x \iff a^\sharp \sqsubseteq x \quad \text {and}\quad x\sqsubseteq a \iff x\sqsubseteq a^\sharp . \end{aligned}$$

Proof

We will prove only the first part, since the second is analogous. We distinguish two cases: and $a\parallel a^\sharp$. Suppose first that . If $a\sqsubseteq x$, then $a^\sharp \sqsubseteq a\sqsubseteq x$, so $a^\sharp \sqsubseteq x$. Since $(a^\sharp )^\sharp = a$, this also proves that $a^\sharp \sqsubseteq x$ implies $a\sqsubseteq x$. Suppose now that $a\parallel a^\sharp$. Then $x\in A\setminus \{a,a^\sharp \}$ commutes with both a and $a^\sharp$, and is hence $\sqsubseteq$-comparable with them. If $a\sqsubseteq x$ and $x\sqsubseteq a^\sharp$, then $a\sqsubseteq a^\sharp$, contradicting $a\parallel a^\sharp$. Hence $a\sqsubseteq x$ if and only if $a^\sharp \sqsubseteq x$. $\square$

We now identify properties of the monoidal preorder, analogously to the commutative case, and show that in the finite setting these properties provide a complete description of the algebra. First, let us say that a preorder $\sqsubseteq$ on a set A is laced if

• 1. it has a (unique) greatest element ${\mathrm e}$;

• 2. each $a\in A$ is either comparable with all the other elements and we fix $a^\sharp = a$, or there is a unique element $a^\sharp$ such that or $a\parallel a^\sharp$;

• 3. for all $a\in A$ and $x\in A\setminus \{a,a^\sharp \}$,

  $$\begin{aligned} a\sqsubseteq x \iff a^\sharp \sqsubseteq x\quad \text {and}\quad x\sqsubseteq a \iff x\sqsubseteq a^\sharp . \end{aligned}$$

Now let $\mathbf {C} = \langle C,\le \rangle$ be any chain. We say that a laced preorder $\sqsubseteq$ on C is compatible with $\mathbf {C}$ if

• 1. any least element of $\mathbf {C}$ is also the least element of $\sqsubseteq$;

• 2. for all $x,y\in C$, if ${\mathrm e}\le x,y$, then $x\le y \iff y\sqsubseteq x$;

• 3. for all $x,y\in C$, if $x, y\le {\mathrm e}$, then $x\le y \iff x\sqsubseteq y$;

• 4. for each $x\in C$, if $x\ne x^\sharp$, then ${\mathrm e}\le x \iff x^\sharp \le {\mathrm e}$.

Theorem 4.3

• (a) The monoidal preorder $\sqsubseteq$ of any idempotent residuated chain $\mathbf {A}$ is laced and compatible with $\langle A,\le \rangle$.

• (b) For any chain $\mathbf {C}=\langle C,\wedge ,\vee \rangle$ and compatible laced preorder $\sqsubseteq$ on $\mathbf {C}$, the algebra $\langle C,\wedge ,\vee ,\cdot ,{\mathrm e}\rangle$ is an idempotent totally ordered monoid, where

  $$\begin{aligned} x\cdot y = {\left\{ \begin{array}{ll} x &{}\quad \text {if } x\sqsubseteq y,\\ y &{}\quad \text {otherwise}, \end{array}\right. } \end{aligned}$$

  Moreover, if $\mathbf {C}$ is finite, then $\cdot$ has (uniquely determined) residuals ${\backslash }$ and ${/}$ and $\langle C,\wedge ,\vee ,\cdot ,{\backslash },{/},{\mathrm e}\rangle$ is an idempotent residuated chain.

Proof

Part (a) is an immediate consequence of Lemmas 4.1 and 4.2. For part (b), note first that, since $\sqsubseteq$ is reflexive and has greatest element ${\mathrm e}$, the product is idempotent and has neutral element ${\mathrm e}$. To prove associativity, we consider $x,y,z\in C$ and distinguish the following cases:

• If $x\sqsubseteq y$ and $y\sqsubseteq z$, then $x\sqsubseteq z$. So $(xy)z = xz = x = xy = x(yz)$.

• If $x\sqsubseteq y$ and $y\not \sqsubseteq z$, then $(xy)z = xz = x(yz)$.

• If $x\not \sqsubseteq y$ and $y\sqsubseteq z$, then $(xy)z = yz = y = xy = x(yz)$.

• If $x\not \sqsubseteq y$ and $y\not \sqsubseteq z$, then there are four subcases: $z\sqsubseteq y\sqsubseteq x$, $z \parallel y \sqsubseteq x$, $z\sqsubseteq y\parallel x$, $y\parallel x = z$. In the first three, we obtain $x\not \sqsubseteq z$ and hence $x(yz) = xz = z = yz = (xy)z$; in the last, $x(yz) = x(yx) = xx = x = yx = (xy)x = (xy)z$.

We check now that the product distributes over joins, which, since $\mathbf{C}$ is a chain, is equivalent to the monotonicity of the product. Suppose that $x,y,z\in C$ and $y\le z$. We distinguish the following cases:

• ${\mathrm e}\le x,y,z$ or $x,y,z\le {\mathrm e}$. Then the product is, respectively, the join or meet and the result follows immediately.

• $x\le {\mathrm e}\le y \le z$. Then $z\sqsubseteq y$ and $y\not \sqsubseteq z$. If $x\sqsubseteq z$, then $x\sqsubseteq y$ and so $xy = x = xz$. Otherwise, $x\not \sqsubseteq z$, so xy is x or y and hence $xy \le z = xz$. To prove $yx\le zx$, we proceed analogously, noting that if $z\not \sqsubseteq x$, then $yx = x = zx$, and if $z\sqsubseteq x$, then $yx \le z = zx$.

• $x,y \le {\mathrm e}\le z$. Then $xy = yx = x\wedge y$, so $xy \le x \le xz$ and $yx \le x \le zx$.

• $y\le {\mathrm e}\le x, z$. Then $xz = zx = x\vee z$, so $xy \le x \le xz$ and $yx \le x \le zx$.

• $y\le z\le {\mathrm e}\le x$. Then $y\sqsubseteq z$ and $z\not \sqsubseteq y$. If $x\sqsubseteq y$, then $x\sqsubseteq z$ and $xy = x = xz$. If $x\not \sqsubseteq y$, then $xy = y$, which is smaller than xz. For the other inequation, if $y\not \sqsubseteq x$, then $z\not \sqsubseteq x$ and then $yx = x = zx$. If $y\sqsubseteq x$, then $yx = y\le zx$.

In the case that $\mathbf{C}$ is finite, it has a least element $\bot$ and, by compatibility, this is also the least element of $\langle C, \sqsubseteq \rangle$. That is, $x \bot = \bot = \bot x$ for all $x \in C$. Since $\mathbf{C}$ also satisfies $x(y\vee z) = xy\vee xz$ for all $x,y,z\in C$, it follows immediately that the product is residuated. $\square$

We use this representation theorem to count the number of idempotent residuated chains of size $n\ge 2$ up to isomorphism.

Theorem 4.4

The number of idempotent residuated chains of size $n\ge 2$ is

$$\begin{aligned} \mathbf {I} (n) = \sum _{s=0}^{[\frac{n}{2}]-1} \sum _{t=0}^{[\frac{n}{2}]-1-s} 2^{n-2(1+s+t)}\left( {\begin{array}{c}n-2-s-t\\ n-2(1+s+t), s, t\end{array}}\right) . \end{aligned}$$

Proof

We determine the number of laced preorders that are compatible with a finite chain $\langle A,\le \rangle$ of size $n\ge 2$. Notice that, in every noncommuting pair, one of them will be positive and the other negative. Hence, up to isomorphism, which one is which is not relevant. Moreover, if we let $C=\{a\in A : a=a^\sharp \}$, then ${\sqsubseteq }\mathord {\upharpoonright }C^2$ is a compatible total order on the finite chain $\langle C,{\le }\mathord {\upharpoonright }C^2\rangle$. Hence it suffices to determine the relative positions of the noncommuting pairs and the compatible total preorder of the central elements.

Observe first that the greatest and least elements are fixed, so there are at most $m=n-2$ possible positions for the noncommuting pairs. Let s be the number of comparable noncommuting pairs, and t the number of incomparable (noncommuting) pairs. Then $0\le s\le \big [\frac{m}{2}\big ] = \big [\frac{n}{2}\big ]-1$ and $0\le t \le \big [\frac{m}{2}\big ] - s = \big [\frac{n}{2}\big ] - 1 - s$, and there are $r=n-2s-2t$ central elements. The number of total positions is $r-2 + s + t$. Hence there are $\left( {\begin{array}{c}r-2+s+t\\ s\end{array}}\right)$ possible choices for the positions of the comparable noncommuting pairs and $\left( {\begin{array}{c}r-2 + t\\ t\end{array}}\right)$ possible choices for the positions of the incomparable pairs. The number of compatible total orders is $2^{r-2}$, so the number of compatible laced preorders with s comparable noncommuting pairs and t incomparable pairs is

$$\begin{aligned} f(s,t) = 2^{r-2} \left( {\begin{array}{c}r-2+s+t\\ s\end{array}}\right) \left( {\begin{array}{c}r-2+t\\ t\end{array}}\right) = 2^{r-2}\left( {\begin{array}{c}r-2+s+t\\ r-2 + s + t,s,t\end{array}}\right) . \end{aligned}$$

Hence the number of compatible laced preorders is

$$\begin{aligned} \mathbf {I}(n)&= \sum _{s=0}^{[\frac{n}{2}]-1} \sum _{t=0}^{[\frac{n}{2}]-1-s} f(s,t)\\&= \sum _{s=0}^{[\frac{n}{2}]-1} \sum _{t=0}^{[\frac{n}{2}]-1-s} 2^{r-2}\left( {\begin{array}{c}r-2+s+t\\ r-2 + s + t,s,t\end{array}}\right) \\&= \sum _{s=0}^{[\frac{n}{2}]-1} \sum _{t=0}^{[\frac{n}{2}]-1-s} 2^{n-2(1+s+t)}\left( {\begin{array}{c}n-2-s-t\\ n-2(1+s+t), s, t\end{array}}\right) . \end{aligned}$$

$\square$

Theorem 4.5

The sequence $(\mathbf {I}(n) : n\ge 2)$ satisfies the recurrence formula $\mathbf {I}(2) = 1$, $\mathbf {I}(3) = 2$, $\mathbf {I}(n+2) = 2\mathbf {I}(n) + 2\mathbf {I}(n+1)$, and the number of idempotent residuated chains of size $n\ge 2$ is

$$\begin{aligned} \mathbf {I}(n) = \frac{\big (1+\sqrt{3}\,\big )^n - \big (1-\sqrt{3}\,\big )^n}{2\sqrt{3}}. \end{aligned}$$

Proof

It is easy to see that, up to isomorphism, there is only one idempotent residuated chain with 2 elements and only two with 3 elements: one in which the identity is the greatest element and one with a strictly positive element. For any compatible laced preorder on a chain $\langle A,\le \rangle$ with $n\ge 4$ elements, there are four possible cases:

• There is only one $\sqsubseteq$-cocover a of ${\mathrm e}$, and ${\mathrm e}< a$.

• There is only one $\sqsubseteq$-cocover a of ${\mathrm e}$, and $a < {\mathrm e}$.

• There are two $\sqsubseteq$-cocovers $a,a^\sharp$ of ${\mathrm e}$, and .

• There are two $\sqsubseteq$-cocovers $a,a^\sharp$ of ${\mathrm e}$, and $a\parallel a^\sharp$.

It is not difficult to prove that, removing the $\sqsubseteq$-cocovers of ${\mathrm e}$, we obtain a compatible laced preorder on a chain of $n-1$ elements in the first two cases, or a chain of $n-2$ elements in the last two cases.

Reciprocally, given a compatible laced preorder on a chain of size $n\ge 2$, we can add a $\sqsubseteq$-cocover of ${\mathrm e}$, which can be either positive or negative, or two $\sqsubseteq$-cocovers of ${\mathrm e}$, which can consist of comparable or incomparable elements. We obtain a compatible laced preorder on a chain with $n+1$ elements or $n+2$ elements, respectively. $\square$

Recall that the variety of semilinear commutative idempotent residuated lattices is locally finite ([21] and Corollary 3.6). This property fails, however, if semilinearity is weakened to distributivity or idempotence is weakened to being square-increasing, square-decreasing, or n-potent for $n \ge 3$ (see [21]). The next result shows that also commutativity plays an essential role.

Proposition 4.6

The variety of semilinear idempotent residuated lattices is not locally finite.

Proof

It suffices to exhibit an infinite idempotent residuated chain with a finite set of generators. Consider the set ${{\mathbb {Z}}}$ of integers with the standard order, and define $x\cdot y = x$ if $|x| \ge |y|$ and $x\cdot y = y$ otherwise. It is easy to see that this determines the unique structure of an idempotent residuated chain. Moreover, $x{\backslash }x = |x|$ for each $x \in {{\mathbb {Z}}}$, and if $x>0$, then $x{\backslash }0 = -x-1$. So we have $1 = |-1|$, $-2 = 1{\backslash }0$, $2 = |-2|$, $-3 = 2{\backslash }0$, etc. Also, $0 = (-1)/(-1)$. Hence $\{-1\}$ generates the whole algebra. $\square$

The variety of semilinear idempotent residuated lattices does have the finite embeddability property, however, as will be shown in Corollary 5.2.

5 Conservative residuated lattices

In the previous two sections, we have studied classes of idempotent residuated lattices that are totally ordered, i.e., classes satisfying the positive universal formula $(\forall x)(\forall y)(x\vee y \approx x \mathrel {\texttt {or}} x\vee y \approx y)$. In this section, we obtain similar results for classes of idempotent residuated lattices that are conservative, i.e., classes satisfying the positive universal formula $(\forall x)(\forall y)(xy \approx x \mathrel {\texttt {or}} xy \approx y)$. That is, we consider the variety ${\mathsf {CsRL}}$ generated by the class of conservative residuated lattices, noting that by congruence distributivity and Jónsson’s Lemma, every subdirectly irreducible member of $\mathsf {CsRL}$ is conservative and any subvariety of $\mathsf {CsRL}$ is generated by its conservative members.

We show first that any variety ${\mathsf {V}}$ generated by a class of conservative residuated lattices defined relative to ${\mathsf {IdRL}}$ by positive universal formulas in the language $\{\vee ,\cdot ,{\mathrm e}\}$ has the finite embeddability property: that is, any finite partial subalgebra of a member of ${\mathsf {V}}$ embeds into a finite member of ${\mathsf {V}}$.

Theorem 5.1

Let ${\mathsf {K}}$ be a class of conservative residuated lattices defined relative to ${\mathsf {IdRL}}$ by positive universal formulas in the language $\{\vee ,\cdot ,{\mathrm e}\}$. Then the variety ${\mathsf {V}}$ generated by ${\mathsf {K}}$ has the finite embeddability property.

Proof

It suffices to check that the finite embeddability property holds for the subdirectly irreducible members of ${\mathsf {V}}$. Hence, since ${\mathsf {K}}$ is a positive universal class, it suffices to show that any finite partial subalgebra $\mathbf {B}$ of some $\mathbf {A}\in {\mathsf {K}}$ embeds into a finite member of ${\mathsf {K}}$. Without loss of generality, we may also assume that ${\mathrm e}\in B$. First, we let

$$\begin{aligned} \top = \bigvee B, \quad B' = B \cup \{\top {\backslash }{\mathrm e}, {\mathrm e}{/}\top \}, \text {and }C = B' \cup \{a \wedge {\mathrm e}: a \in B'\}. \end{aligned}$$

Notice that C is finite, every element $a\in C$ is lower bounded by $a\wedge {\mathrm e}\in C \cap \mathord {\downarrow }{\mathrm e}$ and, by Lemma 2.5, $\langle C\cap \mathord {\downarrow }{\mathrm e},\le \rangle$ is a chain. Hence C has a least element $\bot$.

Now consider the join-subsemilattice $\langle C^*,\vee \rangle$ of $\langle A,\vee \rangle$ generated by C. The order induced by $\vee$ in $C^*$ is the restriction of the order $\le$ of $\mathbf{A}$. Since C is finite and has a least element, $\langle C^*,\le \rangle$ is a lattice with the same least element $\bot$. Moreover, by the conservativity of $\mathbf{A}$, the set $C^*$ is also the universe of a submonoid of $\langle A,\cdot ,{\mathrm e}\rangle$. That is, $\langle C^*,\vee ,\cdot ,{\mathrm e}\rangle$ is a subalgebra of $\langle A,\vee ,\cdot ,{\mathrm e}\rangle$ and hence every positive universal formula in the language $\{\vee ,\cdot ,{\mathrm e}\}$ that is valid in $\mathbf{A}$ is also valid in $\langle C^*,\vee ,\cdot ,{\mathrm e}\rangle$, in particular, the equations $x(y \vee z) \approx xy \vee xz$ and $(x \vee y)z \approx xz \vee yz$.

Observe next that ${\mathrm e}\le \top$, since ${\mathrm e}\in B$, and hence that $\top {\backslash }{\mathrm e}$ and ${\mathrm e}{/}\top$ are both negative. So $\top = \bigvee B = \bigvee B' = \bigvee C = \bigvee C^*$. If $\top = {\mathrm e}$, then $\bot \cdot \top = \bot = \top \cdot \bot$. Otherwise, ${\mathrm e}< \top$ and $\bot \cdot \top \le ({\mathrm e}/\top )\top \le {\mathrm e}< \top$ and hence, by conservativity, $\bot \cdot \top = \bot$; similarly, $\top \cdot \bot = \bot$. Hence, in both cases, $\bot \cdot a = \bot = a\cdot \bot$ for all $a \in C^*$. Since $\langle C^*,\vee ,\cdot ,{\mathrm e}\rangle$ also satisfies $x(y \vee z) \approx xy \vee xz$ and is finite, it follows that the product of $C^*$ has residuals given by $a{\backslash \backslash }b = \max \{c\in C^* : ac \le b\}$ and $a{//}b = \max \{c\in C^* : ca \le b\}$. It is then straightforward to see that if $a{\backslash }b\in B$, then $a{\backslash \backslash }b = a{\backslash }b$, and if $a{/}b\in B$, then $a{//}b = a{/}b$. Hence the partial algebra $\mathbf{B}$ embeds into $\langle C^*,\wedge ^{\mathbf{C}^*},\vee ,\cdot ,{\backslash \backslash },{//},{\mathrm e}\rangle \in {\mathsf {K}}$. $\square$

Corollary 5.2

${\mathsf {CsRL}}$, ${\mathsf {CCsRL}}$, and ${\mathsf {SemIdRL}}$ have the finite embeddability property.

Proof

The result follows directly from Theorem 5.1, since ${\mathsf {CsRL}}$, ${\mathsf {CCsRL}}$, and ${\mathsf {SemIdRL}}$ are generated by the classes of all conservative residuated lattices, commutative conservative residuated lattices, and conservative residuated lattices satisfying $(\forall x)(\forall y)(x\vee y \approx x \mathrel {\texttt {or}} x\vee y \approx y)$, respectively. $\square$

Let us turn our attention now to the variety $\mathsf {CCsRL}$ generated by the class of commutative conservative residuated lattices. As has just been shown, this variety has the finite embeddability property and is therefore generated by its finite members. Also, any finite commutative conservative residuated lattice is subdirectly irreducible, since its negative cone is a finite chain of (central) idempotents. The class ${\text {Si}}({\mathsf {CCsRL}})_ fin$ of finite subdirectly irreducible members of $\mathsf {CCsRL}$ therefore consists of all finite commutative conservative residuated lattices and generates ${\mathsf {CCsRL}}$. Moreover, using Mace4 [16], it can be shown that there are 1, 2, 5, 14, 42, 132, 429, 1430, 4862, and 16796 such algebras of size 2 to 11, respectively. As we show below, it is no accident that this sequence corresponds exactly to the Catalan numbers $C_n=\frac{1}{n+1}\left( {\begin{array}{c}2n\\ n\end{array}}\right)$.

We first define a binary operation on ${\text {Si}}({\mathsf {CCsRL}})_ fin$, which we call the Catalan sum, and show that the resulting algebra is uniquely determined up to isomorphism by its two summands. For $\mathbf{A},\mathbf{B}\in {\text {Si}}(\mathsf {CCsRL})_ fin$, we define an algebra $\mathbf{C}=\mathbf{A}\mathbin {\copyright }\mathbf{B}$ as follows. We let C be the disjoint union of A and B and define a lattice order

$$\begin{aligned} {\le ^\mathbf{C}}={\le ^\mathbf{A}}\cup {\le ^\mathbf{B}}\cup (\{\bot ^\mathbf{A}\}\times B)\cup (A\times \mathord {\uparrow }{\mathrm e}^\mathbf{B}). \end{aligned}$$

To specify $\cdot ^\mathbf{C}$, it suffices to define the following monoidal order:

$$\begin{aligned} {\sqsubseteq ^\mathbf{C}}={\sqsubseteq ^\mathbf{A}}\cup {\sqsubseteq ^\mathbf{B}}\cup (\{\bot ^\mathbf{A}\}\times B)\cup (B\times (A\setminus \{\bot ^\mathbf{A}\})). \end{aligned}$$

Informally, the monoidal order of $\mathbf{C}$ is the ordinal sum $\{\bot ^\mathbf{A}\}\oplus \langle B,\sqsubseteq \rangle \oplus \langle A\setminus \{\bot ^\mathbf{A}\},\sqsubseteq \rangle$. Since the greatest element is always the identity, it follows that if $\mathbf{A}$ is nontrivial, then ${\mathrm e}^\mathbf{C}={\mathrm e}^\mathbf{A}$ and otherwise ${\mathrm e}^\mathbf{C}={\mathrm e}^\mathbf{B}$. The lattice order implies that $\bot ^\mathbf{A}$ is the least element of $\mathbf{C}$, and that $a\vee b={\mathrm e}^\mathbf{B}\vee b$ whenever $a\in A\setminus \{\bot ^\mathbf{A}\}$ and $b\in B$. Note also that if $\mathbf{A}$ or $\mathbf{B}$ is a one element algebra, then the underlying lattice of $\mathbf{C}$ is simply the ordinal sum of the lattices of $\mathbf{A}$ and $\mathbf{B}$ (see Figure 2).

Fig. 2

The Catalan sum $\mathbf{C}=\mathbf{A}\mathbin {\copyright }\mathbf{B}$, for nontrivial $\mathbf{A}$

Lemma 5.3

If $\mathbf{A},\mathbf{B}\in {\text {Si}}({\mathsf {CCsRL}})_ fin$, then $\mathbf{A}\mathbin {\copyright }\mathbf{B}\in {\text {Si}}({\mathsf {CCsRL}})_ fin$.

Proof

Let $\mathbf{C} = \mathbf{A}\mathbin {\copyright }\mathbf{B}$. It is straightforward to check that $\langle C,\le ^\mathbf{C}\rangle$ is a lattice. By assumption, $\mathbf{A}$ and $\mathbf{B}$ have total monoidal orders, so by definition the same holds for $\sqsubseteq ^\mathbf{C}$. Hence $\sqsubseteq ^\mathbf{C}$ determines a unique commutative monoidal operation. Since $\mathbf{A},\mathbf{B}$ are finite and the least element of $\langle C,\le ^\mathbf{C}\rangle$ is also the least element of $\langle C,\sqsubseteq ^\mathbf{C}\rangle$, to show that $\mathbf{C}$ is a residuated lattice, it suffices to check that $x(y\vee z)=xy\vee xz$ for all $x,y,z\in C$. Note that $\{\bot ^\mathbf{A}\}\cup B$ and A are both closed under $\cdot ^\mathbf{C}$ and $\vee ^\mathbf{C}$, hence the identity holds when $x,y,z\in B\cup \{\bot ^\mathbf{A}\}$ or $x,y,z\in A$, and we now check the remaining six cases.

• $x\in A\setminus \{\bot ^\mathbf{A}\}$, $y,z\in B$: From the definition of $\sqsubseteq ^\mathbf{C}$, we have $y,z,y\vee ^\mathbf{B} z\sqsubseteq ^\mathbf{C} x$ and hence $x(y\vee z)=y\vee z=xy\vee xz$.

• $y\in A\setminus \{\bot ^\mathbf{A}\}$, $x,z\in B$: In this case $x\sqsubseteq ^\mathbf{C} y$ and $y\vee z={\mathrm e}^\mathbf{B}\vee z$, so $x(y\vee z)=x({\mathrm e}^\mathbf{B}\vee z)=x\vee xz=xy\vee xz$. The case $z\in A\setminus \{\bot ^\mathbf{A}\}$, $x,y\in B$ is similar.

• $x,y\in A\setminus \{\bot ^\mathbf{A}\}$, $z\in B$: In this case $y\vee z={\mathrm e}^\mathbf{B}\vee z\sqsubseteq ^C x$ and $xy\in A\setminus \{\bot ^\mathbf{A}\}$, so $x(y\vee z)=y\vee z={\mathrm e}^\mathbf{B}\vee z$ and $xy\vee xz=xy\vee z={\mathrm e}^\mathbf{B}\vee z$. The case $x,z\in A\setminus \{\bot ^\mathbf{A}\}$, $y\in B$ is similar.

• $y,z\in A\setminus \{\bot ^\mathbf{A}\}$, $x\in B$: In this case $x\sqsubseteq ^C y,z,y\vee z$, so $x(y\vee z)=x=x\vee x=xy\vee xz$.

The algebra $\mathbf{C}$ is subdirectly irreducible since its negative cone, which is also the negative cone of $\mathbf{A}$, is a finite chain of central idempotents. $\square$

We now prove a converse to the preceding lemma.

Lemma 5.4

Suppose that $\mathbf{C}\in {\text {Si}}({\mathsf {CCsRL}})_ fin$ has size $n\ge 2$. Then $\mathbf{C}=\mathbf{A}\mathbin {\copyright }\mathbf{B}$ for a pair $\mathbf{A},\mathbf{B}\in {\text {Si}}({\mathsf {CCsRL}})_ fin$ that is unique up to isomorphism.

Proof

Since $\mathbf{C}$ is finite, commutative, and conservative, the semilattice order $\sqsubseteq ^\mathbf{C}$ is a chain. Let $b\in C$ be the unique atom of this chain. The sets A, B are defined by $B=\mathord {\uparrow }b=\{x\in C:b\le x\}$ and $A=C\setminus B$. The operations $\wedge ,\vee ,\cdot$ are defined on A and B by restriction from $\mathbf{C}$. To ensure that these operations are total, we need to prove that both A and B are closed under the operations on $\mathbf{C}$. This is obvious for the conservative operation $\cdot$. Moreover, since B is a filter, it is the universe of a sublattice. The set A is closed under meets since it is the complement of a filter. Suppose now that $b\le x\vee y$ and $x\ne \bot ^\mathbf{C} \ne y$. If $xy = x$, then $b = xb \le x^2\vee xy = x \vee x = x$; analogously, if $xy = y$, then $b\le y$. If $x = \bot ^\mathbf{C}$, then $b \le x \vee y = y$; and if $y = \bot ^\mathbf{C}$, then $b\le x$. So if $x\vee y\in \mathord {\uparrow }b$, then $x\in \mathord {\uparrow }b$ or $y\in \mathord {\uparrow }b$; that is, A is closed under $\vee$.

Let us show that B is an interval of $\langle C,\sqsubseteq \rangle$. If $b\sqsubseteq b'' \sqsubseteq b'$ and $b'\in B$, then $b\le b'$ implies that $b = b'' b \le b'' b' = b''$, and therefore $b''\in B$. Since C is finite, $B = [b,c]_{\sqsubseteq }$ for some $c\in C$. Hence, for every $x\in B$ we have that $cx = x$. That is, c is the identity on B. Notice also that $cb = b\le c$ implies $b\le c{\backslash }c$, that is, $c{\backslash }c \in B$. So $c{\backslash }c = c(c{\backslash }c) \le c$. By idempotence, $cc\le c$, and hence $c\le c{\backslash }c$. So $c = c{\backslash }c$. If ${\mathrm e}^\mathbf{C}\in B$, then $c = {\mathrm e}^\mathbf{C}$ and $A=\{\bot ^\mathbf{A}\}$. Otherwise, ${\mathrm e}^\mathbf{C}$ is the identity on A.

If $x\in A\setminus \{\bot ^\mathbf{C}\}$, then $cx = c$, yielding $x\le c{\backslash }c = c$. Clearly also $\bot ^\mathbf{C} \le c$. Given $x\in A\setminus \{\bot ^\mathbf{C}\}$ and $y\in B$, if $x\le y$, we have that $c = cx \le cy = y$. So c is the cover of A in $\mathbf{C}$ if $A\ne \{\bot ^\mathbf{C}\}$. If $A = \{\bot ^\mathbf{A}\}$, then b is the cover of A in $\mathbf{C}$.

For $y\in B$ and $x\in A\setminus \{\bot ^\mathbf{C}\}$, we have $x\le x\vee y\in B$. Hence $c\le x\vee y$ and $c\vee y\le x\vee y$. Since also $x\le c$, we have $x\vee y \le c\vee y$. So $x\vee y = c\vee y$.

Finally, if $\bot< x < b$, then $x\in A$, and hence $c = xc\le bc = b \le c$. That is, $\mathord {\uparrow }b = \{b\}$, which implies $b = \top ^\mathbf{C}$. So b is an atom of $\mathbf{C}$, unless $b = \top ^\mathbf{C}$.

We have shown that $\mathbf{A}$ and $\mathbf{B}$ are commutative conservative residuated lattices. Moreover, by Lemma 2.5, their negative cones are finite chains of central idempotents, so both are subdirectly irreducible. The proof concludes with the observation that $\mathbf{C}=\mathbf{A}\mathbin {\copyright }\mathbf{B}$ by definition of the Catalan sum. $\square$

Let us call an algebra Catalan if it is a one element algebra (in the language of residuated lattices) or a Catalan sum of Catalan algebras. In particular, if $\mathbf{C}^1_1$ is a one element algebra, then $\mathbf{C}^2_1=\mathbf{C}^1_1\mathbin {\copyright }\mathbf{C}^1_1$ is the two element Boolean algebra. The two three element chains are $\mathbf{C}^3_1=\mathbf{C}^1_1\mathbin {\copyright }\mathbf{C}^2_1$ and $\mathbf{C}^3_2=\mathbf{C}^2_1\mathbin {\copyright }\mathbf{C}^1_1$. In general, the algebras of size n are built by constructing all Catalan sums of algebras $\mathbf{A}$ and $\mathbf{B}$ of size $n-k$ and k respectively, as k ranges from 1 to $n-1$ (see Figure 2). The following characterization theorem is now an immediate consequence of Lemmas 5.3 and 5.4

Theorem 5.5

The class of finite conservative commutative residuated lattices is precisely the class of Catalan algebras.

This yields the following result.

Theorem 5.6

The number of conservative commutative residuated lattices of $n\ge 1$ elements is $\mathbf {C}(n) = \frac{1}{n}\left( {\begin{array}{c}2(n-1)\\ n-1\end{array}}\right)$, that is, the $(n-1)$th Catalan number.

Proof

We will prove the result by induction. The sequence $(C_i : i\ge 0)$ of Catalan numbers is determined by $C_0 = 1$ and $C_{n+1} = \sum _{i=0}^n C_iC_{n-i}$. Obviously, $\mathbf {C}(1) = 1 = C_0$. Suppose now that $n>1$. Using Lemmas 5.3 and 5.4 and the induction hypothesis,

$$\begin{aligned} \mathbf {C}(n+1)&= \sum _{k=1}^{n} \mathbf {C}(k)\cdot \mathbf {C}(n+1-k)\\&= \sum _{k=1}^{n} C_{k-1}C_{n-k}\\&= \sum _{i=0}^{n-1}C_iC_{n-1-i} = C_{n-1}. \end{aligned}$$

$\square$

6 The amalgamation property

For the purposes of this paper, a span of a class of algebras ${\mathsf {K}}$ is a pair of embeddings $\langle i_1:\mathbf{A}\hookrightarrow \mathbf{B}, i_2:\mathbf{A}\hookrightarrow \mathbf{C}\rangle$ between algebras $\mathbf{A},\mathbf{B},\mathbf{C}\in {\mathsf {K}}$. The class ${\mathsf {K}}$ is said to have the amalgamation property if for every span of ${\mathsf {K}}$, there exist $\mathbf{D}\in {\mathsf {K}}$ and embeddings $j_1:\mathbf{B}\hookrightarrow \mathbf{D}$ and $j_2:\mathbf{C}\hookrightarrow \mathbf{D}$ such that the following diagram commutes:

In this section, we prove that both the variety of semilinear commutative idempotent residuated lattices and a noncommutative variety of idempotent residuated lattices have the amalgamation property. Our main tools will be the characterization of commutative idempotent residuated chains provided by Theorem 3.5 and the following criterion for amalgamation in varieties of semilinear residuated lattices obtained in [18].

Theorem 6.1

([18]). Let ${\mathsf {V}}$ be a variety of semilinear residuated lattices with the congruence extension property, and let ${\mathcal {T}}$ be the class of finitely generated totally ordered members of ${\mathsf {V}}$. If every span in ${\mathcal {T}}$ has an amalgam in ${\mathsf {V}}$, then ${\mathsf {V}}$ has the amalgamation property.

Let us begin by considering the special case of odd Sugihara monoids.

Lemma 6.2

([8]). Given any chain $\langle C,\le \rangle$ and order-preserving involution ${\sim }$ on C with fixpoint ${\mathrm e}\in C$, define for $x,y \in C$,

$$\begin{aligned} x\cdot y := {\left\{ \begin{array}{ll} x \wedge y &{} \text {if } x \le {\sim }y,\\ x \vee y &{} \text {if } x > {\sim }y,\\ \end{array}\right. } \qquad \text {and}\qquad x\rightarrow y := {\left\{ \begin{array}{ll} {\sim }x\vee y &{} \text {if } x \le y,\\ {\sim }x \wedge y &{} \text {if } y < x.\\ \end{array}\right. } \end{aligned}$$

Then $\langle C,\wedge ,\vee ,\cdot ,\rightarrow ,{\mathrm e}\rangle$ is a totally ordered odd Sugihara monoid.

Lemma 6.3

The class of totally ordered odd Sugihara monoids has the amalgamation property.

Proof

Consider a span $\langle i_1:\mathbf{A}\hookrightarrow \mathbf{B}, i_2:\mathbf{A}\hookrightarrow \mathbf{C}\rangle$ of totally ordered odd Sugihara monoids, assuming without loss of generality that $i_1$ and $i_2$ are inclusion maps and that $B \cap C = A$. Let $A^-$, $B^-$, and $C^-$ denote the negative cones of $\mathbf {A}$, $\mathbf {B}$, and $\mathbf {C}$ with induced total orders $\le _A$, $\le _B$, and $\le _C$, respectively. We fix $S = A^- \cup B^-$ and let $\le _S$ be any total order extending $\le _B$ and $\le _C$.

Now consider the set $D=B\cup C$ and the map ${\sim }:D\rightarrow D$ given by ${\sim }^{\mathbf{B}}\cup {\sim }^{\mathbf{C}}$, recalling that ${\sim }x := x \rightarrow {\mathrm e}$. We also define $x \le _D y$ if and only if (i) $x,y \in S$ and $x \le _S y$, (ii) $x \in S$, $y \in D\setminus S$, or (iii) $x,y \in D\setminus S$ and ${\sim }y \le _S {\sim }x$. It is easy to check that $\le _D$ is a total order on D extending both $\le _B$ and $\le _C$, and that $S = \{x\in D : x\le _D {\mathrm e}\}$. Moreover, ${\sim }$ is an order-preserving involution on D with fixpoint ${\mathrm e}$. Hence by Lemma 6.2, we obtain a totally odd ordered Sugihara monoid $\mathbf{D}=\langle D,\wedge ,\vee ,\cdot ,\rightarrow ,{\mathrm e}\rangle$. Since the order of $\mathbf{D}$ and the map ${\sim }$ extend the orders and involutions of $\mathbf{B}$ and $\mathbf{C}$, it follows that $\mathbf{B}$ and $\mathbf{C}$ are subalgebras of $\mathbf{D}$, and hence that $\mathbf{D}$ is the required amalgam. $\square$

Since the variety ${\mathsf {OSM}}$ of odd Sugihara monoids has the congruence extension property, an application of Theorem 6.1 yields the following result, proved using model-theoretic methods in [15] as part of a full classification of varieties of Sugihara monoids with the amalgamation property.

Corollary 6.4

(Cf. [15]). The variety of odd Sugihara monoids has the amalgamation property.

Note that this last result also follows from the fact that ${\mathsf {OSM}}$ and the variety of relative Stone algebras are categorically equivalent and the latter has the amalgamation property, as shown in [10] and [14], respectively. Let us also mention that ${\mathsf {OSM}}$ is locally finite by Corollary 3.6; moreover, every n-generated subdirectly irreducible member of $\mathsf {OSM}$ is a residuated chain with at most $2n + 2$ elements (see [8]).

We now turn our attention to the variety ${\mathsf {SemCIdRL}}$ of semilinear commutative idempotent residuated lattices.

Lemma 6.5

The class of commutative idempotent residuated chains has the amalgamation property.

Proof

Let $\langle i_1:\mathbf{A}\hookrightarrow \mathbf{B}, i_2:\mathbf{A}\hookrightarrow \mathbf{C}\rangle$ be a span of commutative idempotent residuated chains, assuming without loss of generality that $i_1$ and $i_2$ are inclusion maps and that $B \cap C = A$. Then, using Lemma 3.3, we also have inclusions between their skeletons $\mathbf{A}_{\gamma _{\mathrm e}} \hookrightarrow \mathbf{B}_{\gamma _{\mathrm e}}$ and $\mathbf{A}_{\gamma _{\mathrm e}}\hookrightarrow \mathbf{C}_{\gamma _{\mathrm e}}$. Since, by Proposition 3.4, these skeletons are totally ordered odd Sugihara monoids, Lemma 6.3 yields an amalgam $\mathbf{S}$ for this span that is also a totally ordered odd Sugihara monoid. Moreover, we may assume that $S=B_{\gamma _{\mathrm e}}\cup C_{\gamma _{\mathrm e}}$.

Consider $a \in A_{\gamma _{\mathrm e}}$. Recalling that $A_a = \{x\in A : \gamma _{\mathrm e}(x) = a\}$, clearly

$$\begin{aligned} A_a \subseteq B_a = \{x\in B : \gamma _{\mathrm e}(x) = a\} \text {and}A_a\subseteq C_a = \{x\in C : \gamma _{\mathrm e}(x) = a\}. \end{aligned}$$

Moreover, the inclusions $\langle A_a,{\le }^{\mathbf{A}}\mathord {\upharpoonright }A_a\rangle \hookrightarrow \langle B_a,{\le }^{\mathbf{B}}\mathord {\upharpoonright }B_a\rangle$ and $\langle A_a,{\le }^{\mathbf{A}}\mathord {\upharpoonright }A_a\rangle \hookrightarrow \langle C_a,{\le }^{\mathbf{C}}\mathord {\upharpoonright }C_a\rangle$ form a span of chains (viewed as algebras) and have as an amalgam a chain $\langle D_a,\le _a\rangle$ with $D_a = B_a\cup C_a$. Since a is the greatest element of $A_a$, $B_a$, and $C_a$, it is also the greatest element of $\langle D_a,\le _a\rangle$. Now, for all $b\in B_{\gamma _{\mathrm e}}\setminus A_{\gamma _{\mathrm e}}$ and $c\in C_{\gamma _{\mathrm e}}\setminus A_{\gamma _{\mathrm e}}$, let $\langle D_b,\le _b\rangle = \langle B_b,{\le }^{\mathbf{B}}\mathord {\upharpoonright }B_b\rangle$ and $\langle D_c,\le _c\rangle = \langle C_c,{\le }^{\mathbf{C}}\mathord {\upharpoonright }C_c\rangle$. Then ${\mathcal {X}} = \{\langle D_s,\le _s\rangle : s\in S\}$ is a family of (disjoint) chains such that each $s\in S$ is the greatest element of $D_s$. By Theorem 3.5, $\mathbf {D} = \mathbf {S} \otimes {\mathcal {X}}$ is a commutative idempotent residuated chain satisfying $\mathbf{S} = (\mathbf {S} \otimes {\mathcal {X}})_{\gamma _{\mathrm e}}$ and $(S \otimes {\mathcal {X}})_s = D_s$ for each $s\in S$.

To show that $\mathbf{D}$ is an amalgam of the original span, it suffices to check that $\mathbf{B}$ and $\mathbf {C}$ are subalgebras of $\mathbf{D}$. Consider $x,y\in B$ with $x\in B_{b_1}$ and $y\in B_{b_2}$. Then $b_1,b_2\in S$ and $x\in D_{b_1}$, $y\in D_{b_2}$. If $x\le ^\mathbf{B} y$, then $b_1\le b_2$. If $b_1=b_2=b$, then $x,y\in D_b$ and since the order of $\langle D_b,\le _b\rangle$ extends the order of $B_b$, we also have $x\le _b y$, and hence $x\le ^\mathbf{D} y$. If $b_1\ne b_2$, then $b_1\le b_2$, and hence $x\le ^\mathbf{D} y$. This shows that the order of $\mathbf{D}$ extends the order of $\mathbf{B}$.

Let us prove next that the product of $\mathbf{D}$ extends the product of $\mathbf{B}$. If $b_1 = b_2 =b$, then either ${\mathrm e}<^\mathbf{B} b$ and $x\cdot ^\mathbf{B} y = x\vee ^\mathbf{B} y = x\vee ^\mathbf{D} y = x\cdot ^\mathbf{D} y$, or $b <^\mathbf{B} {\mathrm e}$, which is analogous. If $b_1\ne b_2$, then

$$\begin{aligned} x\cdot ^\mathbf{B} y =x&\iff b_1\cdot ^\mathbf{B} b_2 = b_1 \iff b_1\cdot ^{\mathbf{B}_{\gamma _{\mathrm e}}} b_2 = b_1 \iff b_1\cdot ^\mathbf{S} b_2 = b_1\\&\iff b_1\cdot ^\mathbf{D} b_2 = b_1 \iff x\cdot ^\mathbf{D} y =x. \end{aligned}$$

For the residuals:

$$\begin{aligned} x\rightarrow ^\mathbf{B} y&= {\left\{ \begin{array}{ll} {\sim }^{\mathbf{B}_{\gamma _{\mathrm e}}} b_1 \vee ^\mathbf{B} y &{}\quad \text {if } x\le ^\mathbf{B} y,\\ {\sim }^{\mathbf{B}_{\gamma _{\mathrm e}}} b_1 \wedge ^\mathbf{B} y &{}\quad \text {if } y<^\mathbf{B} x \end{array}\right. }\\&= {\left\{ \begin{array}{ll} {\sim }^\mathbf{S} b_1 \vee ^\mathbf{D} y &{}\quad \text {if } x\le ^\mathbf{D} y,\\ {\sim }^\mathbf{S} b_1 \wedge ^\mathbf{D} y &{}\quad \text {if } y <^\mathbf{D} x \end{array}\right. } \\&= x\rightarrow ^\mathbf{D} y. \end{aligned}$$

The proof that $\mathbf {C}$ is a subalgebra of $\mathbf {D}$ is symmetrical. $\square$

Every variety of commutative residuated lattices has the congruence extension property, so Theorem 6.1 yields the following result.

Theorem 6.6

The variety of semilinear commutative idempotent residuated lattices has the amalgamation property.

We now address an open question in the literature (see, e.g., [18]) by describing a noncommutative variety of (idempotent) residuated lattices that has the amalgamation property. Note first that all idempotent residuated chains with at most 3 elements are commutative, since $\bot$ and ${\mathrm e}$ are central elements and noncentral elements come in pairs. Similarly, there are only two nonisomorphic noncommutative idempotent residuated chains of size 4: the one represented in Figure 3, which we call $\mathbf{C}_4$, and its “opposite” (i.e., the algebra resulting from swapping the order of the product).

Fig. 3

The algebra $\mathbf{C}_4$

We will use Theorem 6.1 to prove that the variety ${\mathsf {V}}(\mathbf{C}_4)$ generated by $\mathbf{C}_4$ has the amalgamation property. To show first that ${\mathsf {V}}(\mathbf{C}_4)$ has the congruence extension property, we make use of some results from [1]. Recall that a term $u(\mathbf {x},\mathbf {y}\,)$ is an ideal term in $\mathbf {x}$ for a variety ${\mathsf {V}}$ with respect to a (term-definable) constant 1 if and only if ${\mathsf {V}}\models t(\mathbf {1},\mathbf {y}\,) \approx 1$. The ideals (with respect to 1) of an algebra $\mathbf{A}\in {\mathsf {V}}$ are the subsets $I\subseteq A$ such that $u(\mathbf {a},\mathbf {b}\,)\in I$ for every ideal term $u(\mathbf {x},\mathbf {y}\,)$ and $\mathbf {a} \in I$, $\mathbf {b} \in A$. If $\mathbf {A}$ is a residuated lattice, then the ideals with respect to ${\mathrm e}$ coincide with the convex normal subalgebras of $\mathbf {A}$. In [1] it was proved that the variety generated by a residuated lattice $\mathbf{A}$ has equationally definable principal congruences (and therefore the congruence extension property) if there exists a finite set J of ideal terms (with respect to ${\mathrm e}$) such that for all $a,b\in \mathord {\downarrow }{\mathrm e}$, there exists $u(x,y) \in J$ satisfying

$$\begin{aligned} b\in {\langle a\rangle }^\mathbf{A} \iff b = u^\mathbf{A}(a,b), \end{aligned}$$

(1)

where ${\langle a\rangle }^\mathbf{A}$ denotes the convex normal subalgebra generated by a.

Lemma 6.7

${\mathsf {V}}(\mathbf{C}_4)$ has the congruence extension property.

Proof

Observe first that $\mathbf{C}_4$ has only the trivial proper subalgebra, since $c^\sharp = c{\backslash }{\mathrm e}= \bot {\backslash }{\mathrm e}$, $\bot = c^\sharp {\backslash }{\mathrm e}= {\mathrm e}{/}c^\sharp$, and $c = {\mathrm e}{/}c^\sharp$. It suffices now to check that $\mathbf{C}_4$ satisfies (1) for the set of ideal terms $J = \{{\mathrm e},x,(x{\backslash }{\mathrm e}){\backslash }{\mathrm e}, {\mathrm e}{/}({\mathrm e}{/}x)\}$. For $a = {\mathrm e}$, we have ${\langle {\mathrm e}\rangle }^{\mathbf{C}_4} = \{{\mathrm e}\} = J({\mathrm e})$, and for $a \ne {\mathrm e}$, we have ${\langle a\rangle }^{\mathbf{C}_4} = C_4$ and $J(a) = \{{\mathrm e}, c, \bot \}$. $\square$

Theorem 6.8

${\mathsf {V}}(\mathbf{C}_4)$ has the amalgamation property.

Proof

By Theorem 6.1 and Lemma 6.7, it suffices to consider spans of finitely generated totally ordered members of ${\mathsf {V}}(\mathbf{C}_4)$. But $\mathbf{C}_4$ only has the trivial proper subalgebra $\{e\}$ and, since the lattice of congruences of a residuated lattice is isomorphic to the lattice of its convex normal subalgebras, is simple. By Jónsson’s Lemma, the only nontrivial subdirectly irreducible algebra of ${\mathsf {V}}(\mathbf{C}_4)$ up to isomorphism is $\mathbf{C}_4$. Hence all spans of finitely generated totally ordered members of ${\mathsf {V}}(\mathbf{C}_4)$ are trivial and clearly have an amalgam. $\square$

Let us note finally that the same method can be used to prove that the variety generated by the strongly simple idempotent residuated chain $\mathbf{C}_{2n+2}$ with $n \ge 2$ pairs of noncommuting elements has the amalgamation property.