Partially Ordered Set and Hasse Diagram

Relation and Poset

In this section we define relation and special type of relation called reflexive, symmetric, anti-symmetric and transitive relation
and we discuss examples on these relations. Further, we define partial ordering relation and posets and discuss some examples
of posets.

Let A and B the non-empty sets. A relation R from A to B is a subset of A ´ B. Relation from A to A is called relation on A.
If (a, b) Î R then we write aRb and say that "a is in relation R to b". Also, if a is not in relation R to b, we write ab.



Example:

Let A = B = Z⁺, the set of all positive integers. The relation R is defined on Z⁺ in the following way aRb if and only if a divides b.
So, 6 R 18, but 38
A relation R on a set A is reflexive if (a, a) for every aÎ A, that is, if aRa for all aÎ A.

Example:

Let A= {1,2,3} and let R = {(1,1), (2,2), (3,3), (1,2) (1,3)}
Then R is reflexive, while R' = {(1,1), (2,2), (2,1), (1,2)} is not a reflexive, for (3,3) Ï R', i.e., 33.

A relation R, on a set A, is anti-symmetric if whenever aRb and bRa, then a = b. That is, R is anti-symmetric whenever
a ¹ b we must have either ab or ba.



Example 1:

Let X be a set and let A Í X and B Í X. Then from the Section 1.1, it is clear that A = B. Therefore, "Í " is anti-symmetric
on the set of subsets of X.

Example 2:

Let A=Z⁺, the set of all positive integer. Define R on A by aRb if and only if a ½ b that is "a divides b".
Then, if a R b and b R a, i.e., a½b and b½a, then there exist integers c, d Î Z⁺ such that b = ca and a = db.
Therefore, b = cbd.
So, 1 = cd. Therefore c = d = 1.
Hence a = b.
Therefore, R is anti-symmetric on Z⁺

Example 3:

Let A = Z, the set of integers and let R = {(a, b) Î A ´ A / a <> i.e., R is usual "less than".
If a ¹ b, then either a < face="Symbol">¹ b then either b a or ab.
Hence,if a ¹ b then either a b or ba is true.
Therefore, "<", usual "less than", is anti-symmetric.

[Note that in the anti-symmetric relation symmetryness will happen only with equal elements and symmetryness will never
happen between the unequal elements].

We say that a relation R on a set A is transitive if aRb and bRc then aRc.

Example:

Let A={1,2,3,4} and let R={(1,2), (2,1), (1,1), (2,2), (2,3), (2,3)}. Then R is transitive.
Let R={(1,2) (1,3), (4,2)}. Then R is also transitive, because we cannot find elements a, b, and c in A such that aRb and bRc,
but a c. So, we conclude that R is transitive.

A relation R on a set A is called a partial order relation or partial ordering if R is reflexive, anti-symmetric and
transitive.

A non-empty set A together with a partial order relation R, (A, R), is called partially ordered set or poset.

Partial order relations are "hierarchical relations", usually we write £ instead of R for partial ordering.
Thus, (A, £ ) denote a partially ordered set or poset.

Example 1:

Let A be a non empty set. Consider the power set P(A), the set of subsets of A, together with the relation set inclusion, "Í ".
Then (P(A), Í ) is a poset.

For, S Í S, for all S Í P(A).
Therefore, Í is reflexive.
If S Í T and T Í S, for S, T Í P(A),
then S = T (since S = T if and only if S Í T and T Í S).
Therefore, Í is anti-symmetric.
Also, if S Í T and T Í U, then by definition of Í , it is clear that S Í U.
Therefore, Í is transitive.
Hence, (P(A), Í ) is a partially ordered set.

Example 2:

Let A = Z⁺ and let a £ b if and only if a½b then (A, £ ) is a poset.
For, since a = 1.a ," a Î Z⁺, i.e., a½a, " a Î Z^+.
Therefore "£ " is reflexive.
If a½b and b½c, then there exists d₁ and d₂ in Z⁺, such that b = d₁a and c = d₂b.
So, we have c = d₂d₁a.
As d₁, d₂ Î Z⁺, d₂d₁ Î Z⁺
Then a½c.
Hence, " £ " is transitive.
Already we have seen that " £ " is anti-symmetric.
Thus, " £ " is partial ordering.
Hence, (A, £ ) is a poset.

Example 3:
(R, £ ) is a poset, where R is the set of all real number and " £ " is "usual less than or equal to " (Prove!).

Example 4:
(P(S), Ì ) is not a poset, for, the relation Ì is anti-symmetric and transitive but not reflexive so it is not a poset.

Example 5:
Let S be the set of all subgroups of a group G. Then (S, Í ) is a poset (Prove!)

Example 6:
Let S be the set of all normal subgroups of G. then (S, Í ) is a poset (Prove!).

Example 7:
Let S = {( i₁, i₂,…,i_n) / i_r = 0 or 1, 1 £ r £ n}
Define (i₁,i₂,…,i_n) R ( j₁,j₂,…,j_n ) if and only if i₁ £ j₁, i₂ £ j₂,…,i_n £ j_n.
Then (S,R) is a poset (Prove!).

Back to top

6.2.2 Hasse Diagram

In this section we discuss the diagrammatic representation of a poset.

In a poset (A, £ ), if a £ b and a ¹ b then we write a <>in a poset (A, £ ), we say that a is a cover of b if a < b
and there exists no u such that a <>

A finite poset can be represented graphically, such a diagram of a poset is called Hasse diagram. We represent the
elements of A by points in the plane. If b is a cover of a then we place b above a and connect the two points a and b by a
straight line (actually directing from a to b). Thus, if a < b if and only if there is a ascending broken line (a path) connecting a to b.
If no line connecting a and b and a ¹ b, then a and b are not related or not comparable, that is, we have neither a £ b nor b £ a.



Example:

1. Hasse diagram of the poset ({1,2,3,4,5}, £ ), where £ is "usual less than or equal to" is given below.

2. Consider the poset (P(A₃), Í ), where A₃ = {a, b, c}. The Hasse diagram of (P(A₃), Í ) is given below :
te that actually all the lines should have upward directions. Since all the lines are having only one direction, it is a convention
to draw without direction in the lines. Thus, in the Hasse diagram every path has only upward direction, i.e., there cannot be any
path connecting top to bottom in the downward direction.
In the above example we see that {a} and {a, b, c} are related, since there is an ascending path from {a} to {a, b, c}, while {a}
and {b} are not related or not comparable, since there is no ascending path connecting {a} and {b}.

3. Let D_n denote the set of all positive divisiors of a positive integer n.
Hasse diagram of the poset (D₁₂, ½) is given below.



Conversely, if we have a Hasse diagram then we can describe the poset, that is, we can describe the partial order relation.
For example, consider the Hasse diagram given below :



Then the set is {a, b, c, d, e, f, g} and the relation £ is {(a, a) (a, c) (a, d), (a,e), (a, f), (a, g), (b, b), (b, c), (b, d), (g, e), (g, f),
(b, g), (c, c), (c, d), (c, e), (c, f), (c, g), (d, d), (d, e), (d, f), (d, g), (e, e), (e, g), (f, f), (f, g), (g, g)}.

One can check that £ is indeed partial ordering.

So, we conclude that for the finite poset it is enough to just give the Hasse diagram to describe the poset.

Remark:

From the above examples of the posets, we observe that in a poset it is not necessary that all the pair of elements are related or
comparable, that is, in a poset not necessarily all the elements are ordered. That is the reason we call such sets (posets) as
partially ordered set.

6.2.3 Totally Ordered Set and Dual Poset


In this section we define totally ordered set and dual poset and discuss about them.

A partial order relation £ on a set A is called a total order (or linear order) if, for each a, b A either a £ b or b £ a.
If £ is a totally order on a set A, then (A, £ ) is called totally ordered set or linearly ordered set or chain.

Example 1:

The poset (N, £ ), where N is the set of all natural numbers and £ is the usual "less than or equal to", is a totally ordered set, since
for any two a, b Î N, we have either a £ b or b £ a.

In fact, ( Z, £ ), ( Q, £ ) ( R, £ ), are all totally ordered set, where Z, the set of all integers, Q, the set of all rational numbers and
R, the set of all real number and £ is usual less than or equal to. Also, any finite subset of either Z or Q or R with usual "less than
or equal to" are also totally ordered sets.

Example 2:
( D₃₀, ½) is not a totally ordered set (Prove !)


Exercise:

Let L be the set of complex numbers z = x + iy, where x and y are rationals.
Define a partial order " £ " on L by: x₁ + iy₁ £ x₂ + iy₂ if and only if y₁ £ y₂.

Is ( L, £ ) a totally ordered set. If not, what is the additional condition needed in order to make ( L, £ ) into a chain?

Remark 1:
From the definition of totally ordered set, it is clear that any two elements in a totally ordered set are related or comparable. That
is, in a totally ordered set all the elements are ordered or related. That is the reason we call such sets as totally ordered set.


If R is a relation from A to B then R^-1 defined by (a, b)Î R^-1 if and only if (b, a)Î R, is a relation from B to A, called the
converse relation of R.

Remark 2:
If (A, R) is a partially ordered set then (A, R^-1) is a partial ordered set.

Proof:
Let (A, R) be a poset. Then R is a partial ordering on A. Therefore, R is reflexive, anti-symmetric and transitive.
Now we shall prove that R^-1 is reflexive, anti-symmetric and transitive.
Since R is reflexive, we have, (a, a) Î R ,for all a Î A.
Therefore, (a, a) Î R^-1, for all a Î A also.
Thus, R^-1 is reflexive.
If aR^-1 b and bR^-1a, then by definition of R^-1 we have bRa and aRb.
Since R is anti-symmetric, we have a = b. Therefore, R^-1 is anti-symmetric.
Let aR^-1 b and bR^-1c. Then by definition of R^-1, we have bRa and cRb.
Since R is transitive, we have cRa. Therefore, aR^-1c. Thus, R^-1 is transitive.
Hence (A, R^-1) is a partially ordered set.

Note:

Since we use £ for denoting partial ordering we denote ³ for its converse. Thus, if (A, £ ) is a partial ordered set then (A, ³ ) is
also partial ordered set. The poset (A, ³ ) is called dual poset to the poset (A, £ ).

Remark 3: (Duality Principle)

Every statement or formula or expression on an ordered set (A, £ ) remains correct if everywhere in the statement the relation £
is replaced by its converse relation ³ .

Back to top

6.2.4 Extremal Elements of Partially Ordered Sets

In this section we discuss about the extremal elements of a poset. Let (A, £ ) be a poset. An element aÎ A is called a maximal
element of A if there is no element c in A such that a < face="Symbol">Î A is called a minimal element of A if there is no
element c in A such that c < face="Symbol">Î A is called a greatest element of A if x £ a, for all xÎ A. Similarly, an
element aÎ A is called a least element of A if a £ x, for all xÎ A.

Example:

Consider the following poset represented by the following Hasse diagram

In this poset, a, f and i are minimal elements c, h, k are maximal elements, there is a no greatest element and there is no least
element.

Consider the following posets represented by Hasse diagrams.


In the poset (i), a is the least and minimal element and d is the greatest and maximal element.
In the poset (ii), a is the least and minimal element and d and e are maximal elements but there is no greatest element.

Remark:

In a poset, least element or greatest element need not always exist. It is clear that least element is a minimal element and greatest
element is a maximal element but not conversely.


Exercise:

1. Let (A, £ ) be a finite non empty poset. Then prove that A has at least one maximal element and at least one minimal
   element.
   
2. Let (A, £ ) be a poset. Then prove that if least element or greatest element exist then they are unique.

Let (A, £ ) be a poset and B Í A.

1. a Î A is called an upper bound of B if and only if b £ a, for all b Î B.
   
2. a Î A is called a lower bound of B if and only if a £ b, for all b Î B.
   
3. An lower bound g of B is called a greatest lower bound or infimum if and only if h £ g for every lower bound h of
   B in A and it is denoted by inf B or GLB of B.
   
4. An upper bound v of B is called least upper bound or superimum if and only if v £ u for all upper bound u of B in A
   and it is denoted by sup B or LUB of B.

Example:

Consider the poset (D₃₀ ,½), i..e ({30, 15, 10, 6, 5, 3, 2, 1}, ½ ).

Let B = {2, 3, 6}. Then inf B = 1, upper bounds of B are 6 and 30 but supB = 6.

Exercise:

Let (A, £ ) be a poset and let B Í A. Prove that if inf B or sup B exist then they are unique.

Exit Quiz Questions:

1. On the set A = {a, b, c}, find all partial orders £ in which a £ b?
   
2. If (A, £ ) is a poset and A' is a subset of A. check whether (A', ' ) is also a poset, where ' is the restriction of £ to A.
   
3. Construct the Hasse diagram of (D₃₀ ,½) and (P(A₃), £ ), where A₃ = {1,2,3} Do they have structural similarity?
   
4. Find ( i ) all the lower bound of B.
   ( ii ) all the upper bound of B.
   ( iii ) the least upper bound of B.
   ( iv ) the greatest lower bound of B, where B = {c, d, e} in the poset represented by the following poset.
   
   
5. Whether every finite poset has maximal element? If yes, justify your answer