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 .
Read more about this topic: Free Lattice
Famous quotes containing the words word and/or problem:
“New is a word for fools in towns who think
Style upon style in dress and thought at last
Must get somewhere.”
—Robert Frost (1874–1963)
“The government is huge, stupid, greedy and makes nosy, officious and dangerous intrusions into the smallest corners of life—this much we can stand. But the real problem is that government is boring. We could cure or mitigate the other ills Washington visits on us if we could only bring ourselves to pay attention to Washington itself. But we cannot.”
—P.J. (Patrick Jake)