Editing Complete lattice (section)

== Free construction and completion ==
{{Tone|section|date=April 2024}}
=== Free "complete semilattices" ===
The construction of [[free object]]s depends on the chosen class of morphisms. Functions that preserve all joins (i.e. lower adjoints of Galois connections) are called ''free complete join-semilattices''.

The standard definition from [[universal algebra]] states that a free complete lattice over a generating set <math>S</math> is a complete lattice <math>L</math> together with a function <math>i: S \rightarrow L</math>, such that any function <math>f</math> from <math>S</math> to the underlying set of some complete lattice <math>M</math> can be ''factored uniquely'' through a morphism <math>f^ \circ</math> from <math>L</math> to <math>M</math>. This means that <math>f(s) = f^\circ(i(s))</math> for every element <math>s</math> of <math>S</math>, and that <math>f^\circ</math> is the only morphism with this property. Hence, there is a functor from the category of sets and functions to the category of complete lattices and join-preserving functions which is [[adjoint functors|left adjoint]] to the [[forgetful functor]] from complete lattices to their underlying sets.

Free complete lattices can thus be constructed such that the complete lattice generated by some set ''<math>S</math>'' is just the [[powerset]] <math>2^S</math>, the set of all subsets of ''<math>S</math>'' ordered by [[subset|subset inclusion]]. The required unit <math>i: S \rightarrow 2^S</math> maps any element <math>s</math> of <math>S</math> to the singleton set <math>\{s\}</math>. Given a mapping <math>f</math> as above, the function <math>f^\circ : 2^S \rightarrow M</math> is defined by
 
:<math>f^\circ (X) = \bigvee \{ f(s) | s \in X \}</math>.

Then <math>f^\circ</math> transforms unions into suprema and thus preserves joins.

These considerations also yield a free construction for morphisms that preserve meets instead of joins (i.e. upper adjoints of Galois connections). The above can be [[duality (order theory)|dualized]]: free objects are given as powersets ordered by reverse inclusion, such that set union provides the meet operation, and the function <math>f^\circ</math> is defined in terms of meets instead of joins. The result of this construction is known as a ''free complete meet-semilattice''. It can be noted that these free constructions extend those that are used to obtain [[semilattice|free semilattices]], where finite sets need to be considered.

=== Free complete lattices ===
The situation for complete lattices with complete homomorphisms is more intricate. In fact, free complete lattices generally do not exist. Of course, one can formulate a word problem similar to the one for the case of [[lattice (order)|lattices]], but the collection of all possible [[word problem (mathematics)|words]] (or "terms") in this case would be a [[proper class]], because arbitrary meets and joins comprise operations for argument sets of every [[cardinality]].

This property in itself is not a problem: as the case of free complete semilattices above shows, it can well be that the solution of the word problem leaves only a set of equivalence classes. In other words, it is possible that the proper classes of all terms have the same meaning and are thus identified in the free construction. However, the equivalence classes for the word problem of complete lattices are "too small," such that the free complete lattice would still be a proper class, which is not allowed.

Now, one might still hope that there are some useful cases where the set of generators is sufficiently small for a free, complete lattice to exist. Unfortunately, the size limit is very low, and we have the following theorem:

: The free complete lattice on three generators does not exist; it is a [[proper class]].

A proof of this statement is given by Johnstone.<ref>P. T. Johnstone, ''Stone Spaces'', Cambridge University Press, 1982; ''(see paragraph 4.7)''</ref> The original argument is attributed to [[Alfred W. Hales]];<ref>[[Alfred W. Hales|A. W. Hales]], ''On the non-existence of free complete Boolean algebras'', Fundamenta Mathematicae 54: pp.45-66.</ref> see also the article on [[free lattice]]s.

=== Completion ===
<!-- This section is linked from [[Completely distributive lattice]]. See [[WP:MOS#Section management]] -->

If a complete lattice is freely generated from a given ''poset'' used in place of the set of generators considered above, then one speaks of a ''completion'' of the poset. The definition of the result of this operation is similar to the above definition of free objects, where "sets" and "functions" are replaced by "posets" and "monotone mappings". Likewise, one can describe the completion process as a functor from the category of posets with monotone functions to some category of complete lattices with appropriate morphisms that are left adjoint to the forgetful functor in the converse direction.

As long as one considers meet- or join-preserving functions as morphisms, this can easily be achieved through the so-called [[Dedekind–MacNeille completion]]. For this process, elements of the poset are mapped to (Dedekind-) ''cuts'', which can then be mapped to the underlying posets of arbitrary complete lattices in much the same way as done for sets and free complete (semi-) lattices above.

The aforementioned result that free complete lattices do not exist entails that an according free construction from a poset is not possible either. This is easily seen by considering posets with a discrete order, where every element only relates to itself. These are exactly the free posets on an underlying set. Would there be a free construction of complete lattices from posets, then both constructions could be composed, which contradicts the negative result above.