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:
“He began therefore to invest the fortress of my heart by a circumvallation of distant bows and respectful looks; he then entrenched his forces in the deep caution of never uttering an unguarded word or syllable. His designs being yet covered, he played off from several quarters a large battery of compliments. But here he found a repulse from the enemy by an absolute rejection of such fulsome praise, and this forced him back again close into his former trenches.”
—Sarah Fielding (1710–1768)
“I don’t have any problem with a reporter or a news person who says the President is uninformed on this issue or that issue. I don’t think any of us would challenge that. I do have a problem with the singular focus on this, as if that’s the only standard by which we ought to judge a president. What we learned in the last administration was how little having an encyclopedic grasp of all the facts has to do with governing.”
—David R. Gergen (b. 1942)