Poset Matematika Diskrit

Summary

This video lecture delves into the concept of partial order relations (poset) and their key properties: reflexivity, transitivity, and antisymmetry. It explains the essential traits of binary relations and how they form partial orderings, with real-life examples such as divisibility among integers. The lecture also covers the visualization of these relations using Hasse diagrams and discusses concepts like upper and lower bounds, maximum, and minimum elements within a poset. The lesson is aimed at helping students understand how these properties work together to create structured sets, providing a solid foundation for further exploration in set theory and mathematical relations.

Takeaways

• 😀 A binary relation on a set can have properties such as reflexive, symmetric, antisymmetric, and transitive.
• 😀 A relation is reflexive if every element of the set relates to itself, i.e., (a, a) is in the relation for all a in the set.
• 😀 A relation is transitive if whenever (a, b) and (b, c) are in the relation, then (a, c) must also be in the relation.
• 😀 A relation is symmetric if (a, b) in the relation implies (b, a) is also in the relation.
• 😀 A relation is antisymmetric if (a, b) and (b, a) being in the relation implies a = b.
• 😀 A partial order (poset) is a binary relation that is reflexive, antisymmetric, and transitive.
• 😀 The divisibility relation among positive integers is an example of a partial order.
• 😀 A Hasse diagram visually represents a poset by placing elements in levels with arrows pointing upwards to show the order.
• 😀 Upper bounds and lower bounds of a subset in a poset are elements that are greater than or equal to, or less than or equal to, every element of the subset respectively.
• 😀 The least upper bound (supremum) is the smallest of the upper bounds, and the greatest lower bound (infimum) is the largest of the lower bounds.

Q & A

What is a reflexive relation in a set?

A reflexive relation on a set is one where every element of the set is related to itself. For example, in a set A = {1, 2, 3, 4}, the relation R = {(1,1), (2,2), (3,3), (4,4)} is reflexive, as each element is related to itself.

Why is the relation R = {(1,1), (2,2), (2,3), (3,4)} not reflexive?

This relation is not reflexive because it lacks some necessary pairs. Specifically, the pair (3,3) is missing. A reflexive relation must contain a pair (a,a) for every element a in the set.

What does it mean for a relation to be transitive?

A relation is transitive if, for any elements a, b, and c in a set, whenever a is related to b and b is related to c, a must also be related to c. For example, if (a, b) and (b, c) are in the relation, (a, c) must also be included.

Why is the relation R = {(1,1), (2,3), (3,4), (4,2)} not transitive?

This relation is not transitive because there is no (2,4) pair, even though (2,3) and (3,4) are present. For transitivity to hold, the relation should include (2,4), as it follows from the other two pairs.

What is an antisymmetric relation?

A relation is antisymmetric if, for any two distinct elements a and b, if both (a,b) and (b,a) are in the relation, then a must be equal to b. In other words, no two different elements can be mutually related in both directions.

How can a relation be both symmetric and antisymmetric?

A relation can be both symmetric and antisymmetric only if it only contains pairs where a = b. This occurs because symmetry requires that if (a,b) is in the relation, then (b,a) must also be in the relation, and antisymmetry requires that a = b if both pairs exist.

What defines a partial order relation?

A partial order is a relation that is reflexive, antisymmetric, and transitive. It imposes a partial ordering on the elements of a set, meaning not every pair of elements need be comparable.

What is the Hasse diagram, and how is it used?

The Hasse diagram is a graphical representation of a partial order relation. It uses nodes to represent elements and edges to show the relationships between them, with the edges pointing upwards to indicate the ordering. The diagram helps visualize the structure of the partial order.

What does 'a divides b' mean in the context of partial order?

'a divides b' means that a is a divisor of b, or b is divisible by a without any remainder. This relation can be visualized as a partial order, where 'a divides b' is represented as a relation between a and b.

What are upper and lower bounds in a partially ordered set?

In a partially ordered set, an upper bound of a set of elements is an element that is greater than or equal to every element in the set. A lower bound is an element that is less than or equal to every element in the set. The greatest upper bound is the least element that is an upper bound, while the least lower bound is the greatest element that is a lower bound.