Lattice (order)

In mathematics, specifically order theory, a lattice is an abstract structure that formalizes the intuitive notion of a collection of objects where, for any two objects, there is a unique least upper bound (also called the supremum or join) and a unique greatest lower bound (also called the infimum or meet).

Formally, a lattice is a partially ordered set (poset) in which, for any two elements a and b, the set {a, b} has both a least upper bound (denoted a ∨ b) and a greatest lower bound (denoted a ∧ b). The join (a ∨ b) is also referred to as the supremum or least upper bound, while the meet (a ∧ b) is also referred to as the infimum or greatest lower bound.

A lattice can also be defined as an algebraic structure (L, ∨, ∧) satisfying certain axioms. This algebraic definition is equivalent to the order-theoretic definition. The algebraic definition requires that the operations ∨ (join) and ∧ (meet) satisfy the following axioms for all elements a, b, and c in L:

• Idempotency:

  • a ∨ a = a
  • a ∧ a = a

• Commutativity:

  • a ∨ b = b ∨ a
  • a ∧ b = b ∧ a

• Associativity:

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

• Absorption:

  • a ∨ ( a ∧ b ) = a
  • a ∧ ( a ∨ b ) = a

These two definitions, the order-theoretic and the algebraic, are inter-convertible. Starting with a partially ordered set, one can define the meet and join operations based on the order relation, and then show that the resulting algebraic structure satisfies the lattice axioms. Conversely, starting with an algebraic structure satisfying the lattice axioms, one can define a partial order relation based on the meet and join operations, and then show that the resulting partially ordered set is a lattice.

Important special types of lattices include complete lattices, distributive lattices, modular lattices, and Boolean lattices. A complete lattice is a partially ordered set in which every subset has both a least upper bound and a greatest lower bound. A distributive lattice is a lattice in which the distributive law holds: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) and a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c). A modular lattice is a lattice that satisfies the modular law: a ≤ b implies a ∨ (c ∧ b) = (a ∨ c) ∧ b. A Boolean lattice is a distributive and complemented lattice.

Lattices have numerous applications in various areas of mathematics and computer science, including set theory, logic, algebra, and formal concept analysis.