9.6 Partial Orderings

Partial Orderings • Definition 1 ○ A relation R on a set S is called a partial ordering, or partial order, if it is reflexive, antisymmetric, and transitive. ○ A set together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R). ○ Members of S are called elements of the poset. • Example 1 ○ Show that the “greater than or equal” relation (≥) is a partial ordering on the set of integers. ○ Reflexivity: a≥a for every integer a. ○ Antisymmetry: If a≥b and b≥a , then a=b. ○ Transitivity: If a≥b and b≥c , then a≥c. • Example 2 ○ Show that the divisibility relation (∣) is a partial ordering on the set of integers. ○ Reflexivity § a∣a for all integers a. (see Example 9 in Section 9.1) ○ Antisymmetry § If a and b are positive integers with a | b and b | a, then a = b § (see Example 12 in Section 9.1) ○ Transitivity § Suppose that a divides b and b divides c. § Then there are positive integers k and l such that b = ak and c = bl § Hence, c=a(kl), so a divides c. § Therefore, the relation is transitive. ○ (Z^+, ∣) is a poset. • Example 3 ○ Show that the inclusion relation (⊆) is a partial ordering on the power set of a set S. ○ Reflexivity: A⊆A whenever A is a subset of S. ○ Antisymmetry: If A and B are positive integers with A⊆B and B⊆A, then A=B. ○ Transitivity: If A⊆B and B⊆C, then A⊆C. Comparability • Definition 2 ○ The elements a and b of a poset (S,≼) are comparable if either a ≼ b or b ≼ a. ○ a,b∈S so that neither a ≼ b nor b ≼ a, then a and b are called incomparable. • Definition 3 ○ If (S,≼) is a poset and every two elements of S are comparable ○ Then S is called a totally ordered or linearly ordered set ○ And ≼ is called a total order or a linear order. ○ A totally ordered set is also called a chain. • Definition 4 ○ (S,≼) is a well-ordered set if it is a poset such that § ≼ is a total ordering § every nonempty subset of S has a least element. Hasse Diagrams • A Hasse diagram is a visual representation of a partial ordering that leaves out edges that must be present because of the reflexive and transitive properties. • A partial ordering is shown in (a) of the figure above. • The loops due to the reflexive property are deleted in (b). • The edges that must be present due to the transitive property are deleted in (c). • The Hasse diagram for the partial ordering (a), is depicted in © Lexicographic Order • Definition ○ Given two posets (A_1,≼_1) and (A_2,≼_2) ○ The lexicographic ordering on A_1⨉A_2 is defined by specifying that ○ (a_1, a_2) is less than (b1,b2), that is, (a_1, a_2) ≺ (b_1,b_2), ○ either if a_1 ≺_1 b_1 or if a_1=b_1 and a_2 ≺_2 b_2. ○ This definition can be easily extended to a lexicographic ordering on strings (see text). • Example ○ Consider strings of lowercase English letters ○ A lexicographic ordering can be defined using the ordering of the letters in the alphabet ○ This is the same ordering as that used in dictionaries. ○ discreet ≺ discrete, because these strings differ in the seventh position and e ≺ t. ○ discreet ≺ discreetness, because the first eight letters agree, but the second string is longer. Well Ordered Induction • Theorem ○ If (S,≤) is a well ordered poset and P is a property s.t. ○ If P(y) is true for all y x, then P(x) is true ○ Then P is true for all elements in the poset • Example ○ Suppose that a_(m,n) is defined for (m,n)∈N×N § a_0,0=0 § a_(m,n)={■8(a_(m−1,n)+1&if n=0 and m 0@a_(m,n−1)+n&if n 0)┤ ○ Show that a_(m,n)=m+n(n+1)/2 is defined for all (m,n)∈N×N • Solution ○ Use induction ○ Basis Step § a_0,0=0+(0⋅1)/2 ○ Inductive Step § Assume that a_(m^′,n′ )=m^′+(n′ (n^′+1))/2 whenever § (m^′,n′) is less than (m,n) in the lexicographic ordering of N×N § If n=0, by the inductive hypothesis, we can conclude □ a_(m,n)=a_(m−1,n)+1=m−1+n(n+1)/2+1=m+n(n+1)/2 § If n 0, by the inductive hypothesis, we can conclude □ a_(m,n)=a_(m−1,n)+1=m+n(n−1)/2+n=m+n(n+1)/2 Maximal and Minimal Elements • Definition ○ If (S,≤) is a ordered poset then an element a is ○ Minimal if there is no element b s.t. b≤a, and b is not equal to a ○ Maximal if there is no element b s.t. a≤b, and b is not equal to a ○ Greatest if for every element b∈S, b≤a ○ Least if for every element b∈S, a≤b • Intuition ○ Minimal: No element is strictly smaller ○ Least: Every other element is bigger ○ Maximal: No element is strictly bigger ○ Greatest: Every other element is smaller • Example 1 ○ Let {2,4,5,10,12,20,25} ordered by divisibility relation ○ Which element of {2,4,5,10,12,20,25} are maximal and which are minimal? ○ Is there a least or greatest element? ○ Maximal: 12, 20, 25 ○ Minimal: 2,5 ○ No least or greatest element. • Example 2 ○ Given an example of a poset with no minimal element and two maximal elements? ○ {〖1,1〗^∗,0,−1,−2,−3,…} where 1≥0≥−1≥−2≥…, and 1^∗≥0≥−1≥−2≥… Topological Sorting • Definition ○ If (S,R) is a partial ordering and (S,R^∗ ) is a total ordering then we say that ○ The two are compatible if R is a subset of R^∗ • Theorem ○ Let S be a finite set ○ Every partial order R on S has a compatible total order R^∗ • Proof ○ Every nonempty finite partial order has a minimal element ○ This can be proved by induction on the size of S ○ We should build a total ordering of S be selecting § a_1 to be a minimal element of S § a_2 to be the minimal element of S−{a_1 } § a_i to be the minimal element of S−{a_1,a_2,…,a_(i−1) } § a_n to be the least available element of S ○ We set R^∗={(a_i,a_i )|j≥i}