Four generators of an equivalence lattice with consecutive block counts

For $p,q\in A$, the smallest equivalence collapsing $p$ and $q$ is an atom in $\textup{Equ}(A)$; we denote it by $\textup{at}(p,q)$. So $(x,y)\in\textup{at}(p,q)$ if and only if $x=y$ or $\{x,y\}=\{p,q\}$. Denote the elements of $A$ as follows: $A=\{a_{0},a_{1},\dots,a_{9}$, $b_{0},b_{1},\dots,b_{8}\}$; see Figure 1. The figure defines a subset $X:=\{\alpha,\beta,\gamma,\delta\}$ of the equivalence lattice $\textup{Equ}(A)$ as follows. Assume that the horizontal edges, the vertical edges, and the slanted straight edges of the graph are labeled by $\alpha$, $\beta$, and $\gamma$, respectively. To avoid a crowded figure, these labels are not indicated in the figure, but the triangle on the right reminds us of this convention. There are also two $\delta$-labeled edges, which are drawn as curves. For $\epsilon\in X$, the figure defines $\epsilon$ as follows; walks of length zero are allowed.

For example, $\{b_{1},a_{2}\}$ is a block of $\gamma$ and $\{b_{0},\dots,b_{8}\}$ is a block of $\alpha$. Let $S$ be the sublattice generated by $X$. In Figure 2, where $A$ is drawn three times, some equivalences are given by their non-singleton blocks. The meanings of these blocks, with different geometric orientations, line styles, and colors, are defined on the right of the figure. For example, $\rho_{0}=\textup{at}(a_{0},b_{0})$ and $\lambda^{\prime}_{1}=\textup{at}(a_{9},a_{8})\vee\textup{at}(a_{8},a_{7})\vee\textup{at}(b_{8},b_{7})$. We can easily show that, in this order, $\rho_{0}$, $\rho^{\prime}_{0}$, $\rho^{\prime\prime}_{0}$, $\rho_{1}$, $\rho^{\prime}_{1}$, $\rho^{\prime\prime}_{1}$, $\rho_{2}$, $\rho^{\prime}_{2}$, $\rho^{\prime\prime}_{2}$, $\rho_{3}$, $\rho^{\prime}_{3}$, $\rho^{\prime\prime}_{3}$, $\rho_{4}$, …belong to $S$, since each of them is expressible from the generators and the earlier ones. Indeed, $\rho_{0}=\beta\wedge\delta$ and, for $i=0,1,2,\dots$, we have that $\rho^{\prime}_{i}=(\rho_{i}\vee\gamma)\wedge\alpha$, $\rho^{\prime\prime}_{i}=(\rho^{\prime}_{i}\vee\beta)\wedge\gamma$, and $\rho_{i+1}=\bigl{(}((\rho^{\prime\prime}_{i}\vee\beta)\wedge\alpha)\vee\rho^{\prime\prime}_{i}\bigr{)}\wedge\beta$. The increasing sequences $(\rho_{0},\rho_{1},\rho_{2},\dots)$, $(\rho^{\prime}_{0},\rho^{\prime}_{1},\rho^{\prime}_{2},\dots)$, and $(\rho^{\prime\prime}_{0},\rho^{\prime\prime}_{1},\rho^{\prime\prime}_{2},\dots)$ are right-going in the sense that when the subscript increases by $1$, the subscripted equivalence obtains a new “edge” on the right of the earlier edges. By interchanging the role of $\beta$ and $\gamma$, we obtain three increasing “left-going” sequences $(\lambda_{0},\lambda_{1},\lambda_{2},\dots)$, $(\lambda^{\prime}_{0},\lambda^{\prime}_{1},\lambda^{\prime}_{2},\dots)$, and $(\lambda^{\prime\prime}_{0},\lambda^{\prime\prime}_{1},\lambda^{\prime\prime}_{2},\dots)$. Where a right-going sequence “reaches” the appropriate left-going one, the meet of the two sequences yields an atom of $\textup{Equ}(A)$. Namely, for $i\in\{0,1,\dots,8\}$, $\textup{at}(a_{i},b_{i})=\rho_{i}\wedge\lambda^{\prime\prime}_{8-i}\in S$, $\textup{at}(a_{i+1},b_{i})=\rho^{\prime\prime}_{i}\wedge\lambda_{8-i}\in S$, and $\textup{at}(a_{i},a_{i+1})=\rho^{\prime}_{i}\wedge\lambda^{\prime}_{8-i}\in S$. Furthermore, for $i\in\{0,\dots,7\}$, $\textup{at}(b_{i},b_{i+1})=\bigl{(}\textup{at}(a_{i+1},b_{i})\vee\textup{at}(a_{i+1},b_{i+1})\bigr{)}\wedge\alpha\in S$. Hence, for every edge $(x,y)$ of the graph, $\textup{at}(x,y)\in S$. Therefore, the following lemma implies easily that $X$ generates $\textup{Equ}(A)$. ∎

For $x,y\in A$, $\textup{qu}(x,y)$ denotes the smallest quasiorder containing $(x,y)$. Let $S$ stand for the sublattice generated by $Y$. Since $f\colon\textup{Quo}(A)\to\textup{Quo}(A)$ defined by $\mu\mapsto\mu^{-1}$ is an automorphism of $\textup{Quo}(A)$ and $Y$ is $f$-closed, $S$ is also closed with respect to forming inverses. In particular, whenever $\textup{qu}(x,y)$ is in $S$, then so is $\textup{qu}(y,x)$; this fact will be used without further explanation. Let us compute; each containment “$\in S$” below follows from the earlier ones and $Y\subseteq S$:

and so on. Computations (1.2)–(1.14) and the fact that $S$ is closed with respect to forming inverses show that for each thick and red edge $(x,y)$ of the graph, $\textup{qu}(x,y)$ and $\textup{qu}(y,x)$ are in $S$. The figure and (1.2)–(1.14) also show how we can proceed further to the right. Hence, $\textup{qu}(x,y)$ and $\textup{qu}(y,x)$ are in $S$ for every edge $(x,y)$ of the graph. Thus, the straightforward counterpart of Lemma 1.3 for quasiorder lattices completes the proof of Claim 1.4. ∎

The situation is visualized in Figure 4, where the blocks of some elements, all important elements from our perspective, are drawn. The three blocks drawn by solid lines are blocks of some members of $\Phi\subseteq\textup{Equ}(A)$. The seven blocks drawn in non-solid line styles (dotted and various kinds of dashed) are blocks of the equivalences belonging to $\Phi^{\prime}\subseteq\textup{Equ}(A^{\prime})$. The figure uses different line styles or distinct colors for the blocks of different equivalences, but we use the same color for $\epsilon\in\Phi$ and $\epsilon^{\prime}$. Note that the geometrically large blocks on the left could be singletons and, on the other hand, $u/\alpha:=\{x:(x,u)\in\alpha\}$ and $v/\gamma$ can be but need not be disjoint. Not all blocks of all $\epsilon$ and $\epsilon^{\prime}$ are drawn for $\epsilon\in\Phi$. However, for any $x\in A$ and $\epsilon\in\Phi$, if the block $x/\epsilon$ is not drawn, then $x/\epsilon=x/\epsilon^{\prime}$. The last sentence of Lemma 2.4 follows from the trivial fact that $\textup{blnum}(\epsilon^{\prime})=1+\textup{blnum}(\epsilon)$ holds for every $\epsilon\in\Phi$. Applying a lemma from [5] twice (in a “twisted way” and in a “straight way”), we could derive the rest of Lemma 2.4 from [5]. To keep the paper self-contained, we give a different and direct proof.

The existence of an $x\in u/\beta\wedge v/\gamma$ would violate the conjunction of $\beta\wedge(\gamma\vee\textup{at}(u,v))=\mathbf{0}_{A}$ and $\gamma\wedge(\beta\vee\textup{at}(u,v))=\mathbf{0}_{A}$ —call them the meet conditions for $\beta$ and $\gamma$— and $u\neq v$. Thus, $u/\beta$ and $v/\gamma$ are disjoint.

By the two paragraphs above, Figure 4 faithfully represents the situation and contains all the details the proof needs. Hence, it is straightforward to verify that the three pairs in Definition 2.3 for $\textup{Equ}(A^{\prime})$ are complementary. Let $S$ and $E$ denote the sublattice generated by $\Phi^{\prime}$ in $\textup{Equ}(A^{\prime})$ and the sublattice $\{\mu\in\textup{Equ}(A^{\prime})$ : both $u^{\prime}/\mu$ and $v^{\prime}/\mu$ are singletons$\}$. Then $f\colon\textup{Equ}(A)\to E$ defined by $\mu\mapsto\overline{\textup{eq}}\kern 1.0pt^{\prime}(\mu)$ is a lattice isomorphism.

Observe that $\{u^{\prime}\}$ is a singleton block of $\beta^{\prime}\vee^{\prime}\gamma^{\prime}$. Furthermore, $\{v^{\prime}\}$ is a singleton block of both $\alpha^{\prime}$ and $\delta^{\prime}\wedge^{\prime}(\beta^{\prime}\vee^{\prime}\gamma^{\prime})$. Thus $\{v^{\prime}\}$ is a singleton block of $\alpha^{\prime}\vee^{\prime}\bigl{(}\delta^{\prime}\wedge^{\prime}(\beta^{\prime}\vee^{\prime}\gamma^{\prime})\bigr{)}$. Therefore, with

$|u^{\prime}/\kappa|=|v^{\prime}/\kappa|=1$. Using the fact that $\epsilon\subseteq\epsilon^{\prime}$ for all $\epsilon\in X$, the join condition $\beta\vee\textup{at}(u,v)\vee\gamma=\mathbf{1}_{A}$ for $\beta$ and $\gamma$, and $(u,v)\in\beta^{\prime}\vee^{\prime}\gamma^{\prime}$, we obtain that $A^{2}\subseteq\beta^{\prime}\vee^{\prime}\gamma^{\prime}$. By the previous two “$\subseteq$” inclusions, $\delta\subseteq\delta^{\prime}\wedge^{\prime}(\beta^{\prime}\vee^{\prime}\gamma^{\prime})$. Using this fact, $\alpha\subseteq\alpha^{\prime}$, and the join condition for the complementary pair $(\alpha,\delta)$, we obtain that $A^{2}\subseteq\kappa$. Combining this with $|u^{\prime}/\kappa|=|v^{\prime}/\kappa|=1$, we have that $f(\mathbf{1}_{A})=\kappa\in S$. Thus, for all $\epsilon\in\Phi$, $f(\epsilon)=f(\mathbf{1}_{A})\wedge\epsilon^{\prime}\in S$, whereby $f(\Phi)\subseteq S$. Since $\Phi$ generates $\textup{Equ}(A)$ and $f\colon\textup{Equ}(A)\to E$ is an isomorphism, we obtain that $E\subseteq S$. In particular, $\textup{at}^{\prime}(u,v)=f(\textup{at}(u,v))\in S$. As the following equalities are clear by the figure, we obtain further elements of $S$ as follows:

Finally, since $E\subseteq S$ and we have (2.1), (2.2), and (2.3), Lemma 1.3 implies that $S=\textup{Equ}(A^{\prime})$. This completes the proof of Lemma 2.4. ∎

Let $\Phi:=\{\alpha,\beta,\gamma,\delta\}$, and let $S$ stand for the sublattice generated by $S$. The labels above the equality signs will indicate which members of $S$ imply that the equivalences on the left of these equality signs belong to $S$.

In particular, $\textup{at}(1,2)\in S$ by (2.10), $\textup{at}(2,6)\in S$ by (2.22), $\textup{at}(6,5)\in S$ by (2.26), $\textup{at}(5,4)\in S$ by (2.16), $\textup{at}(4,3)\in S$ by (2.5), and $\textup{at}(3,1)\in S$ by (2.25). Hence, $\Phi$ is a generating set by Lemma 1.3. Clearly, $\Phi$ is of consecutive block counts. It is easy to check that the pairs in Definition 2.3 are complementary. Thus, $\mathbf{A}$ is an eligible system, proving Lemma 2.5. ∎

Combine Lemmas 2.4, 2.5, and 2.6. ∎

The idea is the same as in the proof of Lemma 2.5 but the concrete computations are different. Again, $S$ denotes the sublattice generated by $\{\alpha,\dots,\delta\}$. Let us compute; to avoid line breaks, the formatting will be slightly different from that of (2.8)–(2.26).