Partial Ordering and Hasse Diagram

Partial Ordering: A relation 'R' on a set 'A' is said to be a partial ordering relation if 'R' is reflexive, antisymmetric & transitive.
Example:
A = {1, 2, 3}
R = {(1,1), (2,2), (3,3), (1,2)} is a partial ordering relation.
Partially Ordered Set: A set 'A' with a partial order 'R' defined on 'A' is called partially ordered set (Poset) and it is denoted by [A ; R].
Totally Ordered Set: A poset [A ;R] is called totally ordered set if every pair of elements in A are comparable, i.e, aRb or bRa ∀ a,b ∈ A.
Strict Order: A binary relation R on a set A is a strict order on A iff R is irreflexive and transitive.
Poset Diagram(Hasse diagram): Let [A;R] be a poset. The poset diagram is as follows
I. There is a vertex corresponding to each element of 'A'.
II. An edge between the elements 'a' and 'b' is not present in the diagram if there exists an element x∈ A such that aRx and xRb.
III. An edge between the elements 'a' and 'b' is present iff aRb and there is no element x∈A such that aRx and xRb.
Example: 
1.Set A ≡ {1,2,3,4}
Relation R ≡ 'is less than or equal to' ≡ ≤
Here set A on relation R is a partially ordered relation [A;R]. (Means it is reflexive, antisymmetric and transitive)
We can represent this

2. A= {1,2,3,6,9,18}  Relation R = "is devisor of "
Poset: [A, /]

Maximal element: If in a poset, an element in not related to any other element, then it is called maximal element.
Minimal element: If in a poset, if no element is related to an element, then it is called minimal element.
Example:
[{1,2,3,4,6};/]
We can draw Hass diagram as,

0Comment