Discrete Maths: POSETs, Lattices, and Boolean Algebra
Contents
Recall the Partial Order Set and Totally Ordered Set 1
Verify the given Set with a relation is a POSET or not 2
Recall the components of POSET 4
Draw the Hasse diagram and find its maximal, minimal, first, and last elements 5
Recall the Concept of Lattice in terms of POSET and Algebraic Structure 7
List and prove the properties of Lattice 9
Recall the Partial Order Set and Totally Ordered Set
Partial Order Set:
A partial order set, also known as a partially ordered set or poset, is a set equipped with a binary relation that satisfies certain properties. Formally, a partial order set is defined as a set P together with a binary relation ≤, which is reflexive, antisymmetric, and transitive.
Properties of a Partial Order Set:
- Reflexivity: Every element in the set is related to itself. For all a ∈ P, a ≤ a.
- Antisymmetry: If two elements are related to each other, they must be the same element. For all a, b ∈ P, if a ≤ b and b ≤ a, then a = b.
- Transitivity: If one element is related to another and the second element is related to a third element, then the first element is also related to the third element. For all a, b, c ∈ P, if a ≤ b and b ≤ c, then a ≤ c.
Totally Ordered Set:
A totally ordered set, also known as a linearly ordered set or a chain, is a partial order set in which every pair of elements is comparable. In other words, for any two elements in a totally ordered set, one element is either less than or equal to the other element, or vice versa.
In a totally ordered set, every element can be compared to every other element in a meaningful way. This allows for a total ordering or linear ordering of the elements, where every pair of elements can be arranged in a linear sequence.
Example:
Consider the set S = {1, 2, 3, 4} with the relation ≤ defined as the usual less-than-or-equal-to relation. This forms a partial order set because the relation satisfies reflexivity, antisymmetry, and transitivity. However, it is also a totally ordered set because every pair of elements can be compared to each other. For any two elements a and b in S, either a ≤ b or b ≤ a is true.
In this example, the partial order set S is also a totally ordered set because every pair of elements in S can be arranged in a linear sequence based on the less-than-or-equal-to relation.
Verify the given Set with a relation is a POSET or not
Example 1:
Set: A = {1, 2, 3}
Relation: R = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3)}
Reflexivity: (1, 1), (2, 2), and (3, 3) are present in R, satisfying reflexivity.
Antisymmetry: There are no pairs in R such that (a, b) and (b, a) both exist, satisfying antisymmetry.
Transitivity: (1, 2) and (2, 3) are present in R, and (1, 3) is also present, satisfying transitivity.
This set with the given relation is a POSET.
Example 2:
Set: A = {a, b, c, d}
Relation: R = {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (a, d)}
Reflexivity: (a, a), (b, b), (c, c), and (d, d) are present in R, satisfying reflexivity.
Antisymmetry: (a, b) and (b, a) are present in R, violating antisymmetry.
Transitivity: (a, b) and (b, c) are present in R, but (a, c) is not, violating transitivity.
This set with the given relation is not a POSET.
Example 3:
Set: A = {x, y, z, w}
Relation: R = {(x, x), (y, y), (z, z), (w, w), (x, y), (y, z), (x, z), (y, w), (x, w)}
Reflexivity: (x, x), (y, y), (z, z), and (w, w) are present in R, satisfying reflexivity.
Antisymmetry: (x, y) and (y, x) are present in R, violating antisymmetry.
Transitivity: (x, y) and (y, z) are present in R, but (x, z) is not, violating transitivity.
This set with the given relation is not a POSET.
Example 4:
Set: A = {apple, banana, cherry}
Relation: R = {(apple, apple), (banana, banana), (cherry, cherry), (apple, banana), (banana, cherry)}
Reflexivity: (apple, apple), (banana, banana), and (cherry, cherry) are present in R, satisfying reflexivity.
Antisymmetry: There are no pairs in R such that (a, b) and (b, a) both exist, satisfying antisymmetry.
Transitivity: (apple, banana) and (banana, cherry) are present in R, satisfying transitivity.
This set with the given relation is a POSET.
Example 5:
Set: A = {1, 2, 3, 4, 5}
Relation: R = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (2, 3), (3, 4), (4, 5)}
Reflexivity: (1, 1), (2, 2), (3, 3), (4, 4), and (5, 5) are present in R, satisfying reflexivity.
Antisymmetry: There are no pairs in R such that (a, b) and (b, a) both exist, satisfying antisymmetry.
Transitivity: (1, 2), (2, 3), (3, 4), and (4, 5) are present in R, satisfying transitivity.
This set with the given relation is a POSET.
Recall the components of POSET
The components of a partially ordered set (POSET) are as follows:
- Set: The POSET consists of a non-empty set of elements, denoted as A or S.
- Relation: The POSET has a relation, denoted as ≤ or ⪯, defined on the set A. This relation establishes the ordering or precedence between elements of the set.
- Reflexivity: Every element in the set is related to itself. In other words, for every element a in A, (a, a) ∈ R, where R is the relation.
- Antisymmetry: If (a, b) ∈ R and (b, a) ∈ R, then a = b. In other words, if two elements are related in both directions, they must be equal.
- Transitivity: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R. In other words, if two elements have a common ordering with a third element, they have an ordering with each other.
These components together define the properties and structure of a partially ordered set.
Example 1:
Consider the set A = {1, 2, 3, 4} with the relation ≤ defined as follows:
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (4, 4)}
This relation satisfies the components of a POSET:
- Reflexivity: Every element is related to itself.
- Antisymmetry: If (a, b) and (b, a) are in the relation, then a = b.
- Transitivity: If (a, b) and (b, c) are in the relation, then (a, c) is also in the relation.
Example 2:
Consider the set B = {a, b, c, d} with the relation ≤ defined as follows:
{(a, a), (a, b), (a, c), (a, d), (b, b), (b, c), (b, d), (c, c), (d, d)}
This relation satisfies the components of a POSET as well.
In both examples, the sets A and B, along with their respective relations, form partially ordered sets.
Recall Hasse Diagram
A Hasse diagram is a graphical representation of a partially ordered set (POSET) that visually depicts the ordering of elements. It provides a compact and intuitive way to understand the relationships between the elements in a POSET.
In a Hasse diagram, each element of the POSET is represented by a node or vertex. The nodes are arranged in such a way that if an element ‘a’ is less than or equal to another element ‘b’, then the node representing ‘a’ is placed below the node representing ‘b’. The ordering is indicated by drawing directed edges or lines between the nodes.
The Hasse diagram eliminates redundant edges, meaning it does not show edges for pairs of elements that are indirectly related through a common ancestor. This helps to simplify the representation and focus on the essential relationships in the POSET.
Hasse diagrams are particularly useful for visualizing finite POSETs, as they allow for a clear understanding of the partial order structure and can reveal important properties such as maximal and minimal elements, chains, antichains, and the overall shape of the POSET.
It’s worth noting that while a Hasse diagram provides a visual representation of a POSET, it does not capture all the information about the elements and the relation. However, it serves as a powerful tool for understanding the partial order and analyzing the properties of a POSET.
Draw the Hasse diagram and find its maximal, minimal, first, and last elements
To draw a Hasse diagram, the following rules can be followed:
- Start by listing all the elements of the partially ordered set (POSET).
- Determine the ordering relation between the elements. For each pair of elements, check if there is a strict order or partial order relation between them.
- Identify the minimal and maximal elements in the POSET. These are the elements that have no predecessors or successors, respectively.
- Arrange the elements vertically according to the ordering relation. Place the minimal elements at the bottom and the maximal elements at the top.
- Draw directed edges or lines between the elements to indicate the ordering relation. If element A is less than or equal to element B, draw an edge from A to B. Make sure not to draw redundant edges.
- Avoid crossing edges as much as possible to maintain clarity and readability of the diagram.
- If there are any chains (linearly ordered subsets) or antichains (subsets with no order relation), represent them as horizontally aligned elements.
- Add labels or names to the nodes to indicate the elements of the POSET, if necessary.
- Simplify the diagram by removing any unnecessary edges or nodes that do not affect the partial order structure.
By following these rules, you can create a clear and concise Hasse diagram that represents the partial order relation between the elements of a POSET.
Example 1:
Elements: A, B, C, D, E
Order Relation: A ≤ B, A ≤ C, B ≤ D, C ≤ D, D ≤ E
Hasse Diagram:
Maximal Element: E
Minimal Element: A
First Element: A
Last Element: E
Example 2:
Elements: X, Y, Z, W
Order Relation: X ≤ Y, Y ≤ Z, X ≤ W
Hasse Diagram:
Maximal Element: Z
Minimal Element: X
First Element: X
Last Element: Z
Recall the Concept of Lattice in terms of POSET and Algebraic Structure
In terms of POSET (Partially Ordered Set), a lattice is a special kind of partially ordered set where every pair of elements has a unique greatest lower bound (meet) and a unique least upper bound (join).
Formally, a lattice is defined as follows:
- A partially ordered set (POSET) in which every pair of elements has a greatest lower bound (infimum) and a least upper bound (supremum).
- The greatest lower bound (infimum) of a pair of elements is their meet denoted by a ∧ b.
- The least upper bound (supremum) of a pair of elements is their join denoted by a ∨ b.
In terms of Algebraic Structure, a lattice is a partially ordered set equipped with two binary operations, meet (⊓) and join (⊔), that satisfy certain properties. These properties are known as the lattice axioms and they ensure that the operations of meet and join are well-defined and have specific properties.
The lattice axioms are as follows:
- Associativity: (a ⊓ b) ⊓ c = a ⊓ (b ⊓ c) and (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c)
- Commutativity: a ⊓ b = b ⊓ a and a ⊔ b = b ⊔ a
- Idempotence: a ⊓ a = a and a ⊔ a = a
- Absorption: a ⊓ (a ⊔ b) = a and a ⊔ (a ⊓ b) = a
In a lattice, the meet operation represents the greatest lower bound and the join operation represents the least upper bound. The lattice structure allows for the analysis of relationships between elements and provides a framework for reasoning about order and structure.
Examples of lattices include the power set of a set ordered by set inclusion, the set of divisors of a positive integer ordered by divisibility, and the Boolean algebra of sets ordered by set containment.
Example 1: Power Set Lattice
Consider the set A = {1, 2}. The power set of A, denoted as P(A), is the set of all subsets of A. The partial order relation is set inclusion (⊆). The meet operation (⊓) is the intersection of sets, and the join operation (⊔) is the union of sets. The Hasse diagram of this lattice would have the empty set (∅) at the bottom, the singleton sets {1} and {2} above it, and the top element would be the set A = {1, 2}.
Example 2: Divisor Lattice
Consider the set of positive divisors of the number 12, denoted as D = {1, 2, 3, 4, 6, 12}. The partial order relation is divisibility (|). The meet operation (⊓) is the greatest common divisor (GCD) of two numbers, and the join operation (⊔) is the least common multiple (LCM) of two numbers. The Hasse diagram of this lattice would have 1 at the bottom, followed by 2 and 3, then 4 and 6, and finally 12 at the top.
Example 3: Boolean Algebra Lattice
Consider the set of all subsets of a universal set U. The partial order relation is set containment (⊆). The meet operation (⊓) is the intersection of sets, and the join operation (⊔) is the union of sets. The Hasse diagram of this lattice would have the empty set (∅) at the bottom, followed by the singleton sets, then the pairs of subsets, and so on, until the top element is the universal set U itself.
These examples demonstrate different types of lattices and how the meet and join operations work in each case to form a lattice structure.
List and prove the properties of Lattice
The properties of a lattice are as follows:
- Reflexivity: For every element a in the lattice, a ≤ a (a is less than or equal to itself).
Proof: This property holds because any element is always comparable to itself in a lattice.
- Antisymmetry: For any elements a and b in the lattice, if a ≤ b and b ≤ a, then a = b.
Proof: This property holds because in a lattice, if two elements are comparable in both directions, they must be equal.
- Transitivity: For any elements a, b, and c in the lattice, if a ≤ b and b ≤ c, then a ≤ c.
Proof: This property holds because the transitive property holds in the partial order relation of a lattice. If a is less than or equal to b, and b is less than or equal to c, then by transitivity, a must be less than or equal to c.
- Join and Meet Existence: For any elements a and b in the lattice, there exist elements c and d in the lattice such that c is the join (a ⊔ b) of a and b, and d is the meet (a ⊓ b) of a and b.
Proof: This property holds because in a lattice, for any two elements, their join and meet always exist. The join of two elements is the least upper bound (supremum) of the set containing those elements, and the meet is the greatest lower bound (infimum) of the set containing those elements.
- Join and Meet Associativity: For any elements a, b, and c in the lattice, (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c) and (a ⊓ b) ⊓ c = a ⊓ (b ⊓ c).
Proof: This property holds because the join and meet operations in a lattice are associative. The associativity property ensures that the result of joining or meeting multiple elements is independent of the grouping.
These properties collectively define the characteristics of a lattice and ensure that it forms a well-defined structure with a partial order relation, join and meet operations, and other fundamental properties.
Here are examples of lattices for each property:
- Reflexivity:
- In the lattice {0, 1, 2}, where ≤ represents the usual order relation, every element is less than or equal to itself. For example, 0 ≤ 0, 1 ≤ 1, and 2 ≤ 2.
- Antisymmetry:
- In the lattice {a, b, c, d} with the partial order relation defined as a ≤ b if a divides b, the elements are comparable in both directions. For example, 2 divides 6 (2 ≤ 6) and 6 divides 6 (6 ≤ 6), but no other elements are equal.
- Transitivity:
- In the lattice {1, 2, 3, 4, 6} with the usual order relation, if a ≤ b and b ≤ c, then a ≤ c. For example, 1 ≤ 2 and 2 ≤ 6 imply that 1 ≤ 6.
- Join and Meet Existence:
- In the lattice {0, 2, 4, 6, 8, 10} with the usual order relation, the join and meet operations exist for any pair of elements. The join of two elements is their maximum value, and the meet is their minimum value. For example, the join of 4 and 8 is 8 (4 ⊔ 8 = 8), and the meet of 4 and 8 is 4 (4 ⊓ 8 = 4).
- Join and Meet Associativity:
- In the lattice {a, b, c, d} with the partial order relation defined as a ≤ b if a divides b, the join and meet operations are associative. For example, (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c) and (a ⊓ b) ⊓ c = a ⊓ (b ⊓ c) for any elements a, b, and c.
These examples demonstrate the properties of lattices and how they are satisfied in different contexts.
Recall the term Duality
Duality refers to a concept in mathematics and logic that establishes a relationship between two mathematical structures or concepts by interchanging certain properties or operations. In the context of duality, the properties or operations of one structure can be transformed into the corresponding properties or operations of another structure.
In mathematics, duality often arises in different branches, such as algebra, geometry, and logic. It allows us to study and understand a problem from different perspectives, providing alternative insights and approaches.
Here are a few examples of duality in mathematics:
- Boolean Algebra: In Boolean algebra, duality refers to the interchanging of logical operations AND (∧) and OR (∨), as well as the operations of complementation (NOT). This means that any statement or equation in Boolean algebra remains valid if we replace AND with OR and vice versa, as well as replace TRUE with FALSE and vice versa.
- Linear Algebra: In linear algebra, duality relates vector spaces and their dual spaces. The dual space of a vector space consists of all linear functionals on that space. This duality establishes a correspondence between vectors and linear functionals, where operations on vectors can be translated into operations on linear functionals and vice versa.
- Graph Theory: In graph theory, duality refers to the relationship between a graph and its dual graph. The dual graph is obtained by interchanging the roles of vertices and edges. The properties and characteristics of the original graph can be analyzed and understood by examining its dual graph.
Duality allows mathematicians to leverage one set of ideas and techniques to gain insights into another related set of ideas. It helps in simplifying complex problems, establishing connections between seemingly different structures, and facilitating the transfer of knowledge and results between different areas of mathematics.
Recall and verify the following Lattices: i. Bounded Lattice ii. Complete lattice iii. Distributive Lattice
Let’s verify the following types of lattices:
i. Bounded Lattice:
A bounded lattice is a lattice that has both a maximum element (top) and a minimum element (bottom). To verify if a lattice is bounded, we need to check if it has a top and a bottom element, and if these elements satisfy the properties of a lattice. Let’s consider the following lattice:
In this lattice, the top element is “a” and the bottom element is “d”. We can see that all pairs of elements have a unique least upper bound (join) and greatest lower bound (meet). Therefore, this lattice is a bounded lattice.
ii. Complete Lattice:
A complete lattice is a lattice in which every subset has a supremum (join) and an infimum (meet). To verify if a lattice is complete, we need to check if every subset of the lattice has a join and a meet operation defined. Let’s consider the following lattice:
In this lattice, let’s consider the subset {d, e, f}. The supremum (join) of this subset is “a” since “a” is the least upper bound of {d, e, f}. The infimum (meet) of this subset is “b” since “b” is the greatest lower bound of {d, e, f}. Similarly, for any other subset of this lattice, we can find the supremum and infimum. Therefore, this lattice is a complete lattice.
iii. Distributive Lattice:
A distributive lattice is a lattice in which the distributive property holds, meaning that for any elements a, b, and c in the lattice, the following property holds: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c). To verify if a lattice is distributive, we need to check if this property holds for all elements in the lattice. Let’s consider the following lattice:
In this lattice, let’s consider the elements a, b, and c. We have (a ∧ b) ∨ (a ∧ c) = b ∨ c = a. Also, we have a ∧ (b ∨ c) = a ∧ a = a. Therefore, the distributive property holds for this lattice, and it is a distributive lattice.
By verifying the properties of a lattice, we can determine if a given lattice is a bounded lattice, a complete lattice, or a distributive lattice.
Recall and verify the following Lattices: iv. Modular Lattice v. Complemented Lattice vi. Isomorphic Lattice vii. Sub-Lattice
iv. Modular Lattice: A modular lattice is a lattice in which the modular law holds. The modular law states that for any three elements a, b, and c in the lattice, if a ≤ c, then (a ∨ b) ∧ c = a ∨ (b ∧ c). To verify if a lattice is modular, you need to check if the modular law holds for all possible combinations of elements in the lattice.
v. Complemented Lattice: A complemented lattice is a lattice in which every element has a unique complement. For every element a in the lattice, there exists another element b such that a ∨ b = 1 (the top element) and a ∧ b = 0 (the bottom element). To verify if a lattice is complemented, you need to ensure that every element has a unique complement.
vi. Isomorphic Lattice: Two lattices are said to be isomorphic if there exists a one-to-one correspondence between their elements that preserves the order and lattice structure. In other words, if you can map the elements of one lattice to the elements of another lattice in such a way that the order of elements and the join/meet operations are preserved, then the two lattices are isomorphic.
vii. Sub-Lattice: A sub-lattice is a subset of a lattice that is itself a lattice. To verify if a subset of a lattice is a sub-lattice, you need to ensure that it contains the top element, the bottom element, and that it is closed under the join and meet operations.
- Example of a Modular Lattice:
Consider the lattice L = {0, 2, 4, 6, 8, 10} with the usual order relation (≤) and the join operation (∨) as the maximum of two elements and the meet operation (∧) as the minimum of two elements. This lattice satisfies the modular law for all combinations of elements, making it a modular lattice.
- Example of a Complemented Lattice:
Consider the lattice L = {0, 1, 2, 3, 4, 5} with the usual order relation (≤) and the join operation (∨) as the maximum of two elements and the meet operation (∧) as the minimum of two elements. In this lattice, every element except 0 and 5 has a unique complement. For example, the complement of 2 is 3, and the complement of 3 is 2.
- Example of Isomorphic Lattices:
Consider two lattices L1 = {0, 1, 2, 3} and L2 = {a, b, c, d}, both with the usual order relation (≤) and the join operation (∨) as the maximum of two elements and the meet operation (∧) as the minimum of two elements. If we define the following mappings:
f(0) = a, f(1) = b, f(2) = c, f(3) = d,
then these lattices are isomorphic because the order relation and lattice structure are preserved under this mapping.
- Example of a Sub-Lattice:
Consider the lattice L = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} with the usual order relation (≤) and the join operation (∨) as the maximum of two elements and the meet operation (∧) as the minimum of two elements. If we consider the subset S = {0, 2, 4, 6, 8, 10}, we can see that it contains the top element (10), the bottom element (0), and it is closed under the join and meet operations. Therefore, S is a sub-lattice of L.