Complete Lattice Article Index for
Complete 		Website Links For
Complete 		 

Information About

Complete Lattice
  CATEGORIES ABOUT COMPLETE LATTICE
   
lattice theory
   
closure operators
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



Complete lattices must not be confused with Complete Partial Order s (''cpo''s), which constitute a strictly more general class of partially ordered sets. More specific complete lattices are Complete Boolean Algebra s and Complete Heyting Algebra s (''locales'').


FORMAL DEFINITION


A Partially Ordered Set (''L'', ≤) is a ''complete lattice'' if every Subset ''A'' of ''L'' has both a Greatest Lower Bound (infimum, meet) and a Least Upper Bound (supremum, join) in (''L'', ≤). These are denoted by:

: \bigwedge''A'' (meet) and \bigvee''A'' (join).

Note that in the special case where ''A'' is the Empty Set the meet of ''A'' will be the Greatest Element of ''L''. Likewise, the join of the empty set yields the Least Element . Since the definition also assures the existence of binary meets and joins, complete lattices do thus form a special class of Bounded Lattice s.

More implications of the above definition are discussed in the article on Completeness Properties in order theory.


Complete semilattices


It is a well-known fact of order theory that arbitrary meets can be expressed in terms of arbitrary joins and vice versa (for details, see Completeness (order Theory) ). In effect, this means that it is sufficient to require the existence of either all meets or all joins to obtain the class of all complete lattices.

As a consequence, some authors use the terms ''complete Meet-semilattice '' or ''complete Join-semilattice '' as another way to refer to complete lattices. Though similar on objects, the terms entail different notions of Homomorphism s, as will be explained in the below section on morphisms.

On the other hand, some authors have no use for this distinction of morphisms (especially since the emerging concepts of "complete semilattice morphisms" can as well be specified in general terms). Consequently, ''complete meet-semilattices'' have also been defined as those Meet-semilattice s that are also Complete Partial Order s. 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). This discussion is also found in the article on Semilattice 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 \bigwedge''A'' and \bigvee''A'', as defined in ''L'', are actually in ''M''.Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. '' A Course in Universal Algebra. '' Springer-Verlag. ISBN 3-540-90578-2 (A monograph available free online).


EXAMPLES


  • The Power Set of a given set, ordered by Inclusion . The supremum is given by the Union and the infimum by the Intersection of subsets.

  • The Unit Interval {Link without Title} and the Extended Real Number Line , with the familiar total order and the ordinary Suprema and Infima . Indeed, a totally ordered set (with its Order Topology ) is Compact as a Topological Space if it is complete as a lattice.

  • The non-negative Integer s, ordered by Divisibility . The least element of this lattice is the number 1, since it divides any other number. Maybe 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 Minimum subgroup of ''G'', while the Maximum subgroup is the group ''G'' itself.

  • The submodules of a Module , ordered by inclusion. The supremum is given by the sum of submodules and the infimum by the intersection.

  • The Ideals of a Ring , 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 , ordered by inclusion. The supremum is given by the union of open sets and the infimum by the Interior of the intersection.

  • The Convex Subset s of a Real or Complex Vector Space , ordered by inclusion. The infimum is given by the intersection of convex sets and the supremum by the Convex Hull of the union.

  • The Topologies on a set, ordered by inclusion. The infimum is given by the intersection of topologies, and the supremum by the topology generated by the union of topologies.

  • The lattice of all Transitive Relation s on a set.

  • The lattice of all sub-multisets of a Multiset .

  • The lattice of all Equivalence Relation s on a set; the equivalence relation ~ is considered to be smaller (or "finer") than ≈ if ''x''~''y'' always implies ''x''≈''y''.



MORPHISMS OF COMPLETE LATTICES


The traditional morphisms between complete lattices 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

  • f(\bigwedge A) = \bigwedge\{f(a)\mid a\in A\} and

  • f(\bigvee A) = \bigvee\{f(a)\mid a\in A\},


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, that are only required to preserve all meets or all joins, which are indeed inequivalent conditions. This notion may be considered as a homomorphism of complete meet-semilattices or complete join-semilattices, respectively.

Furthermore, morphisms that preserve all joins are equivalently characterized as the ''lower adjoint'' part of a unique to the one with join-preserving mappings (lower adjoints).


FREE CONSTRUCTION AND COMPLETION


Free "complete semilattices"


As usual, the construction of Free Object s depends on the chosen class of morphisms. Let us first consider functions that preserve all joins (i.e. lower adjoints of Galois connections), since this case is simpler than the situation for complete homomorphisms. Using the aforementioned terminology, this could be called a ''free complete join-semilattice''.

Using the standard definition from to the Forgetful Functor from complete lattices to their underlying sets.

Free complete lattices in this sense can be constructed very easily: the complete lattice generated by some set ''S'' is just the Powerset 2''S'', i.e. the set of all subsets of ''S'', ordered by Subset Inclusion . The required unit ''i'':''S''→2''S'' maps any element ''s'' of ''S'' to the singleton set {''s''}. Given a mapping ''f'' as above, the function ''f°'':2S→''M'' is defined by