free lattice

In mathematics, in the area of order theory, a free lattice is the free object corresponding to a lattice. As free objects, they have the universal property.

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 the universal property. The universal morphism is , where η is the unit map η: ''X'' → ''FX'' which takes ''x'' ∈ ''X'' to the singleton set . The universal property is then as follows: given any map ''f'': ''X'' → ''L'' from ''X'' to some arbitrary semilattice ''L'', there exists a unique semilattice homomorphism $\tilde:FX \to L$ such that $f = \tilde\circ\eta$. The map $\tilde$ may be explicitly written down; it is given by
:$S \in FX \mapsto \bigvee\left\$
where $\bigvee$ denotes the semilattice operation in ''L''. This construction may be promoted from semilattices to lattices; by construction the map $\tilde$ will have the same properties as the lattice.

The construction ''X'' ↦ ''FX'' is then a functor from the category of sets to the category of lattices. The functor ''F'' is left adjoint to the forgetful functor from lattices to their underlying sets. The free lattice is a free object.

Word problem

The word problem for free lattices and free bounded lattices is decidable using an inductive relation. The solution 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

:''p''_''n''+1 = ''x'' ∨ (''y'' ∧ (''z'' ∨ (''x'' ∧ (''y'' ∨ (''z'' ∧ ''p''_''n'')))))

where ''x'', ''y'', and ''z'' are the three generators, and ''p''₀ = ''x''. One then shows, using the inductive relations of the word problem, that ''p''_''n''+1 is strictly greaterthat is, ''p''_''n'' ≤_~ ''p''_''n''+1, but not ''p''_''n''+1 ≤_~ ''p''_''n''
than ''p''_''n'', and therefore all infinitely many words ''p''_''n'' evaluate to different values in the free lattice ''FX''.

The complete free lattice

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. The proof of this follows from the word problem as well. 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

:$\operatorname_N:(f:N\to FX)$

Here, ''f'' is a map from the elements of a cardinal ''N'' to ''FX''; the operator $\operatorname_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\$

when $\alpha$ is a limit ordinal. Then, as before, one may show that $p_$ 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)''

Lattice theory
Free algebraic structures
Combinatorics on words