In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a complete lattice is a
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...
in which ''all'' subsets have both a
supremum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
(join) and an
infimum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
(meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' Specifically, every non-empty finite lattice is complete. Complete lattices appear in many applications in mathematics and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
. Being a special instance of
lattices, they are studied both in
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
and
universal algebra
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of study, ...
.
Complete lattices must not be confused with
complete partial order In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central rol ...
s (''cpo''s), which constitute a strictly more general class of partially ordered sets. More specific complete lattices are
complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...
s and
complete Heyting algebra
In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra that is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, ...
s (''locales'').
Formal definition
A
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...
(''L'', ≤) is a ''complete lattice'' if every
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
''A'' of ''L'' has both a
greatest lower bound (the
infimum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
, also called the ''meet'') and a
least upper bound
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
(the
supremum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
, also called the ''join'') in (''L'', ≤).
The ''meet'' is denoted by
, and the ''join'' by
.
In the special case where ''A'' is the
empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
, the meet of ''A'' will be the
greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an elem ...
of ''L''. Likewise, the join of the empty set yields the
least element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an elem ...
. Since the definition also assures the existence of binary meets and joins, complete lattices thus form a special class of
bounded lattice
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper boun ...
s.
More implications of the above definition are discussed in the article on
completeness properties in order theory.
Complete semilattices
In order theory, arbitrary meets can be expressed in terms of arbitrary joins and vice versa (for details, see
completeness (order theory) In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of the te ...
). 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
In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
'' or ''complete
join-semilattice'' as another way to refer to complete lattices. Though similar on objects, the terms entail different notions of
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
, 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
In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
s that are also
complete partial order In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central rol ...
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
In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
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
and
, as defined in ''L'', are actually in ''M''.
If the above requirement is lessened to require only non-empty meet and joins to be in ''L'', the sublattice ''M'' is called a ''closed sublattice'' of ''M''.
Conditionally Complete Latices
A lattice is said to be "''conditionally complete''" if it satisfies
either or both of the following properties:
* Any subset bounded above has a
least upper bound
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
* Any subset bounded below has a
greatest lower bound
Examples
* Any non-empty finite lattice is trivially complete.
* The
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of a given set, ordered by
inclusion
Inclusion or Include may refer to:
Sociology
* Social inclusion, aims to create an environment that supports equal opportunity for individuals and groups that form a society.
** Inclusion (disability rights), promotion of people with disabiliti ...
. The supremum is given by the
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
and the infimum by the
intersection of subsets.
* The
unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysis, ...
,1and the
extended real number line
In mathematics, the affinely extended real number system is obtained from the real number system \R by adding two infinity elements: +\infty and -\infty, where the infinities are treated as actual numbers. It is useful in describing the algebra ...
, with the familiar total order and the ordinary
suprema and
infima
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
. Indeed, a totally ordered set (with its
order topology
In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets.
If ''X'' is a totally ordered set, t ...
) is
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
as a
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
if it is complete as a lattice.
* The non-negative
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s, ordered by
divisibility
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
. 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
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...
and the infimum by the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
. 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
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
here is the usual set-theoretic intersection, the
supremum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
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 is the
minimum
In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given r ...
subgroup of ''G'', while the
maximum
In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given r ...
subgroup is the group ''G'' itself.
* The submodules of a
module
Module, modular and modularity may refer to the concept of modularity. They may also refer to:
Computing and engineering
* Modular design, the engineering discipline of designing complex devices using separately designed sub-components
* Mo ...
, ordered by inclusion. The supremum is given by the sum of submodules and the infimum by the intersection.
* The
ideals of a
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
, 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
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
, 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
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex ...
s of a
real
Real may refer to:
Currencies
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Music Albums
* ''Real'' (L'Arc-en-Ciel album) (2000)
* ''Real'' (Bright album) (2010) ...
or
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
, 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
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...
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
In mathematics, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive.
Definition
A ho ...
s on a set.
* The lattice of all sub-multisets of a
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
.
* The lattice of all
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
s on a set; the equivalence relation ~ is considered to be smaller (or "finer") than ≈ if ''x''~''y'' always implies ''x''≈''y''.
* The lattice of self-adjoint projections (also known as orthogonal projections) of a von Neumann algebra.
Locally finite complete lattices
A complete lattice ''L'' is said to be locally finite if the supremum of any infinite subset is equal to 1, or equivalently, the set
is finite for any
. The lattice (N, , ) is locally finite. Note that in this lattice, the element generally denoted "0" is actually 1 and vice versa.
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
The word preserve may refer to:
Common uses
* Fruit preserves, a type of sweet spread or condiment
* Nature reserve, an area of importance for wildlife, flora, fauna or other special interest, usually protected
Arts, entertainment, and media
...
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
*
and
*
,
for all subsets ''A'' of ''L''. Such functions are automatically
monotonic
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...
, 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 joins (giving a
category
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
* Category of being
* ''Categories'' (Aristotle)
* Category (Kant)
* Categories (Peirce) ...
Sup) or all meets (giving a category Inf), which are indeed inequivalent conditions. This notion may be considered as a homomorphism 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 ''P'' and ''Q'', these are given by pairs of monotone functions ''f'' and ''g'' such that
where ''f'' is called the ''lower adjoint'' and ''g'' is called the ''upper adjoint''. By the
adjoint functor theorem
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kno ...
, 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 boils down to considering Galois connections as morphisms. This also yields the insight that the introduced morphisms do basically describe just two different categories of complete lattices: one with complete homomorphisms and one with meet-preserving functions (upper adjoints),
dual to the one with join-preserving mappings (lower adjoints).
A particularly important special case is for lattices of subsets ''P(X)'' and ''P(Y)'' and a function from ''X'' to ''Y''. In this case, the direct image and inverse image maps between the power sets are upper and lower adjoints to each other, respectively.
Free construction and completion
Free "complete semilattices"
As usual, the construction of
free object
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. Informally, a free object over a set ''A'' can be thought of as being a "generic" algebraic structure over ''A'': the only equations that hold between eleme ...
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
universal algebra
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of study, ...
, a free complete lattice over a generating set ''S'' is a complete lattice ''L'' together with a function ''i'':''S''→''L'', such that any function ''f'' from ''S'' to the underlying set of some complete lattice M can be ''factored uniquely'' through a morphism ''f''° from ''L'' to ''M''. Stated differently, for every element ''s'' of ''S'' we find that ''f''(''s'') = ''f''°(''i''(''s'')) and that ''f''° is the only morphism with this property. These conditions basically amount to saying that there is a functor from the category of sets and functions to the category of complete lattices and join-preserving functions which is
left adjoint
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kno ...
to the
forgetful functor In mathematics, in the area of category theory, a forgetful functor (also known as a stripping functor) 'forgets' or drops some or all of the input's structure or properties 'before' mapping to the output. For an algebraic structure of a given sign ...
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
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset ...
. The required unit ''i'':''S''→2
''S'' maps any element ''s'' of ''S'' to the singleton set . Given a mapping ''f'' as above, the function ''f''°:2
S→''M'' is defined by
:
.
Then ''f''° transforms unions into suprema and thus preserves joins.
Our considerations also yield a free construction for morphisms that do preserve meets instead of joins (i.e. upper adjoints of Galois connections). In fact, we merely have to
dualize what was said above: free objects are given as powersets ordered by reverse inclusion, such that set union provides the meet operation, and the function ''f''° is defined in terms of meets instead of joins. The result of this construction could be called a ''free complete meet-semilattice''. One should also note how these free constructions extend those that are used to obtain
free semilattices, where we only need to consider finite sets.
Free complete lattices
The situation for complete lattices with complete homomorphisms obviously is more intricate. In fact, free complete lattices do generally not exist. Of course, one can formulate a word problem similar to the one for the case of
lattices, but the collection of all possible
words
A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no conse ...
(or "terms") in this case would be a
proper class
Proper may refer to:
Mathematics
* Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact
* Proper morphism, in algebraic geometry, an analogue of a proper map for ...
, because arbitrary meets and joins comprise operations for argument-sets of every
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
.
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 proper classes of the class 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
Proper may refer to:
Mathematics
* Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact
* Proper morphism, in algebraic geometry, an analogue of a proper map for ...
.
A proof of this statement is given by Johnstone; the original argument is attributed to
Alfred W. Hales
Alfred Washington Hales (born November 30, 1938) is an American mathematician, a professor emeritus of mathematics at the University of California, Los Angeles, and one of the namesakes of the Hales–Jewett theorem. He was born in Pasadena, Califo ...
;
[ A. W. Hales, ''On the non-existence of free complete Boolean algebras'', Fundamenta Mathematicae 54: pp.45-66.] see also the article on
free lattices.
Completion
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 is 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
In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed ...
. 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
Already G. Birkhoff's ''Lattice Theory'' book
[Garrett Birkhoff, ''Lattice Theory'', AMS Colloquium Publications Vol. 25, ] 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 systems. Closure systems are intersection-closed families of sets. When ordered by the subset relation ⊆, they are complete lattices.
A special instance of Birkhoff's construction starts from an arbitrary poset ''(P,≤)'' and constructs the Galois connection from the order relation ≤ 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
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
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
increasing and idempotent (but not necessarily extensive) self-map.
The identity mapping obviously 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 In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:
:''Let'' (''L'', ≤) ''be a complete lattice and let f : L → L be an monotonic function ...
, which states that the set of
fixed points 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, since these are instances of the theorem.
See also
*
lattice (order)
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper bou ...
.
References
{{DEFAULTSORT:Complete Lattice
Closure operators
Lattice theory