As free objects, they have the universal property.
Because the concept of a lattice can be axiomatised in terms of two operations
satisfying certain identities, the category of all lattices constitute a variety (universal algebra), and thus there exist (by general principles of universal algebra) free objects within this category: lattices where only those relations hold which follow from the general axioms.
These free lattices may be characterised using the relevant universal property.
is left adjoint to the forgetful functor from lattices to their underlying sets.
It is frequently possible to prove things about the free lattice directly using the universal property, but such arguments tend to be rather abstract, so a concrete construction provides a valuable alternative presentation.
is straightforward to give; this helps illustrate several features of the definition by way of universal property.
may be realised as the set of all finite nonempty subsets of
, with ordinary set union as the join operation
can be written as a finite union of elements on the form
as just a set: The actual structure of the free lattice
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.
This set of words contains many expressions that turn out to denote equal values in every lattice.
The word problem for free bounded lattices is the problem of determining which of these elements of W(X) denote the same element in the free bounded lattice FX, and hence in every bounded lattice.
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: This defines a preorder ≤~ on W(X), so an equivalence relation can be defined by w ~ v when w ≤~ v and v ≤~ w. One may then show that the partially ordered quotient space W(X)/~ is the free bounded lattice FX.
[1][2] The equivalence classes of W(X)/~ are the sets of all words w and v with w ≤~ v and v ≤~ w. Two well-formed words v and w in W(X) denote the same value in every bounded lattice if and only if w ≤~ v and v ≤~ w; the latter conditions can be effectively decided using the above inductive definition.
The case of lattices that are not bounded is treated similarly, omitting rules 2. and 3. in the above construction.
The solution of 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.
By induction, this eventually yields a sublattice free on countably many generators.
One then shows, using the inductive relations of the word problem, that pn+1 is strictly greater[4] than pn, and therefore all infinitely many words pn evaluate to different values in the free lattice FX.
Another corollary is that the complete free lattice (on three or more generators) "does not exist", in the sense that it is a proper class.
To define a complete lattice in terms of relations, it does not suffice to use the finitary relations of meet and join; one must also have infinitary relations defining the meet and join of infinite subsets.
For example, the infinitary relation corresponding to "join" may be defined as Here, f is a map from the elements of a cardinal N to FX; the operator
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.
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.