- Free lattice
In
mathematics , in the area oforder theory , a free lattice is thefree object corresponding to a lattice. As free objects, they have theuniversal property . The word problem for free lattices is also challenging.Formal definition
Any set "X" may be used to generate the free semilattice "FX". The free semilattice is defined to consist of all of the finite subsets of "X", with the semilattice operation given by ordinary
set union . The free semilattice has theuniversal property . Theuniversal morphism is FX,eta), where eta the unit map eta:X o FX which takes xin X to thesingleton set x}. The universal property is then as follows: given any map f:X o L from "X" to some arbitrary semilattice "L", there exists a unique semilattice homomorphism ilde{f}:FX o L such that f= ilde{f}circeta. The map ilde{f} may be explicitly written down; it is given by:Sin FX mapstoigveeleft{f(s)vert sin S ight}Here, igvee denotes the semilattice operation in "L". This construction may be promoted from semilattices to lattices; by construction the map ilde{f} will have the same properties as the lattice.The symbol "F" is then a
functor from thecategory of sets to the category of lattices and lattice homomorphisms. The functor "F" is left adjoint to theforgetful functor from lattices to their underlying sets. The free lattice is afree object .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 vee and wedge and the two constants (
nullary operation s) 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 "a"vee1 = 1 and "a"wedge1 ="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" vee "w2" and both "w1"<~"v" and "w2"<~"v" hold,
* "w" = "w1" wedge "w2" and either "w1"<~"v" or "w2"<~"v" holds,
* "v" = "v1" vee "v2" and either "w"<~"v1" or "w"<~"v2" holds,
* "v" = "v1" wedge "v2" and both "w"<~"v1" and "w"<~"v2" hold.This defines a
preorder <~ on W("X"), so we can define anequivalence relation given by "w"~"v" when "w"<~"v" and "v"<~"w". One may then show that the partially orderedquotient space W("X")/~ is the free lattice "FX" given above [P.Whitman, "Free Lattices", "Ann. Math." 42 (1941) pp. 325-329] [P.Whitman, "Free Lattices II", "Ann. Math." 43 (1941) pp. 104-115] . Theequivalence class es 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 [L.A. Skornjakov, "Elements of Lattice Theory" (1977) Adam Hilger Ltd. "(see pp.77-78)"] . This property is reminiscent of
SQ universality in groups.The proof that the free lattice in three generators is infinite proceeds by inductively defining
:p_{n+1}=xvee(ywedge(zvee(xwedge(yvee(zwedge p_n)))))
where "x", "y", and "z" are the three generators, and p_0=x. One then shows, using the inductive relations of the word problem, that p_{n+1} is strictly greater than p_n, and therefore that there must be an infinite number of p_n.
The complete free lattice
Another corollary is that the
complete free lattice "does not exist", in the sense that it is instead aproper class . The proof of this follows from the word problem as well. To define acomplete lattice in terms of relations, it does not suffice to use thefinitary relation s of meet and join; one must also haveinfinitary relation s defining the meet and join of infinite subsets. For example, the infinitary relation corresponding to "join" may be defined as:operatorname{sup}_N:(f:N o FX)
Here, "f" is a map from the elements of an cardinal "N" to "FX"; the operator operatorname{sup}_N denotes the supremum, in that it takes the image of "f" to its join. This is, of course, identical to "join" when "N" is a finite number; the point of this definition is to define join as a relation, even when "N" is an infinite cardinal.
The axioms of the pre-ordering of the word problem may be adjoined by the two infinitary operators corresponding to meet and join. After doing so, one then extends the definition of p_n to an ordinally indexed p_alpha given by
:p_alpha = operatorname{sup}{p_eta vert eta
when alpha is a limit ordinal. Then, as before, one may show that p_{alpha+1} is strictly greater than p_alpha. Thus, there are at least as many elements in the complete free lattice as there are ordinals, and thus, the complete free lattice cannot exist as a set, and must therefore be a proper class.
References
* Peter T. Johnstone, "Stone Spaces", Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge, 1982. (ISBN 0-521-23893-5) "(See chapter 1)"
Wikimedia Foundation. 2010.