Lattice

1 Lattice Fundamentals

A lattice is a partially ordered algebraic structure in which any two elements have a well-defined greatest lower bound and least upper bound. Formally, one begins with a partially ordered set (poset) \((L,\le)\) and equips it with two binary operations, meet \(\wedge\) and join \(\vee\), that capture how elements combine relative to \(\le\). In many presentations, the order is recoverable from the operations, while in others the order is primary and the operations are defined by universal properties.

Lattices are useful because they translate geometric and logical intuitions into algebraic laws. For example, intersection and generated span behave like meet and join in familiar settings such as sets ordered by inclusion or subspaces ordered by containment.

1.1 Partially Ordered Sets (Posets)

A poset is a set \(P\) together with a relation \(\le\) that is reflexive \((x\le x)\), antisymmetric \((x\le y\ \&\ y\le x \Rightarrow x=y)\), and transitive \((x\le y\ \&\ y\le z \Rightarrow x\le z)\). Posets provide the background order in which lattice operations are interpreted.

Given a poset, one can speak about chains, upper and lower bounds, and extremal elements such as minima and maxima. These notions become central when defining meet and join: the meet is determined by lower bounds, and the join by upper bounds.

1.2 Lattice Operations: Meet and Join

For elements \(a,b\in L\), their meet \(a\wedge b\) is the greatest element (with respect to \(\le\)) that is still a lower bound of both \(a\) and \(b\). Dually, their join \(a\vee b\) is the least element that is an upper bound of both.

When the operations exist for all pairs, the structure is a lattice. If meet and join are given as operations first, they are required to be consistent with an underlying order; conversely, if an order is given, meet and join can be defined as the GLB and LUB whenever they exist.

1.3 Order-Theoretic Characterizations

Lattice structure can be expressed purely in order-theoretic terms. The key is that meet and join can be characterized as universal bounds among all candidates.

1.3.1 Greatest Lower Bound (GLB)

An element \(m\) is the greatest lower bound of \(a\) and \(b\) if:

• \(m\le a\) and \(m\le b\), and
• for any \(x\) with \(x\le a\) and \(x\le b\), one has \(x\le m\).

This makes \(m\) maximal among common lower bounds. In typical examples, this corresponds to intersection (for sets) or intersection of subspaces (for vector subspaces).

1.3.2 Least Upper Bound (LUB)

An element \(j\) is the least upper bound of \(a\) and \(b\) if:

• \(a\le j\) and \(b\le j\), and
• for any \(y\) with \(a\le y\) and \(b\le y\), one has \(j\le y\).

Thus \(j\) is minimal among all common upper bounds. In common models, this corresponds to generated span (for subspaces) or union (for sets).

1.4 Lattice Axioms and Basic Consequences

A lattice can be described abstractly by axioms governing \(\wedge\) and \(\vee\). The operations satisfy commutativity \((a\wedge b=b\wedge a,\ a\vee b=b\vee a)\), associativity \((a\wedge(b\wedge c)=(a\wedge b)\wedge c\) and similarly for \(\vee\)), and absorption laws: \[ a\wedge(a\vee b)=a,\qquad a\vee(a\wedge b)=a. \] From these, many useful identities follow. For instance, one can define an order by \(a\le b\) iff \(a\wedge b=a\) (equivalently, \(a\vee b=b\)), showing that lattices intertwine order and algebra. Monotonicity also holds: increasing an argument cannot decrease a meet or increase a join.

2 Types of Lattices

Lattice theory refines the basic definition by adding properties that constrain how joins and meets interact. These refinements are often motivated by geometry (subspaces), algebra (ideals or modules), or logical semantics.

2.1 Bounded Lattices

A lattice is bounded if it has a least element \(0\) and a greatest element \(1\). Every element \(a\) then satisfies \(0\le a\le 1\). In operation terms, \(a\wedge 0=0\) and \(a\vee 1=1\). Bounds simplify many statements and allow constants to appear in identities.

Bounded lattices occur frequently because many natural examples—like power sets ordered by inclusion—have obvious minimum and maximum.

2.2 Bounded Distributive Lattices

A bounded distributive lattice satisfies distributive laws: \[ a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c), \] \[ a\vee(b\wedge c)=(a\vee b)\wedge(a\vee c). \] Distributivity is strong: it implies a high degree of structural regularity and often forces the lattice to resemble algebra of sets or logic.

Distributive lattices are central because many systems of constraints can be modeled by such an algebra, and because distributivity supports effective reasoning by transformation.

2.3 Modular Lattices

Modularity is weaker than distributivity and is expressed by the modular identity: \[ a\le c \Rightarrow a\vee(b\wedge c)=(a\vee b)\wedge c. \] Intuitively, modularity controls how meet and join behave when one element lies below another. This condition appears naturally in algebraic settings such as lattices of subspaces.

Modular lattices are often tractable and sit between distributive and general lattices in terms of complexity.

2.4 Semimodular and Other Variants

Beyond distributive and modular lattices, one encounters semimodularity and additional variants tailored to particular applications. Semimodularity, for example, limits how “rank-like” behavior changes along covering relations in finite lattices. There are also conditions defined via graded structure, Jordan–Dedekind properties, or exchange principles.

These variants are typically studied to understand fine-grained combinatorial structure, including how elements build up from atoms and how maximal chains behave.

2.5 Atomistic and Coatomistic Lattices

Atomistic lattices are those in which every element can be expressed as a join of atoms (minimal nonzero elements). Dually, coatomistic lattices are those in which every element can be expressed as a meet of coatoms (maximal proper elements).

These concepts are particularly helpful in finite settings, where atoms and coatoms correspond to minimal generators and maximal constraints.

2.5.1 Atoms in Lattices

An atom is an element \(a\) such that \(a>0\) and there is no element strictly between \(0\) and \(a\). In a bounded lattice, atoms serve as the “building blocks” for join expressions.

In many algebraic examples, atoms correspond to irreducible or minimal substructures, such as one-dimensional subspaces in a vector space.

2.5.2 Coatoms in Lattices

A coatom is an element \(c\) such that \(c<1\) and there is no element strictly between \(c\) and \(1\). In a bounded lattice, coatoms play the dual role: they are minimal obstructions to reaching the top element.

For instance, in lattices of subspaces, coatoms correspond to hyperplanes (subspaces of codimension one), capturing maximal proper containment.

3 Distributivity and Related Properties

Interaction rules between meet and join determine most of the qualitative behavior of a lattice. Distributivity is the most familiar condition, but modularity, complements, and Boolean structure also provide major classifications.

3.1 Distributive Lattices

Distributive lattices satisfy the distributive laws for all elements. This property allows many calculations to be simplified systematically, much as one distributes products over sums in classical algebra.

A key feature is that distributive lattices align with set-like intuition: they can often be represented using families of sets ordered by inclusion, where meet and join correspond to intersection and union.

3.2 Modular vs. Distributive

Modular lattices obey a restricted distributivity law, applicable only under an inequality premise. As a result, modular lattices can be more flexible than distributive ones, yet still retain enough structure for strong theorems.

A frequent theme is that distributivity implies modularity in many common contexts, but the converse generally fails. Thus the modular/distributive distinction helps classify lattices by how “set-like” they are.

3.3 Complemented Lattices

A lattice is complemented if every element \(a\) has a complement \(b\) such that: \[ a\wedge b=0,\qquad a\vee b=1. \] Complements need not be unique in general. Complementation provides an algebraic framework for “negation-like” behavior, linking lattice theory to logic and boolean-like calculi.

Complemented lattices remain broad: some have complements but do not satisfy full boolean laws.

3.4 Boolean Algebras as Special Lattices

A boolean algebra is a complemented distributive lattice. In such a structure, complements are unique and interact with joins and meets in a way that matches classical logic operations.

Boolean algebras provide a bridge between order theory and semantics: elements can be interpreted as propositions, with meet representing conjunction and join representing disjunction.

3.4.1 Complements and Boolean Laws

Within a boolean algebra, complement axioms imply familiar identities such as:

• \(a\vee \neg a=1\) and \(a\wedge \neg a=0\),
• double negation \(\neg(\neg a)=a\),
• De Morgan laws, where complements distribute over joins and meets:

\[ \neg(a\vee b)=\neg a\wedge \neg b,\qquad \neg(a\wedge b)=\neg a\vee \neg b. \] These laws are algebraic reflections of logical rules.

4 Morphisms and Constructions

Lattice theory studies not only individual structures but also how they relate. Morphisms preserve lattice operations, and constructions build new lattices from old ones, enabling classification and example generation.

4.1 Lattice Homomorphisms

A lattice homomorphism between lattices \((L,\wedge,\vee)\) and \((M,\wedge,\vee)\) is a function \(f:L\to M\) satisfying: \[ f(a\wedge b)=f(a)\wedge f(b),\qquad f(a\vee b)=f(a)\vee f(b). \] Homomorphisms preserve the algebraic structure of meet and join, and they automatically respect the induced order. Many properties transfer along homomorphisms, such as distributivity or modularity for suitable images.

4.2 Isomorphisms and Congruences

An isomorphism is a bijective homomorphism whose inverse is also a homomorphism. Isomorphic lattices are structurally the same, differing only by renaming elements.

Congruences formalize “equivalence up to structure”: they are equivalence relations compatible with \(\wedge\) and \(\vee\). Quotients by congruences often yield new lattices that reflect collapsed symmetries of the original.

4.3 Sublattices and Quotients

A sublattice is a subset of a lattice that is closed under meet and join. In many settings, sublattices correspond to restricted families of elements (for example, certain subspaces or certain collections of divisors).

Quotients identify elements according to a congruence and create a smaller lattice where the chosen distinctions are removed. Quotients are central in understanding how local properties combine into global ones.

4.3.1 Congruence Lattices

Given a lattice \(L\), its congruence lattice collects all congruence relations of \(L\), ordered by refinement. This construction turns relational structure into an actual lattice, allowing deeper study of how the original lattice can be decomposed or simplified.

4.4 Direct Products of Lattices

The direct product of lattices \(L_1\times L_2\) uses componentwise operations: \[ (a_1,a_2)\wedge(b_1,b_2)=(a_1\wedge b_1,\ a_2\wedge b_2), \] and similarly for \(\vee\). Direct products provide a systematic way to combine independent lattice behaviors.

Many properties are preserved under products, making them useful both for constructions and for counterexamples.

4.5 Free Lattices (Conceptual Overview)

A free lattice generated by a set \(X\) is, informally, the “most general” lattice built from generators \(X\) subject only to lattice axioms. It is characterized by a universal property: any function from \(X\) into a lattice extends uniquely to a homomorphism from the free lattice.

Free lattices are difficult to describe explicitly but are conceptually important because they separate what is forced by axioms from what depends on additional structure.

5 Representation and Examples

Lattices appear as concrete models in several mathematical areas. Representations and canonical examples help translate abstract axioms into computable structure.

5.1 Subspace Lattices of Vector Spaces

For a vector space \(V\), consider the set of all linear subspaces ordered by inclusion. The meet of two subspaces is their intersection, while the join is their sum (the smallest subspace containing both). This forms a lattice, and in many cases it is modular.

The subspace lattice illustrates modularity vividly: when one subspace is contained in another, the join and meet interact in a controlled way aligned with the modular identity.

5.2 Divisor Lattices in Number Theory

For a positive integer \(n\), one can form a lattice whose elements are the positive divisors of \(n\). Ordering by divisibility (\(a\le b\) when \(a\) divides \(b\)), the meet corresponds to the greatest common divisor, and the join corresponds to the least common multiple. This yields a bounded lattice with structure governed by prime factorizations.

Such lattices are typically distributive because divisor gcd/lcm operations satisfy set-like algebraic laws.

5.3 Power Set Lattices and Set Operations

The power set \(\mathcal{P}(S)\), ordered by inclusion, is the prototypical distributive bounded lattice. Meet is set intersection and join is set union. The existence of \(\varnothing\) and \(S\) provides bottom and top elements.

This example is valuable because it connects lattice terminology directly to familiar set operations and logical interpretation (and/or).

5.4 Intervals in Ordered Sets

In a poset or lattice, an interval between elements \(a\le b\) is the subset \([a,b]=\{x: a\le x\le b\}\). When the ambient structure is a lattice, many intervals inherit lattice operations and form sublattices. Interval structure is also used to examine local complexity: the behavior inside an interval can differ from that of the whole.

Intervals are a practical tool for finding manageable substructures and for studying properties by restriction.

5.5 Lattices in Combinatorics

Combinatorics often produces lattices from partial orderings on combinatorial objects, such as permutations, partitions, or graph-related data. Typical operations correspond to combining objects in a way that yields a least upper bound and greatest lower bound under the chosen ordering.

Lattice-theoretic methods then support counting arguments, structure theorems, and the study of ranked posets, where chain lengths and rank functions mirror combinatorial statistics.

6 Advanced Topics (Algebraic View)

More advanced treatments emphasize categorical, algebraic, and order-theoretic abstractions. These perspectives help unify constructions and explain why lattice properties appear across disciplines.

6.1 Lattice Theory in Algebra

In algebra, lattices frequently arise from substructures such as ideals, submodules, congruence relations, or varieties. For instance, the lattice of submodules of a module is ordered by inclusion, and joins and meets correspond to sums and intersections of submodules.

Many ring and module properties translate into lattice properties (e.g., modularity or distributivity under additional conditions), so lattice theory becomes a diagnostic tool for algebraic behavior.

6.2 Galois Connections and Their Lattice Forms

A Galois connection is a pair of order-reversing maps between posets that satisfy an adjunction-like relationship. Such connections frequently produce lattices or lattice-structured images, where closure operators arise naturally.

In practical terms, one can use a Galois connection to generate a lattice from an underlying relationship between two ordered worlds—for example, between sets of attributes and sets of objects possessing those attributes.

6.3 Duality in Lattices

Duality states that many lattice notions remain valid when the order is reversed. Under order reversal, meet and join swap roles: what is a greatest lower bound becomes a least upper bound in the dual order.

This duality principle means that results proved for one operation often have immediate mirrored versions, simplifying theory development.

6.3.1 Order Duals and Operation Swaps

The dual of a lattice \(L\) has the same underlying set but the opposite order. In the dual, meet corresponds to join from the original lattice and vice versa. Consequently, properties defined via identities involving \(\wedge\) and \(\vee\) often transform in predictable ways.

For example, distributive and modular properties are preserved under duality, while the specific form of certain definitions must be swapped.

7 Basic Proof Techniques

Lattice theory involves both verification of axioms for examples and reasoning about properties like distributivity or modularity. Several standard proof strategies recur across many problems.

7.1 Checking Lattice Axioms

To show a poset is a lattice, one must verify that GLBs and LUBs exist for all pairs. In an operation-based approach, one checks that the proposed meet and join satisfy commutativity, associativity, and absorption laws.

In concrete examples, bounds are often computed directly using familiar operations (intersection/union, gcd/lcm, sums/intersections of subspaces), making axiom checks systematic.

7.2 Proving Distributivity/Modularity

Distributivity proofs typically expand expressions using lattice laws until both sides match, or they use known representation theorems that reduce distributivity to set-like behavior. In modular lattices, proofs rely on verifying the modular identity under the condition \(a\le c\).

A common method is to select generators or use element inequalities to reduce the required identity to simpler cases, especially in finite lattices.

7.3 Constructing Counterexamples

To show a lattice is not distributive or not modular, one produces specific elements \(a,b,c\) that violate the defining identity. Counterexamples are often found by examining small lattices, using diagrammatic reasoning, or searching systematically in finite cases.

Because lattice properties are universal statements over all elements, a single violating triple or configuration is enough to disprove them.

7.4 Minimal and Maximal Elements in Practice

Many proofs in lattice theory depend on extremal elements such as bottom and top, or on atoms and coatoms. Identifying minimal elements helps determine whether joins generate the whole lattice, while maximal elements help analyze complements and meets.

In practice, one often combines extremal reasoning with inequality chains: by proving that an element must be less than or equal to certain bounds, one pins down its exact position in the order.