Editing Complete lattice

{{Short description|Partially ordered set in which all subsets have both a supremum and infimum}}
[[File:Hasse Diagram of Subgroup Lattice of D4.png|thumb|400px|The complete [[Lattice of subgroups|subgroup lattice]] for D4, the [[dihedral group]] of the square. This is an example of a complete lattice.]]

In [[mathematics]], a '''complete lattice''' is a [[partially ordered set]] in which all subsets have both a [[supremum]] ([[Join (mathematics)|join]]) and an [[infimum]] ([[Meet (Mathematics)|meet]]). A '''conditionally complete lattice''' satisfies at least one of these properties for bounded subsets. For comparison, in a general [[Lattice (order)|lattice]], only ''pairs'' of elements need to have a supremum and an infimum. Every non-empty finite lattice is complete, but infinite lattices may be incomplete.

Complete lattices appear in many applications in mathematics and [[computer science]]. Both [[order theory]] and [[universal algebra]] study them as a special class of lattices.

Complete lattices must not be confused with [[complete partial order]]s (CPOs), a more general class of partially ordered sets. More specific complete lattices are [[complete Boolean algebra]]s and [[complete Heyting algebra]]s (locales).{{Citation needed|date=June 2024}}

== Formal definition ==
A ''complete lattice'' is a [[partially ordered set]] (''L'', ≤) such that every [[subset]] ''A'' of ''L'' has both a [[greatest lower bound]] (the [[infimum]], or ''meet'') and a [[least upper bound]] (the [[supremum]], or ''join'') in (''L'', ≤).

The ''meet'' is denoted by <math>\bigwedge A</math>, and the ''join'' by <math>\bigvee A</math>.

In the special case where ''A'' is the [[empty set]], the meet of ''A'' is the [[greatest element]] of ''L''. Likewise, the join of the empty set is the [[least element]] of ''L''. Then, complete lattices form a special class of [[bounded lattice]]s.

=== Complete sublattices ===
A sublattice ''M'' of a complete lattice ''L'' is called a ''complete sublattice'' of ''L'' if for every subset ''A'' of ''M'' the elements <math>\bigwedge A</math> and <math>\bigvee A</math>, as defined in ''L'', are actually in ''M''.<ref>Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. ''[http://www.thoralf.uwaterloo.ca/htdocs/ualg.html A Course in Universal Algebra.]''  Springer-Verlag. {{isbn|3-540-90578-2}} (A monograph available free online).</ref>

If the above requirement is lessened to require only non-empty meet and joins to be in ''M'', the sublattice ''M'' is called a ''closed sublattice'' of ''L''.

=== Complete semilattices ===
The terms ''complete [[meet-semilattice]]'' or ''complete [[join-semilattice]]'' is another way to refer to complete lattices since arbitrary meets can be expressed in terms of arbitrary joins and vice versa (for details, see [[completeness (order theory)|completeness]]). 

Another usage of "complete meet-semilattice" refers to a meet-semilattice that is [[bounded complete]] and a [[complete partial order]]. This concept is arguably the "most complete" notion of a meet-semilattice that is not yet a lattice (in fact, only the top element may be missing).

See [[semilattice]]s for further discussion between both definitions. 

===Conditionally Complete Lattices===
A lattice is said to be "''conditionally complete''" if it satisfies [[Logical disjunction|either or both]] of the following properties:<ref>{{Cite web |last=Baker |first=Kirby |date=2010 |title=Complete Lattices |url=https://www.math.ucla.edu/~baker/222a/handouts/s_complete.pdf |access-date=8 June 2022 |website=UCLA Department of Mathematics}}</ref>

* Any subset bounded above has the [[least upper bound]].
* Any subset bounded below has the [[greatest lower bound]].

== Examples ==
* Any non-empty finite lattice is trivially complete.
* The [[power set]] of a given set when ordered by [[subset|inclusion]]. The supremum is given by the [[union (set theory)|union]] and the infimum by the [[intersection (set theory)|intersection]] of subsets.
* The non-negative [[integer]]s ordered by [[divisibility]]. The least element of this lattice is the number 1 since it divides any other number. Perhaps surprisingly, the greatest element is 0, because it can be divided by any other number. The supremum of finite sets is given by the [[least common multiple]] and the infimum by the [[greatest common divisor]]. For infinite sets, the supremum will always be 0 while the infimum can well be greater than 1. For example, the set of all even numbers has 2 as the greatest common divisor.  If 0 is removed from this structure it remains a lattice but ceases to be complete.
* The subgroups of any given group under inclusion. (While the [[infimum]] here is the usual set-theoretic intersection, the [[supremum]] of a set of subgroups is the subgroup ''generated by'' the set-theoretic union of the subgroups, not the set-theoretic union itself.) If ''e'' is the identity of ''G'', then the [[trivial group]] {''e''} is the [[partial order|minimum]] subgroup of ''G'', while the [[partial order|maximum]] subgroup is the group ''G'' itself.
* The [[ideal (ring theory)|ideals]] of a [[ring (mathematics)|ring]], when ordered by inclusion. The supremum is given by the sum of ideals and the infimum by the intersection.
* The open sets of a [[topological space]], when ordered by inclusion. The supremum is given by the union of open sets and the infimum by the [[interior (topology)|interior]] of the intersection.

=== Non-examples ===
* The [[empty set]] is not a complete lattice. If it were a complete lattice, then in particular the empty set would have an infimum and supremum in the empty set, a contradiction.
* The [[rational numbers]] <math>\mathbb{Q}</math> with the usual order ≤ is not a complete lattice. It is a lattice with <math>\bigwedge \{x, y\} = \min\{x, y\}</math> and <math>\bigvee \{x, y\} = \max\{x, y\}</math>. However, <math>\mathbb{Q}</math> itself has no infimum or supremum, nor does <math>\{ x \in \mathbb{Q} | x^2 < 2 \}</math>.

==Locally finite complete lattices==
A complete lattice ''L'' is said to be locally finite if the supremum of any infinite subset is equal to the supremal element. Denoting this supremal element "1", the condition is equivalently that the set <math>\{y \in L ~|~ y \le x\} \,\!</math> is finite for any <math>1 \ne x \in L</math>. This notation may clash with other notation, as in the case of the lattice ('''N''', |), i.e., the non-negative [[integer]]s ordered by [[divisibility]]. In this locally finite lattice, the infimal element denoted "0" for the lattice theory is the number 1 in the set '''N''' and the supremal element denoted "1" for the lattice theory is the number 0 in the set '''N'''.

== Morphisms of complete lattices ==
The traditional [[Morphism|morphisms]] between complete lattices, taking the complete lattices as the [[Object (category theory)|objects]] of a [[Category (mathematics)|category]], are the ''complete homomorphisms'' (or ''complete lattice homomorphisms''). These are characterized as functions that preserve all joins and all meets. Explicitly, this means that a function ''f: L→M'' between two complete lattices ''L'' and ''M'' is a complete homomorphism if

* <math>f\left(\bigwedge A\right) = \bigwedge\{f(a)\mid a\in A\}</math> and
* <math>f\left(\bigvee A\right) = \bigvee\{f(a)\mid a\in A\}</math>,

for all subsets ''A'' of ''L''. Such functions are automatically [[monotonic]], but the condition of being a complete homomorphism is in fact much more specific. For this reason, it can be useful to consider weaker notions of morphisms, such as those that are only required to preserve all joins (giving a [[Category (mathematics)|category]] '''Sup''') or all meets (giving a category '''Inf'''), which are indeed inequivalent conditions. These notions may also be considered as homomorphisms of complete meet-semilattices or complete join-semilattices, respectively.

=== Galois connections and adjoints ===

Furthermore, morphisms that preserve all joins are equivalently characterized as the ''lower adjoint'' part of a unique [[Galois connection]]. For any pair of preorders ''X'' and ''Y'', a Galois connection is given by a pair of monotone functions ''f'' and ''g'' from ''X'' to ''Y'' such that for each pair of elements ''x'' of ''X'' and ''y'' of ''Y''

:<math>f(x) \leq y \iff x \leq g(y)</math>

where ''f'' is called the ''lower adjoint'' and ''g'' is called the ''upper adjoint''. By the [[adjoint functor theorem]], a monotone map between any pair of preorders preserves all joins if and only if it is a lower adjoint and preserves all meets if and only if it is an upper adjoint.

As such, each join-preserving morphism determines a unique ''upper adjoint'' in the inverse direction that preserves all meets. Hence, considering complete lattices with complete semilattice morphisms (of either type, join-preserving or meet-preserving) boils down to considering Galois connections as one's lattice morphisms. This also yields the insight that three classes of morphisms discussed above basically describe just two different categories of complete lattices: one with complete homomorphisms and one with Galois connections that captures both the meet-preserving functions (upper adjoints) and their [[duality (category theory)|dual]] join-preserving mappings (lower adjoints).

A particularly important class of special cases arises between lattices of subsets of ''X'' and ''Y'', i.e., the power sets {{tmath|P(X)}} and {{tmath|P(Y)}}, given a function {{tmath|f}} from ''X'' to ''Y''. In these cases, the direct image and inverse image maps induced by {{tmath|f}} between the power sets are upper and lower adjoints to each other, respectively.

== 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.

== Representation ==
G. Birkhoff's book ''Lattice Theory'' contains a very useful representation method. It associates a complete lattice to any binary relation between two sets by constructing a [[Galois connection]] from the relation, which then leads to two dually isomorphic [[closure operator|closure systems]].<ref name="birkhoff">{{cite book |last=Birkhoff |first=Garrett |title=Lattice Theory |date=1967 |publisher=American Mathematical Society |publication-place=Providence, RI, USA |page=124 |edition=3rd |series=American Mathematical Society Colloquium Publications |volume=XXV |chapter=Complete Lattices |isbn=978-0821810255}}</ref> Closure systems are intersection-closed families of sets. When ordered by the subset relation &sube;, they are complete lattices.

A special instance of Birkhoff's construction starts from an arbitrary poset ''(P,&le;)'' and constructs the Galois connection from the order relation &le; between ''P'' and itself. The resulting complete lattice is the [[Dedekind-MacNeille completion]]. When this completion is applied to a poset that already is a complete lattice, then the result is [[order-isomorphism|isomorphic]] to the original one. Thus, we immediately find that every complete lattice is represented by Birkhoff's method, up to isomorphism.

The construction is utilized in [[formal concept analysis]], where one represents real-word data by binary relations (called ''formal contexts'') and uses the associated complete lattices (called ''concept lattices'') for data analysis. The mathematics behind formal concept analysis therefore is the theory of complete lattices.

Another representation is obtained as follows: A subset of a complete lattice is itself a complete lattice (when ordered with the induced order) if and only if it is the image of an [[closure operator|increasing and idempotent]] (but not necessarily extensive) self-map. 
The identity mapping has these two properties. Thus all complete lattices occur.

== Further results ==
Besides the previous representation results, there are some other statements that can be made about complete lattices, or that take a particularly simple form in this case. An example is the [[Knaster–Tarski theorem]], which states that the set of [[Fixed point (mathematics)|fixed point]]s of a monotone function on a complete lattice is again a complete lattice. This is easily seen to be a generalization of the above observation about the images of increasing and idempotent functions.

==References==

{{reflist}}

{{Order theory}}
{{DEFAULTSORT:Complete Lattice}}

[[Category:Closure operators]]
[[Category:Lattice theory]]