Glossary

5.1 Complete lattices and their properties

3 min read•august 7, 2024

Complete lattices are powerful structures in lattice theory. They ensure every subset has a least upper bound and greatest lower bound, providing a solid foundation for analyzing ordered sets and their properties.

Lattice homomorphisms and isomorphisms help us understand relationships between different lattices. We'll explore these concepts, along with suprema, infima, chains, and directed sets, to grasp the full scope of complete lattices.

Complete Lattices

Definition and Properties of Complete Lattices

Top images from around the web for Definition and Properties of Complete Lattices

  • Lattice (order) - Wikipedia View original

    Is this image relevant?

  • Category:Infimum and supremum - Wikimedia Commons View original

    Is this image relevant?

  • Lattice (order) - Wikipedia View original

    Is this image relevant?

1 of 3

Top images from around the web for Definition and Properties of Complete Lattices

  • Lattice (order) - Wikipedia View original

    Is this image relevant?

  • Category:Infimum and supremum - Wikimedia Commons View original

    Is this image relevant?

  • Lattice (order) - Wikipedia View original

    Is this image relevant?

1 of 3
  • has every subset containing a least upper bound () and greatest lower bound ()
  • Completeness property ensures the existence of suprema and infima for all subsets of the lattice
  • Completeness axiom states that a lattice LL is complete if every subset S⊆LS \subseteq L has a supremum and an infimum in LL
    • For example, the power set of a set ordered by inclusion (P(X),⊆)(P(X), \subseteq) forms a complete lattice
    • The set of real numbers R\mathbb{R} with the usual order ≤\leq is not a complete lattice, as the subset of positive real numbers has no greatest element

Lattice Homomorphisms

  • is a function f:L1→L2f: L_1 \rightarrow L_2 between two lattices that preserves the lattice operations ( and )
    • f(a∨b)=f(a)∨f(b)f(a \vee b) = f(a) \vee f(b) and f(a∧b)=f(a)∧f(b)f(a \wedge b) = f(a) \wedge f(b) for all a,b∈L1a, b \in L_1
  • Lattice homomorphisms preserve the order relation between elements
    • If a≤ba \leq b in L1L_1, then f(a)≤f(b)f(a) \leq f(b) in L2L_2
  • is a bijective lattice homomorphism, indicating that two lattices have the same structure
    • For instance, the lattice of divisors of 12 and the lattice of divisors of 18 are isomorphic

Bounds and Sets

Supremum and Infimum

  • Supremum (least upper bound) of a subset SS of a partially ordered set (P,≤)(P, \leq) is the least element in PP that is greater than or equal to all elements of SS
    • Denoted as sup⁡S\sup S or ⋁S\bigvee S
    • For example, in the lattice of real numbers with the usual order, sup⁡{1,2,3}=3\sup\{1, 2, 3\} = 3
  • Infimum (greatest lower bound) of a subset SS of a partially ordered set (P,≤)(P, \leq) is the greatest element in PP that is less than or equal to all elements of SS
    • Denoted as inf⁡S\inf S or ⋀S\bigwedge S
    • For example, in the lattice of real numbers with the usual order, inf⁡{1,2,3}=1\inf\{1, 2, 3\} = 1

Chains and Directed Sets

  • is a totally ordered subset of a partially ordered set
    • For any two elements a,ba, b in a chain, either a≤ba \leq b or b≤ab \leq a
    • An example of a chain in the lattice of subsets of {1,2,3}\{1, 2, 3\} is {∅,{1},{1,2}}\{\emptyset, \{1\}, \{1, 2\}\}
  • is a partially ordered set (D,≤)(D, \leq) in which any two elements have an upper bound in DD
    • For any a,b∈Da, b \in D, there exists c∈Dc \in D such that a≤ca \leq c and b≤cb \leq c
    • The set of natural numbers N\mathbb{N} with the usual order is a directed set, as for any a,b∈Na, b \in \mathbb{N}, max⁡{a,b}\max\{a, b\} is an upper bound

Key Terms to Review (19)

Antichain: An antichain is a subset of a partially ordered set where no two elements are comparable; that is, for any two elements in the antichain, neither is less than or greater than the other. This concept highlights how elements can coexist without direct relational hierarchy, which connects deeply with the structure of partially ordered sets, influences the properties of complete lattices, and plays a significant role in understanding dense and discrete lattices.
Birkhoff's Theorem: Birkhoff's Theorem states that every finite distributive lattice is isomorphic to the lattice of open sets of a topological space. This connects the concepts of lattices, order theory, and topology by showing how algebraic structures can represent geometric or spatial ideas. It highlights important properties of complete lattices and emphasizes interconnections within different areas of lattice theory.
Bounded complete lattice: A bounded complete lattice is a special type of lattice in which every subset has both a least upper bound (supremum) and a greatest lower bound (infimum), and it contains both a maximum and a minimum element. This means that not only do all subsets have bounds, but there are also specific elements within the lattice that serve as the upper and lower extremes. Bounded complete lattices are essential because they ensure that the limits and bounds of all possible collections of elements are well-defined, allowing for consistent mathematical reasoning and proof.
Chain: A chain is a subset of a partially ordered set where every two elements are comparable, meaning that for any two elements in the chain, either one is less than or equal to the other. This concept highlights the structure of partially ordered sets by illustrating how elements can be arranged in a linear fashion, connecting to other important features such as completeness, density, and comparability.
Complete distributive lattice: A complete distributive lattice is a special type of lattice where every subset has both a supremum (least upper bound) and an infimum (greatest lower bound), and the lattice satisfies the distributive property. This means that for any elements in the lattice, the join and meet operations distribute over each other. This structure not only ensures that all joins and meets are well-defined but also maintains important properties that facilitate various mathematical proofs and constructions.
Complete Lattice: A complete lattice is a partially ordered set in which every subset has both a least upper bound (join) and a greatest lower bound (meet). This means that not only can pairs of elements be compared, but any collection of elements can also be combined to find their bounds, providing a rich structure for mathematical analysis.
Directed set: A directed set is a non-empty set equipped with a binary relation that is reflexive and transitive, and for any two elements in the set, there exists a third element that is greater than or equal to both. This concept is crucial for understanding the structure of complete and continuous lattices, as it helps describe how elements can be approximated and how supremums can be computed within these systems.
Infimum: The infimum of a subset within a partially ordered set is defined as the greatest lower bound of that subset, meaning it is the largest element that is less than or equal to every element in the subset. This concept plays a vital role in understanding various properties of lattices, as it provides insights into how elements interact with one another through their lower bounds and supports the structure of meets and joins.
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.
Kuratowski's Lemma: Kuratowski's Lemma states that in a complete lattice, any set of subsets can be represented by a finite number of meet and join operations. This key principle illustrates how complete lattices allow the construction of other elements through the operations of infimum (greatest lower bound) and supremum (least upper bound). Understanding this lemma is crucial for grasping the structure and properties of complete lattices, as it emphasizes their ability to encapsulate various subsets within their framework.
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 Bounds: Lower bounds refer to the elements in a partially ordered set (poset) that are less than or equal to every element in a given subset. In the context of complete lattices, lower bounds play a significant role in defining the minimum elements and contribute to the understanding of completeness and structure within the lattice. These bounds are essential for establishing the properties of infima and can affect how we approach order relationships in mathematical structures.
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.
Power Set Lattice: A power set lattice is a specific type of lattice formed by the collection of all subsets of a given set, ordered by inclusion. This structure is crucial as it illustrates fundamental properties of lattices, such as the existence of top and bottom elements, complete lattices, complemented lattices, and how these concepts apply in various domains like logic and programming semantics.
Real Numbers Under Subset Inclusion: Real numbers under subset inclusion refers to the collection of all real numbers that can be organized in a way where each set of real numbers is considered a subset of another set. This framework allows for various operations and relations to be defined among these sets, particularly in the context of lattices, where the subset relation creates a structure that can exhibit properties like completeness and bounds. Understanding this concept is crucial for exploring how sets of real numbers interact and how they can form lattices with specific characteristics.
Supremum: The supremum, often called the least upper bound, of a subset within a partially ordered set is the smallest element that is greater than or equal to every element in that subset. It plays a critical role in understanding the structure and behavior of lattices, particularly when examining the relationships between different elements and their bounds.
Totally Ordered Set: A totally ordered set is a type of partially ordered set where every pair of elements is comparable, meaning for any two elements a and b, either a ≤ b or b ≤ a holds true. This concept connects to various structures, helping us understand how elements relate to one another in a complete way. It plays a crucial role in defining common lattices, understanding top and bottom elements, exploring the properties of complete lattices, and analyzing their applications in universal algebra.
Upper Bounds: In lattice theory, an upper bound for a subset of a partially ordered set is an element that is greater than or equal to every element in that subset. Upper bounds are critical in understanding the structure of lattices, especially when discussing completeness, since a set may have many upper bounds but only one least upper bound, known as the supremum.
© 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