Franklin's Notes


Finite lattice

A finite lattice is simply a lattice with finitely many elements - but finite lattices have sufficiently many uniquely interesting properties that they deserve their own treatment. First of all, the consideration of join-irreducible elements in finite lattices is very fruitful. Here's an example of a useful property:

Proposition 1. Every finite lattice has a maximal element, denoted $1$, and a minimal element, denoted $0$.

Proof. The join of all elements of a finite lattice $L$ is an upper bound for each element of the lattice, and is hence maximal. The meet of all elements of a finite lattice $L$ is similarly a lower bound for each element of the lattice and therefore minimal. $\blacksquare$

This is not true of general lattices, for instance any infinite totally ordered set without endpoints comprises a lattice without maximal or minimal elements. We also have the following, beginning our study of join-irreducible elements:

Proposition 2. Every element of a finite lattice can be written as the join of some collection of join-irreducible elements.

Proof. Each join-reducible element $\ell\in L$ can be written in the form $\ell = \ell_1\lor\ell_2$ for two strictly smaller elements $\ell_1,\ell_2<\ell$ by the definition of join-reducibility. If $\ell_1,\ell_2$ can be written as a join of join-irreducible elements, so can $\ell=\ell_1\lor\ell_2$. If we assume for the sake of contradiction that $\ell$ cannot be written as a join of join-irreducible elements, then it must be the case that at least one of $\ell_1$ and $\ell_2$ must also be inexpressible in this form. Let $\ell'$ be either $\ell_1$ or $\ell_2$, whichever one fails to be a join of join-irreducibles (or either one, if they both fail). We must also have $\ell'$ be join-reducible, for otherwise it is a join of join-irreducibles (namely itself), so we may repeat the process with $\ell'=\ell'_1\lor\ell'_2$ to obtain $\ell' < \ell'$, and so on. In this way, we obtain a chain which is impossible by the finitude of $L$. Hence, $\ell$ must be expressible as a join of join-irreduble elements, to the contrary of our assumption. $\blacksquare$

Proposition 3. Every element $\ell\in L$ of a finite lattice $L$ is the join of the join-irreducible elements that are less than or equal to it. That is, if then $\ell = \lor(W_\ell)$.

Proof. We have established above that $\ell$ is the join of some number of join-irreducible elements of $L$, so that where each of these $w_i$ is an element of $W_\ell$, since the join of any number of elements of a lattice is necessarily greater than each of them, and hence $\ell\ge w_i$. If $w_1,\cdots,w_k$ are all of the elements of $W_\ell$, then the proposition holds in this case. If not, let $w_{k+1},\cdots,w_{n}$ be the elements of $W_\ell\backslash{w_1,\cdots,w_k}$. Then we also have since the $w_{k+1},\cdots,w_n$ are $\leq \ell$ by definition. Hence, the proposition is proven. $\blacksquare$

In finite distributive lattices , this representation of $\ell\in L$ as a join of join-irreducible elements is unique in a certain sense! Let us say that a set of join-irreducible elements $W\subset L$ is lower if $w'\in W$ whenever $w'$ is join-irreducible and $w'\leq w$ for some $w\in W$. We need the following lemma before stating our uniqueness theorem:

Proposition 4. If $w$ is join-irreducible and $w\leq \ell_1\lor\ell_2$ in a distributive lattice $L$, then we have that either $w\leq\ell_1$ or $w\leq\ell_2$.

Proof. Let $L$ be distributive and $w\in L$ join-irreducible, with $w\leq\ell_1\lor\ell_2$. Then we have that and by distributivity However, $w$ is greater than or equal to both $\ell_1\land w$ and $\ell_2\land w$, meaning that $w$ is also greater than or equal to their join. Thus, But since $w$ was assumed to be join-irreducible, this cannot be a decomposition of $w$ into two strictly smaller elements of the lattice, meaning that either $w=\ell_1\land w$ or $w=\ell_2\land w$, and therefore either $w\leq\ell_1$ or $w\leq\ell_2$. $\blacksquare$

Finally, we have the following theorem about uniqueness of representations in finite distributive lattices, sometimes known as Birkhoff's Theorem or The Fundamental Theorem of Finite Distributive Lattices:

Proposition 5. Any element $\ell\in L$ of a finite distributive lattice $L$ can be uniquely represented as the join of a lower set of join-irreducible elements, namely $W_\ell$, the set of all join-irreducible elements of $L$ less than or equal to $\ell$.

Proof. We have seen in a previous proposition that such a representation always exists. For uniqueness, suppose that there are two distinct lower sets $W_\ell,W'\ell\subset L$ such that the join of the elements of either set equals $\ell$. Without loss of generality, since the sets are distinct, we may suppose that $w\in W\ell$ is some element not contained in $W'\ell$. But by the previous theorem, since the join of elements of $W\ell$ equals the join of the elements of $W'\ell$, we have inductively that $w$ must be less than or equal to some element of $W'\ell$. But since $w$ is join-irreducible and $W'\ell$ is lower, this means that $w\in W'\ell$ after all, which is a contradiction. $\blacksquare$

topology

combinatorics

set-theory

back to home page