Lattice (order)

{{No footnotes|date=May 2009}} {{See also|Lattice (group)}} 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\; \backslash 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\; \backslash 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\; \backslash lor\; b$ and $a\; \backslash land\; b$, respectively. This definition makes $\backslash lor$ and $\backslash 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: a₁ ≤ a₂ and b₁ ≤ b₂ implies that a₁$\backslash lor$ b₁ ≤ a₂ $\backslash lor$ b₂ and a₁$\backslash land$b₁ ≤ a₂$\backslash land$b₂. 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 $\backslash bigvee\; A=a\_1\backslash lor\backslash cdots\backslash lor\; a\_n$ (resp.$\backslash bigwedge\; A=a\_1\backslash land\backslash cdots\backslash land\; a\_n$) where $A=\backslash \{a\_1,\backslash ldots,a\_n\backslash \}$. 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 $\backslash bigvee\backslash varnothing=0$, and the meet of the empty set is defined to be the greatest element $\backslash bigwedge\backslash 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, $\backslash bigvee\; \backslash left(\; A\; \backslash cup\; B\; \backslash right)=\; \backslash left(\; \backslash bigvee\; A\; \backslash right)\; \backslash vee\; \backslash left(\; \backslash bigvee\; B\; \backslash right)$ and $\backslash bigwedge\; \backslash left(\; A\; \backslash cup\; B\; \backslash right)=\; \backslash left(\backslash bigwedge\; A\; \backslash right)\; \backslash wedge\; \backslash left(\; \backslash bigwedge\; B\; \backslash right)$ hold. Taking B to be the empty set, $\backslash bigvee\; \backslash left(\; A\; \backslash cup\; \backslash emptyset\; \backslash 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, $\backslash lor,\; \backslash 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....

 $\backslash lor$, and $\backslash land$, on L is a lattice if the following axiomatic identities hold for all elements a, b, c of L. NEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINE

Commutative laws$a\; \backslash lor\; b\; =\; b\; \backslash lor\; a$,$a\; \backslash land\; b\; =\; b\backslash land\; a$.

Associative laws$a\; \backslash lor(b\; \backslash lor\; c)\; =\; (a\; \backslash lor\; b)\backslash lor\; c$,$a\; \backslash land(b\; \backslash land\; c)\; =\; (a\; \backslash land\; b)\backslash land\; c$.

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:... s:$a\; \backslash lor(a\; \backslash land\; b)\; =\; a$,$a\; \backslash land\; (a\; \backslash lor\; b)\; =\; 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\; \backslash lor\; a\; =\; a$,$a\; \backslash land\; a\; =\; a$. These axioms assert that both (L,$\backslash lor$) and (L,$\backslash 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, $\backslash lor,\; \backslash land$, 1, 0) such that (L, $\backslash lor,\; \backslash 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 $\backslash lor$, and 1 (the lattice's top) is the identity element for the meet operation $\backslash 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\; \backslash lor\; 0\; =\; a$,$a\; \backslash 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 $\backslash lor$ and $\backslash land$. Since the commutative, associative and absorption laws can easily be verified for these operations, they make (L, $\backslash lor$, $\backslash 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 = a∧b. The converse is also true. Given an algebraically defined lattice (L, $\backslash lor$, $\backslash land$), one can define a partial order ≤ on L by settingNEWLINE

NEWLINE

a ≤ b if and only if a = a$\backslash land$b, or

NEWLINE

a ≤ b if and only if b = a$\backslash 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 $\backslash lor$ and $\backslash 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) ↔ (a ≤ c) & (b ≤ d). (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: a ≤ b 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 x ≤ y 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 : L → M such that NEWLINE

NEWLINE

f(a∨_Lb) = f(a) ∨_M f(b), and

NEWLINE

f(a∧_Lb) = 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(0_L) = 0_M , and

NEWLINE

f(1_L) = 1_M .

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∨(b∧c) = (a∨b) ∧ (a∨c).

NEWLINE Distributivity of ∧ over ∨NEWLINE

NEWLINE

a∧(b∨c) = (a∧b) ∨ (a∧c).

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: (a ∧ c) ∨ (b ∧ c) = [(a ∧ c) ∨ 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  ...

. For a graded

Graded poset

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(x)+r(y)\; \backslash ge\; r(x\; \backslash wedge\; y)\; +\; r(x\; \backslash vee\; y).$ 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\; \backslash wedge\; y$, then $x\; \backslash 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 $\backslash vee$ and $\backslash 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\; \backslash vee\; y\; =\; 1$ and $x\; \backslash 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$\backslash 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$\backslash not=\backslash varnothing$ is a subset of L such that for every pair of elements a, b in M both a$\backslash wedge$b and a$\backslash 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 = a∨b implies x = a or x = b for any a,b in L. When the first condition is generalized to arbitrary joins $\backslash 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 ≤ a ∨ b implies x ≤ a or x ≤ b. 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 a ≤ x ;
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\backslash nleq\; b,$ there exists an atom x of L such that $x\backslash leq\; a$ and $x\backslash 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.

See also

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

External links

{{Commons|Lattice (order)}}NEWLINE

NEWLINE
• J.B. Nation, Notes on Lattice Theory, unpublished course notes available as two PDF files.
NEWLINE
• Ralph Freese, "Lattice Theory Homepage".

NEWLINE