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 bound or join) and a unique infimum (also called a greatest lower bound or meet). An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor. Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities. Since the two definitions are equivalent, lattice theory draws on both order theory and universal algebra. The class of lattices can be generalized to semilattices, and some notable subclasses of lattices are Heyting algebras, Boolean algebras, distributive lattices, and geometric lattices (matroids). These lattice-like structures all admit order-theoretic as well as algebraic descriptions. The sub-field that studies lattices is called lattice theory.
Definition A lattice can be defined either order-theoretically as a partially ordered set, or as an algebraic structure.
As partially ordered set A partially ordered set (poset) ( L , ≤ ) {\displaystyle (L,\leq )} is called a lattice if it is both a join- and a meet-semilattice, i.e. each two-element subset { a , b } ⊆ L {\displaystyle \{a,b\}\subseteq L} has a join (i.e. least upper bound, denoted by a ∨ b {\displaystyle a\vee b} ) and dually a meet (i.e. greatest lower bound, denoted by a ∧ b {\displaystyle a\wedge b} ). This definition makes ∧ {\displaystyle \,\wedge \,} and ∨ {\displaystyle \,\vee \,} binary operations. Both operations are monotone with respect to the given order: a 1 ≤ a 2 {\displaystyle a_{1}\leq a_{2}} and b 1 ≤ b 2 {\displaystyle b_{1}\leq b_{2}} implies that a 1 ∨ b 1 ≤ a 2 ∨ b 2 {\displaystyle a_{1}\vee b_{1}\leq a_{2}\vee b_{2}} and a 1 ∧ b 1 ≤ a 2 ∧ b 2 . {\displaystyle a_{1}\wedge b_{1}\leq a_{2}\wedge b_{2}.}
It follows by an induction argument that every non-empty finite subset of a lattice has a least upper bound and a greatest lower bound. With additional assumptions, further conclusions may be possible; see Completeness (order theory) 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 connections between related partially ordered sets—an approach of special interest for the category theoretic approach to lattices, and for formal concept analysis. Given a subset of a lattice, H ⊆ L , {\displaystyle H\subseteq L,} meet and join restrict to partial functions – they are undefined if their value is not in the subset H . {\displaystyle H.} The resulting structure on H {\displaystyle H} is called a partial lattice. In addition to this extrinsic definition as a subset of some other algebraic structure (a lattice), a partial lattice can also be intrinsically defined as a set with two partial binary operations satisfying certain axioms.
As algebraic structure A lattice is an algebraic structure ( L , ∨ , ∧ ) {\displaystyle (L,\vee ,\wedge )} , consisting of a set L {\displaystyle L} and two binary, commutative and associative operations ∨ {\displaystyle \vee } and ∧ {\displaystyle \wedge } on L {\displaystyle L} satisfying the following axiomatic identities (sometimes called absorption laws) for all elements a , b ∈ L {\displaystyle a,b\in L} :
a ∨ ( a ∧ b ) = a {\displaystyle a\vee (a\wedge b)=a}
a ∧ ( a ∨ b ) = a {\displaystyle a\wedge (a\vee b)=a}
The following two identities are also usually regarded as axioms, even though they follow from the two absorption laws taken together. These are called idempotent laws.
a ∨ a = a {\displaystyle a\vee a=a}
a ∧ a = a {\displaystyle a\wedge a=a}
… excerpt ends here. Continue reading the full article.
