Lattice (order)

# Lattice (order)

Discussion

Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a lattice is a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set 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 binary relation that indicates that, for certain pairs of elements in the...

(also called a poset) in which any two elements have a unique supremum
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...

(the elements' least upper bound; called their join
Join and meet
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...

) and an infimum
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...

(greatest lower bound; called their meet
Join and meet
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...

). Lattices can also be characterized as algebraic structure
Algebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...

s satisfying certain axiomatic
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...

identities
Identity (mathematics)
In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...

. Since the two definitions are equivalent, lattice theory draws on both order theory
Order theory
Order theory is a branch of mathematics which investigates our 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 introduces the field and gives some basic definitions...

and universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....

. Semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...

s include lattices, which in turn include Heyting
Heyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...

and Boolean algebras. These "lattice-like" structures all admit order-theoretic as well as algebraic descriptions.

## Lattices as posets

A poset
Partially ordered set
In mathematics, especially order theory, a partially ordered set 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 binary relation that indicates that, for certain pairs of elements in the...

(L, ≤) is a lattice if it satisfies the following two axioms. Existence of binary joins:NEWLINE
NEWLINE
For any two elements a and b of L, the set {a, b} has a join: $a \lor b$ (also known as the least upper bound, or the supremum).
NEWLINE Existence of binary meets:NEWLINE
NEWLINE
For any two elements a and b of L, the set {a, b} has a meet
Meet (mathematics)
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...

: $a \land b$ (also known as the greatest lower bound, or the infimum).
NEWLINE The join and meet of a and b are denoted by $a \lor b$ and $a \land b$, respectively. This definition makes $\lor$ and $\land$ binary operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....

s. The first axiom says that L is a join-semilattice; the second says that L is a meet-semilattice. Both operations are monotone with respect to the order: a1 ≤ a2 and b1 ≤ b2 implies that a1$\lor$ b1 ≤ a2 $\lor$ b2 and a1$\land$b1 ≤ a2$\land$b2. It follows by an induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...

argument that every non-empty finite subset of a lattice has a join (supremum) and a meet (infimum). With additional assumptions, further conclusions may be possible; see Completeness (order theory)
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 . A special use of the term refers to complete partial orders or complete lattices...

for more discussion of this subject. That article also discusses how one may rephrase the above definition in terms of the existence of suitable Galois connection
Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...

s between related posets — an approach of special interest for the category theoretic
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...

approach to lattices. A bounded lattice has a greatest
Greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...

(or maximum) and least (or minimum) element, denoted 1 and 0 by convention (also called top (⊤), and bottom (⊥)). Any lattice can be converted into a bounded lattice by adding a greatest and least element, and every non-empty finite lattice is bounded, by taking the join (resp., meet) of all elements, denoted by $\bigvee A=a_1\lor\cdots\lor a_n$ (resp.$\bigwedge A=a_1\land\cdots\land a_n$) where $A=\\left\{a_1,\ldots,a_n\\right\}$. A poset is a bounded lattice if and only if every finite set of elements (including the empty set) has a join and a meet. Here, the join of an empty set of elements is defined to be the least element $\bigvee\varnothing=0$, and the meet of the empty set is defined to be the greatest element $\bigwedge\varnothing=1$. This convention is consistent with the associativity and commutativity of meet and join: the join of a union of finite sets is equal to the join of the joins of the sets, and dually, the meet of a union of finite sets is equal to the meet of the meets of the sets, i.e., for finite subsets A and B of a poset L, $\bigvee \left\left( A \cup B \right\right)= \left\left( \bigvee A \right\right) \vee \left\left( \bigvee B \right\right)$ and $\bigwedge \left\left( A \cup B \right\right)= \left\left(\bigwedge A \right\right) \wedge \left\left( \bigwedge B \right\right)$ hold. Taking B to be the empty set, $\bigvee \left\left( A \cup \emptyset \right\right)$

### General lattice

An algebraic structure
Algebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...

(L, $\lor, \land$), consisting of a set L and two binary operations
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

$\lor$, and $\land$, on L is a lattice if the following axiomatic identities hold for all elements a, b, c of L. NEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINE
 Commutative laws$a \lor b = b \lor a$,$a \land b = b\land a$. Associative laws$a \lor\left(b \lor c\right) = \left(a \lor b\right)\lor c$,$a \land\left(b \land c\right) = \left(a \land b\right)\land c$. Absorption lawAbsorption lawIn algebra, the absorption law or absorption identity is an identity linking a pair of binary operations.Two binary operations, say ¤ and *, are said to be connected by the absorption law if:...s:$a \lor\left(a \land b\right) = a$,$a \land \left(a \lor b\right) = a$.
NEWLINENEWLINE The following two identities are also usually regarded as axioms, even though they follow from the two absorption laws taken together. Idempotent laws
Idempotence
Idempotence is the property of certain operations in mathematics and computer science, that they can be applied multiple times without changing the result beyond the initial application...

$a \lor a = a$,$a \land a = a$. These axioms assert that both (L,$\lor$) and (L,$\land$) are semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...

s. The absorption laws, the only axioms above in which both meet and join appear, distinguish a lattice from a random pair of semilattices and assure that the two semilattices interact appropriately. In particular, each semilattice is the dual
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...

of the other.

### Bounded lattice

A bounded lattice is an algebraic structure of the form (L$\lor, \land$, 1, 0) such that (L$\lor, \land$) is a lattice, 0 (the lattice's bottom) is the identity element
Identity element
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...

for the join operation $\lor$, and 1 (the lattice's top) is the identity element for the meet operation $\land$. Identity laws
Identity (mathematics)
In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...

$a \lor 0 = a$,$a \land 1 = a$. See semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...

for further details.

### Connection to other algebraic structures

Lattices have some connections to the family of group-like algebraic structures
Magma (algebra)
In abstract algebra, a magma is a basic kind of algebraic structure. Specifically, a magma consists of a set M equipped with a single binary operation M \times M \rightarrow M....

. Because meet and join both commute and associate, a lattice can be viewed as consisting of two commutative semigroups having the same domain. For a bounded lattice, these semigroups are in fact commutative monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...

s. The absorption law
Absorption law
In algebra, the absorption law or absorption identity is an identity linking a pair of binary operations.Two binary operations, say ¤ and *, are said to be connected by the absorption law if:...

is the only defining identity that is peculiar to lattice theory. By commutativity and associativity one can think of join and meet as binary operations that are defined on non-empty finite sets, rather than on elements. In a bounded lattice the empty join and the empty meet can also be defined (as 0 and 1, respectively). This makes bounded lattices somewhat more natural than general lattices, and many authors require all lattices to be bounded. The algebraic interpretation of lattices plays an essential role in universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....

.

## Connection between the two definitions

An order-theoretic lattice gives rise to the two binary operations $\lor$ and $\land$. Since the commutative, associative and absorption laws can easily be verified for these operations, they make (L$\lor$$\land$) into a lattice in the algebraic sense. The ordering can be recovered from the algebraic structure because a ≤ b holds if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

a = ab. The converse is also true. Given an algebraically defined lattice (L$\lor$$\land$), one can define a partial order ≤ on L by settingNEWLINE
NEWLINE
ab if and only if a = a$\land$b, or
NEWLINE
ab if and only if b = a$\lor$b,
NEWLINE for all elements a and b from L. The laws of absorption ensure that both definitions are equivalent. One can now check that the relation ≤ introduced in this way defines a partial ordering within which binary meets and joins are given through the original operations $\lor$ and $\land$. Since the two definitions of a lattice are equivalent, one may freely invoke aspects of either definition in any way that suits the purpose at hand.

## Examples

NEWLINE
NEWLINE
• For any set A, the collection of all subsets of A (called the power set of A) can be ordered via subset inclusion
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

to obtain a lattice bounded by A itself and the null set. Set intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....

and union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...

interpret meet and join, respectively.
• NEWLINE
• For any set A, the collection of all finite subsets of A, ordered by inclusion, is also a lattice, and will be bounded if and only if A is finite.
• NEWLINE
• For any set A, the collection of all partition
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...

s of A, ordered by refinement
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...

, is a lattice.
• NEWLINE
• The natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s (including 0) in their usual order form a lattice, under the operations of "min" and "max". 0 is bottom; there is no top.
• NEWLINE
• The Cartesian square of the natural numbers, ordered by ≤ so that (a,b) ≤ (c,d) ↔ (ac) & (bd). (0,0) is bottom; there is no top.
• NEWLINE
• The natural numbers also form a lattice under the operations of taking the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...

and least common multiple
Least common multiple
In arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...

, with divisibility as the order relation: ab if a divides b. 1 is bottom; 0 is top.
• NEWLINE
• Any complete lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...

(also see below) is a (rather specific) bounded lattice. This class gives rise to a broad range of practical examples.
• NEWLINE
• The set of compact element
Compact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....

s of an arithmetic complete lattice is a lattice with a least element, where the lattice operations are given by restricting the respective operations of the arithmetic lattice. This is the specific property which distinguishes arithmetic lattices from algebraic lattices, for which the compacts do only form a join-semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...

. Both of these classes of complete lattices are studied in domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...

.
NEWLINE Most posets are not lattices, including the following. NEWLINE
NEWLINE
• A discrete poset, meaning a poset such that xy implies x = y, is a lattice if and only if it has at most one element. In particular the two-element discrete poset is not a lattice.
• NEWLINE
• Although the set {1,2,3,6} partially ordered by divisibility is a lattice, the set {1,2,3} so ordered is not a lattice because the pair 2,3 lacks a join, and it lacks a meet in {2,3,6}.
• NEWLINE
• The set {1,2,3,12,18,36} partially ordered by divisibility is not a lattice. Every pair of elements has an upper bound and a lower bound, but the pair 2,3 has three upper bounds, namely 12, 18, and 36, none of which is the least of those three under divisibility (12 and 18 do not divide each other). Likewise the pair 12,18 has three lower bounds, namely 1, 2, and 3, none of which is the greatest of those three under divisibility (2 and 3 do not divide each other).
NEWLINE Further examples of lattices are given for each of the additional properties discussed below.

## Morphisms of lattices

The appropriate notion of a morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...

between two lattices flows easily from the above algebraic definition. Given two lattices (L, ∨L, ∧L) and (M, ∨M, ∧M), a homomorphism of lattices or lattice homomorphism is a function f : LM such that NEWLINE
NEWLINE
f(aLb) = f(a) ∨M f(b), and
NEWLINE
f(aLb) = f(a) ∧M f(b).
NEWLINE Thus f is a homomorphism
Homomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...

of the two underlying semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...

s. When lattices with more structure are considered, the morphisms should 'respect' the extra structure, too. Thus, a morphism f between two bounded lattices L and M should also have the following property: NEWLINE
NEWLINE
f(0L) = 0M , and
NEWLINE
f(1L) = 1M .
NEWLINE In the order-theoretic formulation, these conditions just state that a homomorphism of lattices is a function preserving binary meets and joins. For bounded lattices, preservation of least and greatest elements is just preservation of join and meet of the empty set. Any homomorphism of lattices is necessarily monotone with respect to the associated ordering relation; see preservation of limits. The converse is not true: monotonicity by no means implies the required preservation of meets and joins, although an order-preserving
Monotonic function
In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....

bijection
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...

is a homomorphism if its inverse
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...

is also order-preserving. Given the standard definition of isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations.  If there exists an isomorphism between two structures, the two structures are said to be isomorphic.  In a certain sense, isomorphic structures are...

s as invertible morphisms, a lattice isomorphism is just a bijective lattice homomorphism. Similarly, a lattice endomorphism is a lattice homomorphism from a lattice to itself, and a lattice automorphism is a bijective lattice endomorphism. Lattices and their homomorphisms form a category
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...

.

## Properties of lattices

We now introduce a number of important properties that lead to interesting special classes of lattices. One, boundedness, has already been discussed.

### Completeness

{{main|Complete lattice}} A poset is called a complete lattice if all its subsets have both a join and a meet. In particular, every complete lattice is a bounded lattice. While bounded lattice homomorphisms in general preserve only finite joins and meets, complete lattice homomorphisms are required to preserve arbitrary joins and meets. Every poset that is a complete semilattice is also a complete lattice. Related to this result is the interesting phenomenon that there are various competing notions of homomorphism for this class of posets, depending on whether they are seen as complete lattices, complete join-semilattices, complete meet-semilattices, or as join-complete or meet-complete lattices.

### Conditional completeness

A conditionally complete lattice is a poset in which every nonempty subset that has an upper bound has a join (i.e., a least upper bound). Such lattices provide the most direct generalization of the completeness axiom
Completeness axiom
In mathematics the completeness axiom, also called Dedekind completeness of the real numbers, is a fundamental property of the set R of real numbers...

of the real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s. A conditionally complete lattice is either a complete lattice, or a complete lattice without its maximum element 1, its minimum element 0, or both.

### Distributivity

{{main|Distributive lattice}} Since lattices come with two binary operations, it is natural to ask whether one of them distributes
Distributivity
In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...

over the other, i.e. whether one or the other of the following dual
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...

laws holds for any three elements a, b, c of L: Distributivity of ∨ over ∧NEWLINE
NEWLINE
a∨(bc) = (ab) ∧ (ac).
NEWLINE Distributivity of ∧ over ∨NEWLINE
NEWLINE
a∧(bc) = (ab) ∨ (ac).
NEWLINE A lattice that satisfies the first or, equivalently (as it turns out), the second axiom, is called a distributive lattice. For an overview of stronger notions of distributivity which are appropriate for complete lattices and which are used to define more special classes of lattices such as frames
Complete Heyting algebra
In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames...

and completely distributive lattice
Completely distributive lattice
In the mathematical area of order theory, a completely distributive lattice is a complete lattice in which arbitrary joins distribute over arbitrary meets....

s, see distributivity in order theory
Distributivity (order theory)
In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima...

.

### Modularity

{{main|Modular lattice}} For some applications the distributivity condition is too strong, and the following weaker property is often useful. A lattice (L, ∨, ∧) is modular if, for all elements a, b, c of L, the following identity holds. Modular identity: (ac) ∨ (bc) = [(ac) ∨ b] ∧ c. This condition is equivalent to the following axiom. Modular law: a ≤ c implies a ∨ (b ∧ c) = (a ∨ b) ∧ c. Besides distributive lattices, examples of modular lattices are the lattice of submodules of a module
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...

, and the lattice of normal subgroup
Normal subgroup
In abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....

s of a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

.

### Semimodularity

{{main|Semimodular lattice}} A finite lattice is modular if and only if it is both upper and lower semimodular
Semimodular lattice
In the branch of mathematics known as order theory, a semimodular lattice, is a lattice that satisfies the following condition:Semimodular law: a ∧ b  ...

In mathematics, in the branch of combinatorics, a graded poset, sometimes called a ranked poset , is a partially ordered set P equipped with a rank function ρ from P to N compatible with the ordering such that whenever y covers x, then...

lattice, (upper) semimodularity is equivalent to the following condition on the rank function r:$r\left(x\right)+r\left(y\right) \ge r\left(x \wedge y\right) + r\left(x \vee y\right).$ Another equivalent (for graded lattices) condition is Birkhoff's condition:NEWLINE
NEWLINE
for each x and y in L, if x and y both cover $x \wedge y$, then $x \vee y$ covers both x and y.
NEWLINE A lattice is called lower semimodular if its dual is semimodular. For finite lattices this means that the previous conditions hold with $\vee$ and $\wedge$ exchanged, "covers" exchanged with "is covered by", and inequalities reversed.

### Continuity and algebraicity

In domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...

, it is natural to seek to approximate the elements in a partial order by "much simpler" elements. This leads to the class of continuous posets, consisting of posets where any element can be obtained as the supremum of a directed set
Directed set
In mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤...

of elements that are way-below the element. If one can additionally restrict these to the compact element
Compact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....

s of a poset for obtaining these directed sets, then the poset is even algebraic. Both concepts can be applied to lattices as follows: NEWLINE
NEWLINE
• A continuous lattice is a complete lattice that is continuous as a poset.
• NEWLINE
• An algebraic lattice is a complete lattice that is algebraic as a poset.
NEWLINE Both of these classes have interesting properties. For example, continuous lattices can be characterized as algebraic structures (with infinitary operations) satisfying certain identities. While such a characterization is not known for algebraic lattices, they can be described "syntactically" via Scott information system
Scott information system
In domain theory, a branch of mathematics and computer science, a Scott information system is a primitive kind of logical deductive system often used as an alternative way of presenting Scott domains.-Definition:...

s.

### Complements and pseudo-complements

Let L be a bounded lattice with greatest element 1 and least element 0. Two elements x and y of L are complements of each other if and only if: NEWLINE
NEWLINE
$x \vee y = 1$ and $x \wedge y = 0.$
NEWLINE In the case the complement is unique, we write ¬x = y and equivalently, ¬y = x. A bounded lattice for which every element has a complement is called a complemented lattice
Complemented lattice
In the mathematical discipline of order theory, a complemented lattice is a bounded lattice in which every element a has a complement, i.e. an element b satisfying a ∨ b = 1 and a ∧ b = 0....

. The corresponding unary operation
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

over L, called complementation, introduces an analogue of logical negation
Negation
In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...

into lattice theory. The complement is not necessarily unique, nor does it have a special status among all possible unary operations over L. A complemented lattice that is also distributive is a Boolean algebra. For a distributive lattice, the complement of x, when it exists, is unique. Heyting algebra
Heyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...

s are an example of distributive lattices where some members might be lacking complements. Every element x of a Heyting algebra has, on the other hand, a pseudo-complement, also denoted ¬x. The pseudo-complement is the greatest element y such that x$\wedge$y = 0. If the pseudo-complement of every element of a Heyting algebra is in fact a complement, then the Heyting algebra is in fact a Boolean algebra.

## Sublattices

A sublattice of a lattice L is a nonempty subset of L which is a lattice with the same meet and join operations as L. That is, if L is a lattice and M$\not=\varnothing$ is a subset of L such that for every pair of elements a, b in M both a$\wedge$b and a$\vee$b are in M, then M is a sublattice of L. A sublattice M of a lattice L is a convex sublattice of L, if x ≤ z ≤ y and x, y in M implies that z belongs to M, for all elements x, y, z in L.

## Free lattices

{{main|Free lattice}} 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
Universal property
In various branches of mathematics, a useful construction is often viewed as the “most efficient solution” to a certain problem. The definition of a universal property uses the language of category theory to make this notion precise and to study it abstractly.This article gives a general treatment...

.

## Important lattice-theoretic notions

We now define some order-theoretic notions of importance to lattice theory. In the following, let x be an element of some lattice L. If L has a 0, x≠0 is sometimes required. x is:NEWLINE
NEWLINE
• Join irreducible iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...

x = ab implies x = a or x = b for any a,b in L. When the first condition is generalized to arbitrary joins $\lor a_i$, x is called completely join irreducible (or ∨-irreducible). The dual notion is meet irreducibility (∧-irreducible);
• NEWLINE
• Join prime iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...

x ≤ ab implies xa or xb. This too can be generalized to obtain the notion completely join prime. The dual notion is meet prime. Any join-prime element is also join irreducible, and any meet-prime element is also meet irreducible. The converse holds if L is distributive.
NEWLINE Let L have a 0. An element x of L is an atom if 0 < x and there exists no element y of L such that 0 < y < x. We then say that L is:NEWLINE
NEWLINE
• Atomic
Atomic (order theory)
In the mathematical field of order theory, given two elements a and b of a partially ordered set, one says that b covers a, and writes a  a, if a ...

if for every nonzero element x of L, there exists an atom a of L such that ax ;
• NEWLINE
• Atomistic
Atomic (order theory)
In the mathematical field of order theory, given two elements a and b of a partially ordered set, one says that b covers a, and writes a  a, if a ...

if every element of L is a supremum
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...

of atoms. That is, for all a, b in L such that $a\nleq b,$ there exists an atom x of L such that $x\leq a$ and $x\nleq b.$
NEWLINE The dual notions of ideal
Ideal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...

s and filters
Filter (mathematics)
In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...

refer to particular kinds of subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of any partially ordered set, and are therefore important for lattice theory. Details can be found in the respective entries.

NEWLINE
NEWLINE
• Map of lattices
Map of lattices
The concept of a lattice arises in order theory, a branch of mathematics. The Hasse diagram below depicts the inclusion relationships among some important subclasses of lattices.- Proofs of the relationships in the map :...

• NEWLINE
• Pointless topology
Pointless topology
In mathematics, pointless topology is an approach to topology that avoids mentioning points. The name 'pointless topology' is due to John von Neumann...

• NEWLINE
• Lattice of subgroups
Lattice of subgroups
In mathematics, the lattice of subgroups of a group G is the lattice whose elements are the subgroups of G, with the partial order relation being set inclusion....

• NEWLINE
• Ontology (computer science)
Ontology (computer science)
In computer science and information science, an ontology formally represents knowledge as a set of concepts within a domain, and the relationships between those concepts. It can be used to reason about the entities within that domain and may be used to describe the domain.In theory, an ontology is...

• NEWLINE
• Orthocomplemented lattice
NEWLINE