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:
“Here lies our Sovereign Lord, the King
Whose word no man relies on:
He never said a foolish thing
Nor ever did a wise one.”
—John Wilmot, 2nd Earl Of Rochester (1647–1680)
“The great problem of American life [is] the riddle of authority: the difficulty of finding a way, within a liberal and individualistic social order, of living in harmonious and consecrated submission to something larger than oneself.... A yearning for self-transcendence and submission to authority [is] as deeply rooted as the lure of individual liberation.”
—Wilfred M. McClay, educator, author. The Masterless: Self and Society in Modern America, p. 4, University of North Carolina Press (1994)