Lattices — Linear Algebra

The length of a poset. An order relation tells us when one element lies below another, but it does not specify how many steps separate them. The covering relation identifies an immediate step in the order, while chains allow us to examine sequences of comparable elements. We use these notions to define the length of chains, intervals, and posets.

Definition 1.3.1. Let $$P$$ be a poset. For $$x,y\in P$,$ we say that $$y$$ covers $$x$,$ written

\[x\lessdot y,\]

if $$x<y$$ and there is no $z\in P$ such that $$x<z<y$.$ Equivalently, we have

\[x\lessdot y\iff [x,y] = \{x,y\}.\]

In this case, $$x$$ is called the immediate predecessor of $$y$,$ and $$y$$ is called the immediate successor of $$x$.$

Definition 1.3.2. A chain $$C$$ in a poset $$P$$ is a nonempty totally ordered subset of $$P$.$ If $$C$$ is finite, then it is called a finite chain. The length of the finite chain $$C$,$ denoted by $$\ell(C)$,$ is the number of the pairs in the covering relation defined on $$C$.$

Proposition 1.3.3. Let $$C$$ be a finite chain in a poset $$P$.$ Then we have

\[\ell(C) = |C|-1.\]

Proof. Let $$n=|C|$,$ and regard $$C$$ as a poset with the induced order. Since $$C$$ is a finite chain, every element $x\in C$ other than its maximum has an immediate successor in $$C$,$ namely the least element of $$\{y\in C : y>x\}$.$ Furthermore, this immediate successor is unique. Indeed, if both $$y$$ and $$z$$ cover $$x$$ and $$y\ne z$,$ either $$y<z$$ or $$z<y$,$ contradicting the covering relation. Since each of the $$n-1$$ nonmaximum elements is the lower element of exactly one covering pair in $$C$,$ $$\ell(C)=n-1$.$ $\square$

Definition 1.3.4. The length of an interval $$[x,y]$$ in a poset, denoted by $$\ell([x,y])$,$ is the supremum of the lengths of all finite chains in $$[x,y]$.$

Definition 1.3.5. A nonempty poset $$P$$ is said to have finite length if there exists a nonnegative integer $$n$$ such that every chain in $$P$$ is finite and has length at most $$n$.$ The least such $$n$$ is called the length of $$P$,$ denoted by $$\ell(P)$.$ In particular, the length of a finite-length poset $$P$$ is the maximum of the lengths of all chains in $$P$.$

Semilattices and lattices. Many algebraic structures give rise to posets of substructures, ordered by inclusion. In such settings, the intersection of two substructures is their greatest common substructure, while the substructure they generate together is the least substructure containing both. These are concrete instances of infima and suprema. This observation motivates studying the corresponding operations abstractly, independently of the particular objects involved.

Definition 1.3.6. A semilattice is an ordered pair $(S,\vee)$ where $$S$$ is a set, $\vee$ is an associative, commutative, and idempotent binary operation on $$S$.$

Proposition 1.3.7. Given a semilattice $$(S,\vee)$,$ there is a unique order $\le$ on $$S$$ which makes $x\vee y$ the supremum for $\{x,y\}$ for all $$x,y\in S$.$ Conversely, suppose that $$S$$ is a poset and any pair of two elements of $$S$$ has a supremum. If we write the supremum for $\{x,y\}$ as $$x\vee y$,$ and regard $\vee$ as a binary operation on $$S$,$ then $(S,\vee)$ is a semilattice.

Proof. We define a relation $\le$ on $$S$$ by

\[x\le y \iff y=x\vee y\]

for all $$x,y\in S$.$ Then $\le$ is an order on $$S$$ and makes $x\vee y$ the supremum for $\{x,y\}$ for all $$x,y\in S$.$ Conversely, suppose that $$S$$ is partially ordered by $\le$ and any pair of two elements $$x$$ and $$y$$ of $$S$$ has a supremum $$x\vee y$.$ Let $$(x\vee y)\vee z = \alpha$.$ Then $x\vee y \le \alpha$ and $$z\le \alpha$,$ so $\alpha$ is an upper bound for $$\{x,y,z\}$.$ Suppose $\beta$ is an upper bound for $$\{x,y,z\}$.$ It follows that $x\vee y \le \beta$ and $$z\le \beta$.$ Since $$(x\vee y)\vee z = \alpha$,$ we have $$\alpha\le \beta$.$ Therefore $\alpha$ is the supremum for $$\{x,y,z\}$.$ Similarly, $x\vee(y\vee z)$ is the supremum for $$\{x,y,z\}$,$ so that $$x\vee(y\vee z) = \alpha$.$ Hence $\vee$ is associative. By definition, $\vee$ is commutative. Furthermore, since $$x$$ is the supremum for $$\{x\}$,$ $\vee$ is idempotent. Therefore $(S,\vee)$ is a semilattice. $\square$

Definition 1.3.8. A semilattice $(S,\vee)$ is called an upper semilattice if $x\vee y$ is interpreted as the supremum for $\{x,y\}$ for all $$x,y\in S$.$ In this case, the operation $\vee$ is called join. Replacing “supremum” with “infimum”, we obtain the dual concept of a lower semilattice. To distinguish from the previous situation, we shall denote a lower semilattice by $(S,\wedge)$ and call $\wedge$ meet.

Definition 1.3.9. A lattice is an ordered triple $(L,\vee,\wedge)$ where $$L$$ is a set and $\vee$ and $\wedge$ are binary operations on $$L$$ satisfying the following:

$(L,\vee)$ is an upper semilattice;
$(L,\wedge)$ is a lower semilattice;
for all $x,y\in L$
\[x\wedge(x\vee y) = x\quad \text{and} \quad x\vee(x\wedge y) = x.\]

In a lattice $$L$,$ the join and meet operations each determine an order relation. The first identity in (L3) ensures that if $$y$$ is an upper bound for $$x$$ with respect to $$\le_{\vee}$,$ then $$x$$ is a lower bound for $$y$$ with respect to $\le_{\wedge}$ for all $$x,y\in L$.$ The second identity gives the converse implication. Thus the two induced order relations coincide.

Example 1.3.10. The power set $\mathcal P$ of $\{x,y,z\}$ partially ordered by set inclusion is a lattice of length $$3$.$ We can graphically express the covering structure of $\mathcal P$ as follows:

This type of diagram is called a Hasse diagram. In general, the ordered triple $(\mathcal{P}(S),\cup, \cap)$ is a lattice.

A function $$f$$ is an order isomorphism if and only if it is a lattice isomorphism. On the other hand, a lattice homomorphism being monotone, an monotone map between lattices need not preserve joins or meets. Nevertheless, the extremal properties of these operations impose certain inequalities that every such map must satisfy.

Theorem 1.3.11. Let $$L$$ and $$M$$ be lattices, and let $f\colon L\to M$ be a monotone map. Then, for all $$x,y\in L$,$

\[f(x\wedge y) \le f(x)\wedge f(y)\quad \text{and} \quad f(x\vee y)\ge f(x)\vee f(y).\]

Proof. Since $x\wedge y\le x$ and $$x\wedge y\le y$,$ monotonicity yields $f(x\wedge y)\le f(x)$ and $$f(x\wedge y)\le f(y)$.$ Hence $f(x\wedge y)$ is a lower bound for $$f(x)$$ and $$f(y)$.$ It follows from the definition of infimum that $$f(x\wedge y) \le f(x)\wedge f(y)$.$ The second inequality follows from duality. $\square$

The distributive laws need not hold in an arbitrary lattice. Nevertheless, one direction of each distributive identity always holds as an inequality, without any additional assumptions.

Corollary 1.3.12. Let $$L$$ be a lattice. For all $$x,y,z\in L$,$

\[x\vee(y\wedge z) \leq (x\vee y)\wedge(x\vee z) \quad \text{and} \quad x\wedge(y\vee z)\ge (x\wedge y)\vee(x\wedge z).\]

Proof. Fix $x\in L$ and define

\[f_x\colon L\to L,\qquad f_x(t) = x\vee t.\]

Suppose $y,z\in L$ and $$y\le z$.$ Since $x\vee z\ge x$ and $$x\vee z\ge z \ge y$,$ $x\vee z$ is an upper bound for $$x$$ and $$y$.$ By the definition of supremum, $$x\vee y\le x\vee z$,$ so that $$f_x(y)\le f_x(z)$.$ Thus $$f_x$$ is monotone. Theorem 1.3.11 now gives the first inequality. The second inequality follows from duality. $\square$

Modular lattices. The lattices arising from algebraic structures often satisfy additional laws that do not hold in arbitrary lattices. An important example is the lattice of submodules of a module, in which join is given by submodule sum and meet by intersection. Whenever $$X\subseteq Z$,$ these operations satisfy

\[X+(Y\cap Z)=(X+Y)\cap Z.\]

This identity expresses a compatibility between forming sums of submodules and restricting them by intersection. Its validity follows from the additive structure of modules, but it can be expressed entirely in terms of joins, meets, and the underlying order. We can therefore abstract this property without referring to modules themselves. In an arbitrary lattice, the corresponding left-hand side is always bounded above by the right-hand side; requiring equality gives the modular law. As we shall see, this condition has important structural consequences, including natural isomorphisms between certain intervals.

Definition 1.3.13. A lattice $$L$$ is called modular if, for all $$x,y,z\in L$,$

\[x\le z\implies x\vee(y\wedge z)=(x\vee y)\wedge z.\]

Theorem 1.3.14. Let $$L$$ be a modular lattice. Then we have, for all $$x,y\in L$,$

\[[x\wedge y,x] \cong [y,x\vee y].\]

Proof. Let $x,y\in L$ and define

\[\begin{aligned} f\colon [x\wedge y,x]&\to[y,x\vee y], & s&\mapsto s\vee y,\\ g\colon [y,x \vee y]&\to[x\wedge y,x], & t&\mapsto t\wedge x. \end{aligned}\]

Since $$f$$ is monotone, $f(s)\in [y,x\vee y]$ for all $$s\in [x\wedge y,x]$.$ Similarly, since $$g$$ is monotone, $g(t)\in [x\wedge y,x]$ for all $$t\in [y,x \vee y]$.$ Hence the functions are well-defined. Furthermore, by modularity of $$L$,$ we have

\[\begin{aligned} g(f(s)) &=(s\vee y)\wedge x\\ &=s\vee(y\wedge x)=s, \end{aligned}\]

and

\[\begin{aligned} f(g(t)) &=(t\wedge x)\vee y\\ &=t\wedge(x\vee y)=t, \end{aligned}\]

for all $s\in [x\wedge y,x]$ and $$t\in [y,x \vee y]$.$ Thus $$f$$ and $$g$$ are mutually inverse bijections. Since both maps are monotone, $$f$$ is an order isomorphism. An order isomorphism between lattices preserves joins and meets, so $$f$$ is a lattice isomorphism. $\square$

The interval isomorphism in Theorem 1.3.14 preserves covering relations. In particular, if $x\wedge y$ is covered by $$x$,$ then $$y$$ is covered by $$x\vee y$.$ This suggests weakening modularity by retaining this local consequence without requiring an isomorphism between the entire intervals.

Definition 1.3.15. A lattice $$L$$ is called upper semimodular if, for all $$x,y\in L$,$

\[x\wedge y\lessdot x \implies y\lessdot x\vee y.\]

Dually, $$L$$ is called lower semimodular if, for all $$x,y\in L$,$

\[x\vee y \gtrdot y \implies x\gtrdot x\wedge y.\]

Rank functions and graded lattices. The preceding results describe modularity and semimodularity through relations among joins, meets, and covering pairs. To express these structural conditions numerically, we seek a function that assigns a level to each element and increases by one across every covering relation. We then examine inequalities involving the ranks of joins and meets, which lead to numerical characterizations of semimodularity and modularity. Throughout the remainder of this section, we only consider finite-length lattices with their least element.

Definition 1.3.16. Let $$L$$ be a lattice with the least element $$\hat 0$.$ A function

\[\rho\colon L\longrightarrow\mathbb Z_{\geq 0}\]

is called a rank function on $$L$$ if it satisfies the following:

$$\rho(\hat{0})=0$;$
$\rho(y)=\rho(x)+1$ whenever $$x\lessdot y$.$

A lattice is called graded if it admits a rank function.

Proposition 1.3.17. A lattice $$L$$ is graded if and only if all maximal chains in any interval in $$L$$ have the same length. In this case, the rank function is unique and satisfies

\[\rho(x)=\ell([\hat0,x]) \quad \text{and} \quad \ell([x,y])=\rho(y)-\rho(x)\]

for every $x,y\in L$ with $$x\leq y$.$

Proof. Suppose $$L$$ is graded and $\rho\colon L\to Z_{\ge 0}$ is a rank function on $$L$.$ Let $$I=[a,b]$$ be any interval in $$L$$ and $$C$$ be a maximal chain in $$I$.$ Then $$a$$ and $$b$$ are the minimum and maximum of $$C$,$ respectively. Furthermore, since $$C$$ has the form

\[a = x_0\lessdot x_1\lessdot\cdots\lessdot x_{\ell(C)}=b,\]

we have $$\ell(C) = \rho(b)-\rho(a)$.$ It follows that

\[\ell([a,b]) = \ell(C) = \rho(b)-\rho(a).\]

Hence all maximal chains in the interval $$I$$ have the same length. Furthermore, we have

\[\rho(x) = \ell([\hat0,x]) + \rho(\hat0) = \ell([\hat0,x])\]

for all $$x\in L$,$ which implies that a rank function is unique. Conversely, suppose that all maximal chains in any interval in $$L$$ have the same length. Define $$\rho(\hat0) = 0$.$ For each interval $[\hat0,x]$ in $$L$,$ define $$\rho(x) = \ell([\hat0, x])$.$ Let $x,y\in L$ with $x\lessdot y$ and let $$C$$ be a maximal chain in $$[\hat0,x]$.$ Then, $C'=C\mathbin{\dot{\cup}} \{y\}$ is a maximal chain in $$[\hat0,y]$.$ It follows from Proposition 1.3.3 that

\[\begin{align} \ell([\hat0,y]) &= \ell(C')\\ &= |C'|-1\\ &= |C|\\ &= \ell(C) + 1 \\ &= \ell([\hat0, x]) + 1. \end{align}\]

Therefore

\[\rho(y) = \rho(x) + (\ell([\hat0,y]) -\ell([\hat0,x])) = \rho(x) + 1.\]

Hence $\rho$ is the rank function and $$L$$ is graded. $\square$

In a graded lattice, rank differences measure the lengths of intervals. We can therefore compare the intervals associated with joins and meets by comparing the corresponding differences of rank. This motivates the following inequalities for real-valued functions on lattices.

Definition 1.3.18. Let $$L$$ be a lattice and let $f\colon L\to\mathbb R$ be a function. We say that $$f$$ is submodular if, for all $$x,y\in L$,$

\[f(x\vee y) - f(y) \le f(x) - f(x\wedge y).\]

Dually, $$f$$ is called supermodular if, for all $$x,y\in L$,$

\[f(x\vee y) - f(y) \ge f(x) - f(x\wedge y).\]

We say that $$f$$ is modular if it is both submodular and supermodular.

Theorem 1.3.19. A lattice $$L$$ is upper semimodular if and only if $$L$$ is graded and its rank function is submodular.

Proof. Suppose that $$L$$ is upper semimodular. We first prove that $$L$$ is graded. Let $$I=[a,b]$$ be an interval in $$L$.$ We show, by induction on $$\ell(I)$,$ that all maximal chains in $$I$$ have the same length. The assertion is immediate if $$\ell(I)\le 1$.$ Suppose that $\ell(I)\ge 2$ and that the assertion holds for every interval of smaller length. Let $$C$$ and $$D$$ be maximal chains in $$I$,$ and let $$u$$ and $$v$$ be their respective immediate successors of $$a$.$ Thus $a\lessdot u$ and $$a\lessdot v$.$ If $$u=v$,$ the induction hypothesis applied to $$[u,b]$$ gives $$\ell(C)=\ell(D)$.$ Suppose instead that $$u\ne v$.$ Since both $$u$$ and $$v$$ cover $$a$,$ we have $$u\wedge v=a$.$ By upper semimodularity, $u\lessdot u\vee v$ and $$v\lessdot u\vee v$.$ Put $$w=u\vee v$.$ Since $$w\le b$,$ the intervals $$[u,b]$,$ $$[v,b]$,$ and $$[w,b]$$ all have length smaller than $$\ell(I)$.$ By the induction hypothesis, all maximal chains in each of these intervals have the same length. Consequently,

\[\ell(C)=1+\ell([u,b]) =2+\ell([w,b])\]

and, similarly,

\[\ell(D)=1+\ell([v,b]) =2+\ell([w,b]).\]

Hence $$\ell(C)=\ell(D)$.$ By induction, all maximal chains in every interval of $$L$$ have the same length. It follows from Proposition 1.3.17 that $$L$$ is graded. We now prove that its rank function $\rho$ is submodular. First, observe that if $$u\lessdot v$,$ then, for any $$z\in L$,$

\[u\vee z=v\vee z \quad\text{or}\quad u\vee z\lessdot v\vee z.\]

Indeed, since $$u\le v\wedge(u\vee z)\le v$,$ we have either $v\wedge(u\vee z)=v$ or $$v\wedge(u\vee z)=u$.$ In the first case, $$v\le u\vee z$,$ so that $$u\vee z=v\vee z$.$ In the second case, upper semimodularity gives $$u\vee z\lessdot v\vee(u\vee z)=v\vee z$.$ Now let $$x,y\in L$,$ and choose a maximal chain in $$[x\wedge y,x]$,$ say

\[x\wedge y=x_0\lessdot x_1 \lessdot\cdots\lessdot x_k=x.\]

Since $$L$$ is graded, we have $$k=\rho(x)-\rho(x\wedge y)$.$ For each $$i=0,\ldots,k$,$ put $$y_i=x_i\vee y$.$ The preceding observation shows that, for every $$i=1,\ldots,k$,$ either

\[y_{i-1}=y_i\quad \text{or} \quad y_{i-1}\lessdot y_i.\]

Consequently, $$\rho(y_i)-\rho(y_{i-1})\le 1$.$ Since $$y_0=y$$ and $$y_k=x\vee y$,$ it follows that

\[\begin{aligned} \rho(x\vee y)-\rho(y) &=\sum_{i=1}^{k} \left(\rho(y_i)-\rho(y_{i-1})\right)\\ &\le k\\ &=\rho(x)-\rho(x\wedge y). \end{aligned}\]

Therefore $\rho$ is submodular. Conversely, suppose that $$L$$ is graded and its rank function $\rho$ is submodular. Let $x,y\in L$ satisfy $$x\wedge y\lessdot x$.$ Then, by submodularity,

\[\rho(x\vee y) - \rho(y) \le \rho(x)-\rho(x\wedge y)=1.\]

Furthermore, $$x\not\le y$,$ since otherwise $$x\wedge y=x$,$ contradicting $$x\wedge y\lessdot x$.$ Thus $$y<x\vee y$,$ and Proposition 1.3.17 gives $$0<\rho(x\vee y)-\rho(y)\le 1$.$ Since the rank function takes integer values, we conclude that $$\rho(x\vee y)-\rho(y) = 1$.$ By Proposition 1.3.17, $$\ell([y,x\vee y])=1$,$ so $$y\lessdot x\vee y$.$ Hence $$L$$ is upper semimodular. $\square$

Theorem 1.3.20. A lattice $$L$$ is modular if and only if $$L$$ is graded and its rank function is modular.

Proof. Suppose that $$L$$ is modular. Since modularity implies upper semimodularity, $$L$$ is graded by Theorem 1.3.19. Let $x,y\in L$ and let $\rho$ be the rank function on $$L$.$ Then we have

\[[x\wedge y,x] \cong [y,x\vee y]\]

by Theorem 1.3.14. Since order isomorphisms preserve covering relations, the lengths of the two intervals are the same. Hence, by Proposition 1.3.17,

\[\begin{aligned} \rho(x)-\rho(x\wedge y) &=\ell([x\wedge y,x])\\ &=\ell([y,x\vee y])\\ &=\rho(x\vee y)-\rho(y), \end{aligned}\]

proving that $\rho$ is modular. Conversely, suppose that $$L$$ is graded and its rank function $\rho$ is modular. Let $x,y,z\in L$ with $$x\le z$,$ and let $u = x\vee (y\wedge z)$ and $$v=(x\vee y)\wedge z$.$ Since $x\le z$ and $\rho$ is modular, we have

\[\begin{align} \rho(u) &= \rho(x) + (\rho(y\wedge z) -\rho(x\wedge y)),\\ \rho(v) &= \rho(z) -(\rho(y\vee z) - \rho(x\vee y)), \end{align}\]

and

\[\rho(x) = \rho(x\wedge y) + (\rho(x\vee y) - \rho(y)).\]

Therefore

\[\begin{align} \rho(u) &= \rho(x) + (\rho(y\wedge z) -\rho(x\wedge y))\\ &= \rho(x\wedge y) + (\rho(y\vee z) -\rho(y))\\ &= \rho(x\wedge y) + (\rho(z) - \rho(y\wedge z))\\ &= \rho(v). \end{align}\]

If $$u<v$,$ then $$\ell([u,v])\ge 1$,$ contradicting $$\rho(u)=\rho(v)$.$ Hence $$u=v$,$ so that $$x\vee(y\wedge z) = (x\vee y)\wedge z$.$ By Definition 1.3.13, $$L$$ is modular. $\square$