Order, lattices, ordered algebraic structures Lattices: basic notions Theorem

Word problem for free lattices

Builds on Free lattice Join and meet Term Computable set

Statement

Let $X$ be a set and let $\mathrm{FL}(X)$ be the free lattice on $X$ . For lattice terms $s$ and $t$ over $X$ , write $s \le t$ when the value of $s$ is below the value of $t$ in $\mathrm{FL}(X)$ . Then $s \le t$ holds if and only if one of the following holds:

$s$ and $t$ are the same letter $x \in X$ ;
$s = s_1 \vee s_2$ , and $s_1 \le t$ and $s_2 \le t$ ;
$t = t_1 \wedge t_2$ , and $s \le t_1$ and $s \le t_2$ ;
$s$ is a letter $x \in X$ , $t = t_1 \vee t_2$ , and $x \le t_1$ or $x \le t_2$ ;
$s = s_1 \wedge s_2$ , $t$ is a letter $x \in X$ , and $s_1 \le x$ or $s_2 \le x$ ;
$s = s_1 \wedge s_2$ , $t = t_1 \vee t_2$ , and $s_1 \le t$ or $s_2 \le t$ or $s \le t_1$ or $s \le t_2$ .

Consequently, equality of two lattice terms in $\mathrm{FL}(X)$ is decidable: $s = t$ in $\mathrm{FL}(X)$ exactly when $s \le t$ and $t \le s$ .

Remarks

In each clause the comparisons on the right involve terms of smaller total length, so the clauses give a recursive algorithm to decide $s \le t$ . The "if" direction holds in every lattice. The "only if" direction is the content of the theorem; clause 6 is Whitman's condition. Example: $x \wedge (y \vee z) \le (x \wedge y) \vee (x \wedge z)$ fails in $\mathrm{FL}(\set{x, y, z})$ . By clause 6 it would need one of $x \le (x \wedge y) \vee (x \wedge z)$ , $y \vee z \le (x \wedge y) \vee (x \wedge z)$ , $x \wedge (y \vee z) \le x \wedge y$ or $x \wedge (y \vee z) \le x \wedge z$ , and the clauses refute each of them in turn. So the distributive law is not an identity of all lattices.

Going deeper

For a student

The word problem asks whether two terms define the same element of a free algebra. For finitely presented groups it can be undecidable, but for free lattices it has this explicit solution, due to Whitman. The procedure also decides whether a lattice identity holds in all lattices. Indeed, $s = t$ holds in every lattice exactly when $s = t$ in the free lattice on the letters of $s$ and $t$ . Whitman also used these rules to show that each element of $\mathrm{FL}(X)$ has a canonical form: a shortest term, unique up to commutativity and associativity.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Computable set concept
Free lattice concept
Join and meet concept
Term concept
Word problem for free lattices statement

Tag	`Z86VGP5RMG`
URI	`m2://Z86VGP5RMG`
Kind	statement, theorem
Writing	W0 stub
MSC	06B25, 03D40
Status	This copy of the site has no build data. Run `m2 status Z86VGP5RMG`.
About	Free lattice
Uses	Free lattice, Join and meet, Term, Computable set