Glossary

6.2 Distributive lattices and their characterizations

4 min read•august 7, 2024

Distributive lattices are special structures where and operations distribute over each other. They're key to understanding Boolean algebras and have unique properties that set them apart from other lattices.

Characterizing distributive lattices involves looking at their sublattices and element relationships. These characterizations help us identify distributive lattices and understand their structure, connecting them to other important concepts in lattice theory.

Distributive Lattices and Laws

Properties of Distributive Lattices

Top images from around the web for Properties of Distributive Lattices

  • Complemented lattice - Wikipedia View original

    Is this image relevant?

  • Free Boolean algebra - Wikipedia View original

    Is this image relevant?

  • Complemented lattice - Wikipedia View original

    Is this image relevant?

1 of 3

Top images from around the web for Properties of Distributive Lattices

  • Complemented lattice - Wikipedia View original

    Is this image relevant?

  • Free Boolean algebra - Wikipedia View original

    Is this image relevant?

  • Complemented lattice - Wikipedia View original

    Is this image relevant?

1 of 3
  • is a lattice in which the operations of join and meet distribute over each other
  • Distributive law states that for any elements aa, bb, and cc in a distributive lattice, a∧(b∨c)=(a∧b)∨(a∧c)a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c) and a∨(b∧c)=(a∨b)∧(a∨c)a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)
  • is a complemented distributive lattice with a least element 0 and a greatest element 1
    • In a Boolean algebra, every element has a unique
    • Examples of Boolean algebras include the power set of a set with union and intersection as join and meet, and the set of all propositions with logical disjunction and conjunction as join and meet
  • Hasse diagram is a graphical representation of a partially ordered set, such as a distributive lattice
    • In a Hasse diagram, elements are represented as vertices, and the order relation is indicated by edges, with the greater element always placed above the lesser element
    • Example: The Hasse diagram of the divisors of 12 ordered by divisibility is a distributive lattice

Characterizations of Distributive Lattices

  • A lattice is distributive if and only if it does not contain a sublattice isomorphic to the pentagon lattice N5N_5 or the diamond lattice M3M_3
    • The pentagon lattice N5N_5 is a non-distributive lattice with five elements
    • The diamond lattice M3M_3 is a non-distributive lattice with four elements
  • A lattice is distributive if and only if for any three elements aa, bb, and cc, if a∧b=a∧ca \wedge b = a \wedge c and a∨b=a∨ca \vee b = a \vee c, then b=cb = c
  • A finite lattice is distributive if and only if it is isomorphic to a sublattice of a finite Boolean algebra
    • This characterization is a consequence of

Representation and Structure

Birkhoff's Representation Theorem

  • Birkhoff's representation theorem states that every is isomorphic to the lattice of down-sets of a unique finite poset
    • A down-set of a poset PP is a subset DD of PP such that if x∈Dx \in D and y≤xy \leq x, then y∈Dy \in D
    • The lattice of down-sets of a poset PP is a distributive lattice under set inclusion
  • Birkhoff's representation theorem provides a way to represent finite distributive lattices using finite posets
    • Example: The lattice of divisors of 12 is isomorphic to the lattice of down-sets of the poset of prime factors of 12

Prime and Maximal Ideals

  • Prime ideal in a lattice LL is a proper ideal PP such that for any a,b∈La, b \in L, if a∧b∈Pa \wedge b \in P, then either a∈Pa \in P or b∈Pb \in P
    • In a distributive lattice, an ideal is prime if and only if its complement is a filter
  • Maximal ideal in a lattice LL is a proper ideal MM such that if II is an ideal containing MM, then either I=MI = M or I=LI = L
    • In a finite distributive lattice, an ideal is maximal if and only if it is of the form L∖{x}L \setminus \{x\} for some join-irreducible element xx
  • In a finite distributive lattice, every prime ideal is the intersection of maximal ideals
    • This property is a consequence of the fact that finite distributive lattices are isomorphic to the lattice of down-sets of a finite poset

Complemented Lattices

Complemented and Relatively Complemented Lattices

  • Complemented lattice is a bounded lattice in which every element has a complement
    • An element bb is a complement of aa if a∧b=0a \wedge b = 0 and a∨b=1a \vee b = 1, where 0 and 1 are the least and greatest elements of the lattice, respectively
    • Example: The power set of a set with union and intersection as join and meet is a complemented distributive lattice
  • Relatively complemented lattice is a lattice in which every interval [a,b][a, b] is a complemented lattice
    • An interval [a,b][a, b] in a lattice LL is the set {x∈L:a≤x≤b}\{x \in L : a \leq x \leq b\}
    • Every relatively complemented lattice is distributive, but not every distributive lattice is relatively complemented
    • Example: The lattice of subspaces of a vector space is a relatively complemented lattice

Properties of Complemented Distributive Lattices

  • In a complemented distributive lattice, every element has a unique complement
    • This property follows from the distributive law and the definition of a complement
  • A complemented distributive lattice is a Boolean algebra
    • Boolean algebras are the most well-known examples of complemented distributive lattices
  • states that every Boolean algebra is isomorphic to a field of sets
    • A field of sets is a collection of subsets of a set that is closed under union, intersection, and complement
    • Stone's representation theorem provides a concrete representation of abstract Boolean algebras

Key Terms to Review (20)

Absorption law: The absorption law in lattice theory states that for any elements a and b in a lattice, the equations a ∧ (a ∨ b) = a and a ∨ (a ∧ b) = a hold true. This law illustrates how combining elements through meet and join operations can simplify expressions, reinforcing the fundamental structure of lattices and their operations.
Associativity: Associativity is a fundamental property in mathematics that states when performing an operation on three or more elements, the way in which they are grouped does not affect the final result. This property is significant in various algebraic structures, including lattices, where it ensures that the combination of elements yields consistent outcomes regardless of how the operations are ordered.
Birkhoff's Representation Theorem: Birkhoff's Representation Theorem states that every finite distributive lattice can be represented as the lattice of upper sets of a partially ordered set. This theorem provides a crucial link between lattice theory and order theory, illustrating how the structure of distributive lattices can be understood through simpler set-theoretic concepts. It also emphasizes the significance of atoms and coatoms in building lattices and the relationships between modularity and distributivity.
Boolean algebra: Boolean algebra is a mathematical structure that captures the essence of logical operations and relationships through a set of binary values and operators. It forms the foundation for digital logic design, enabling the manipulation of logical variables using operations like conjunction (AND), disjunction (OR), and negation (NOT). Understanding Boolean algebra is crucial for analyzing least upper bounds and greatest lower bounds in lattice theory, as well as exploring modular and distributive properties.
Commutativity: Commutativity is a fundamental property of binary operations where the order of the operands does not affect the result. In the context of lattices, this property implies that for any two elements, their meet (greatest lower bound) or join (least upper bound) can be computed in any order, providing a crucial aspect of how elements interact within the structure.
Complement: In lattice theory, a complement of an element in a lattice is another element that, when combined with the original element using the join operation, yields the greatest element (often denoted as 1), and when combined using the meet operation, yields the least element (often denoted as 0). This concept is crucial for understanding structures like Boolean algebras and distributive lattices, where every element has a unique complement.
Distributive Lattice: A distributive lattice is a specific type of lattice where the operations of meet (greatest lower bound) and join (least upper bound) satisfy the distributive laws. This means that for any three elements a, b, and c in the lattice, the following holds: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) and a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c). Distributive lattices are closely connected to modular lattices and have unique properties that allow for certain algebraic simplifications.
Finite distributive lattice: A finite distributive lattice is a type of lattice that is both finite in size and satisfies the distributive property, meaning that for any elements a, b, and c in the lattice, the operations of meet (∧) and join (∨) distribute over each other. In this structure, if an element can be expressed in multiple ways, those expressions can be simplified without loss of meaning. This property leads to important connections with various characterizations and representations within lattice theory.
Free distributive lattice: A free distributive lattice is an algebraic structure that is generated by a set of elements without imposing additional relations, ensuring that the operations of meet and join satisfy the distributive laws. This type of lattice arises when considering all possible combinations of meet and join operations on its generators, capturing the essential properties of distributive lattices while remaining free from constraints. Free distributive lattices play a crucial role in understanding the foundational aspects of lattice theory, particularly in characterizing distributive properties.
Join: In lattice theory, a join is the least upper bound of a pair of elements in a partially ordered set, meaning it is the smallest element that is greater than or equal to both elements. This concept is vital in understanding the structure of lattices, where every pair of elements has both a join and a meet, which allows for the analysis of their relationships and combinations.
Latt(l): latt(l) refers to the concept of a lattice, which is a partially ordered set in which every two elements have a unique supremum (least upper bound) and an infimum (greatest lower bound). This foundational idea is crucial for understanding distributive lattices, as they have additional properties that allow for the simplification of certain operations, making them easier to analyze and characterize.
Lattice homomorphism: A lattice homomorphism is a function between two lattices that preserves the structure of the lattices, meaning it maintains the meet and join operations. This function ensures that for any elements in the first lattice, the image of their meet is the meet of their images, and the image of their join is the join of their images. This concept connects various important features in lattice theory, such as completeness, distributive properties, congruence relations, and the construction of free lattices.
Lattice isomorphism: Lattice isomorphism is a relationship between two lattices where there exists a bijective function that preserves the lattice operations of meet and join. This means that for any two elements in the lattices, the image of their meet and join in one lattice corresponds to the meet and join of their images in the other lattice. Understanding lattice isomorphisms is crucial for recognizing when two complete or distributive lattices are essentially the same in structure, despite potentially differing in representation.
Lower Bound: A lower bound in a partially ordered set is an element that is less than or equal to every element of a subset within that set. This concept is crucial as it helps to understand how elements relate to one another, particularly when looking at subsets and their properties within structures like lattices, where relationships are built on these comparisons.
Macneille Completion: Macneille completion is a method of constructing the smallest complete lattice from a given partially ordered set by adding all suprema of subsets that do not already have a supremum. This completion ensures that the resulting lattice is both complete and retains the original order structure of the partially ordered set. It is particularly relevant in understanding the structure of distributive lattices, as it preserves important properties such as join and meet operations.
Meet: In lattice theory, the term 'meet' refers to the greatest lower bound (GLB) of a set of elements within a partially ordered set. It identifies the largest element that is less than or equal to each element in the subset, essentially serving as the intersection of those elements in the context of a lattice structure.
Stone's representation theorem: Stone's representation theorem is a fundamental result in lattice theory that establishes a correspondence between Boolean algebras and certain types of topological spaces known as compact Hausdorff spaces. This theorem provides a powerful framework for understanding how Boolean algebras can be represented using points in these topological spaces, connecting algebraic structures with topological concepts.
Upper Bound: An upper bound for a set in a partially ordered set is an element that is greater than or equal to every element in that set. Understanding upper bounds is crucial because they help to define limits within structures, enabling comparisons and the establishment of bounds for operations like joins and meets.
X ∧ y: In lattice theory, the expression 'x ∧ y' represents the greatest lower bound (also known as the meet) of two elements x and y within a lattice. This term signifies the largest element that is less than or equal to both x and y, capturing an essential relationship between the elements in the structure. Understanding this concept is crucial for grasping the behavior of lattices, especially when analyzing least upper bounds and characterizing distributive properties.
X ∨ y: In lattice theory, x ∨ y represents the join of two elements x and y, which is the least upper bound of x and y. This means that x ∨ y is the smallest element in the lattice that is greater than or equal to both x and y, effectively capturing the concept of combining two elements to find their 'union' within a lattice structure. This operation is crucial in understanding how elements relate to one another and helps define the overall structure of lattices, particularly in terms of completeness and order.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Practice QuizGlossary
Practice QuizGlossary
Next guide