Free Lattice - Word Problem

Word Problem

The word problem for free lattices has some interesting aspects. Consider the case of bounded lattices, i.e. algebraic structures with the two binary operations and and the two constants (nullary operations) 0 and 1. The set of all correct (well-formed) expressions that can be formulated using these operations on elements from a given set of generators X will be called W(X). This set of words contains many expressions that turn out to be equal in any lattice. For example, if a is some element of X, then a1 = 1 and a1 =a. The word problem for lattices is the problem of determining which of these elements of W(X) correspond to the same element.

The word problem may be resolved as follows. A relation <~ on W(X) may be defined inductively by setting w <~ v if and only if one of the following holds:

• w = v (this can be restricted to the case where w and v are elements of S),
• w = 0 or v = 1,
• w = w1 w2 and both w1<~v and w2<~v hold,
• w = w1 w2 and either w1<~v or w2<~v holds,
• v = v1 v2 and either w<~v1 or w<~v2 holds,
• v = v1 v2 and both w<~v1 and w<~v2 hold.

This defines a preorder <~ on W(X), so we can define an equivalence relation given by w~v when w<~v and v<~w. One may then show that the partially ordered quotient space W(X)/~ is the free lattice FX given above. The equivalence classes of W(X)/~ are the sets of all words w and v with w<~v and v<~w. The case of lattices that are not bounded is treated similarly, using only the two binary operations in the above construction.

The word problem on free lattices has several interesting corollaries. One is that the free lattice of a three-element set of generators is infinite. In fact, one can even show that every free lattice on three generators contains a sublattice which is free for a set of four generators. By induction, this eventually yields a sublattice free on countably many generators. This property is reminiscent of SQ-universality in groups.

The proof that the free lattice in three generators is infinite proceeds by inductively defining

where x, y, and z are the three generators, and . One then shows, using the inductive relations of the word problem, that is strictly greater than, and therefore that there must be an infinite number of .