Partial OrdersCSE235Partial OrdersSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 7.6 of [email protected] / 1Partial OrdersCSE235Partial Orders IMotivating IntroductionConsider the recent renovation of Avery Hall. In this processseveral things had to be done.Remove AsbestosReplace WindowsPaint WallsRefinish FloorsAssign OfficesMove in Office-Furniture.2 / 1Partial OrdersCSE235Partial Orders IIMotivating IntroductionClearly, some things had to be done before others could evenbegin—Asbestos had to be removed before anything; paintinghad to be done before the floors to avoid ruining them, etc.On the other hand, several things could have been doneconcurrently—painting could be done while replacing thewindows and assigning office could have been done at anytime.Such a scenario can be nicely modeled using partial orderings.3 / 1Partial OrdersCSE235Partial Orderings IDefinitionDefinitionA relation R on a set S is called a partial order if it is reflexive,antisymmetric and transitive. A set S together with a partialordering R is called a partially ordered set or poset for shortand is denoted(S, R)Partial orderings are used to give an order to sets that may nothave a natural one. In our renovation example, we could definean ordering such that (a, b) ∈ R if a must be done before b canbe done.4 / 1Partial OrdersCSE235Partial Orderings IIDefinitionWe use the notationa 4 bto indicate that (a, b) ∈ R is a partial order anda ≺ bwhen a 6= b.The notation ≺ is not to be mistaken for “less than equal to.”Rather, ≺ is used to denote any partial ordering.Latex notation: \preccurlyeq, \prec.5 / 1Partial OrdersCSE235ComparabilityDefinitionThe elements a and b of a p oset (S, 4) are called comparable ifeither a 4 b or b 4 a. When a, b ∈ S such that neither arecomparable, we say that they are incomparable.Looking back at our renovation example, we can see thatRemove Asbestos ≺ aifor all activities ai. Also,Paint Walls ≺ Refinish FloorsSome items are also incomparable—replacing windows can bedone before, after or during the assignment of offices.6 / 1Partial OrdersCSE235Total OrdersDefinitionIf (S, 4) is a poset and every two elements of S arecomparable, S is called a totally ordered set. The relation 4 issaid to be a total order.ExampleThe set of integers over the relation “less than equal to” is atotal order; (Z, ≤) since for every a, b ∈ Z, it must be the casethat a ≤ b or b ≤ a.What happens if we replace ≤ with <?7 / 1Partial OrdersCSE235Well-OrderingsDefinition(S, 4) is a well-ordered set if it is a poset such that 4 is a totalordering and such that every nonempty subset of S has a leastelementExampleThe natural numbers along with ≤, (N, ≤) is a well-ordered setsince any subset of N will have a least element and ≤ is a totalordering on N as before.However, (Z, ≤) is not a well-ordered set. Why? Is it totallyordered?8 / 1Partial OrdersCSE235Principle of Well-Ordered InductionWell-ordered sets are the basis of the proof technique known asinduction (more when we cover Chapter 3).Theorem (Principle of Well-Ordered Induction)Suppose that S is a well ordered set. Then P (x) is true for allx ∈ S ifBasis Step: P (x0) is true for the least element of S andInduction Step: For every y ∈ S if P (x) is true for all x ≺ ythen P (y) is true.9 / 1Partial OrdersCSE235Principle of Well-Ordered InductionProofSuppose it is not the case that (P (x) holds for all x ∈ S ⇒∃y P (y) is false ⇒ A = {x ∈ S|P (x) is false} is not empty.Since S is well ordered, A has a least element a.P (x0) is true ⇒ a 6= x0.P (x) holds for all x ∈ S and x ≺ a, then P (a) holds, by theinduction step.This yields a contradiction. 10 / 1Partial OrdersCSE235Lexicographic Orderings ILexicographic ordering is the same as any dictionary or phonebook—we use alphabetical order starting with the firstcharacter in the string, then the next character (if the first wasequal) etc. (you can consider “no character” for shorter wordsto be less than “a”).11 / 1Partial OrdersCSE235Lexicographic Orderings IIFormally, lexicographic ordering is defined by combining twoother orderings.DefinitionLet (A1, 41) and (A2, 42) be two posets. The lexicographicordering 4 on the Cartesian product A1× A2is defined by(a1, a2) 4 (a01, a02)if a1≺1a01or if a1= a01and a242a02.12 / 1Partial OrdersCSE235Lexicographic Orderings IIILexicographic ordering generalizes to the Cartesian product ofn sets in the natural way.Define 4 on A1× A2× · · · × Anby(a1, a2, . . . , an) ≺ (b1, b2, . . . , bn)if a1≺ b1or if there is an integer i > 0 such thata1= b1, a2= b2, . . . , ai= biand ai+1≺ bi+113 / 1Partial OrdersCSE235Lexicographic Orderings IStringsConsider the two non-equal strings a1a2· · · amand b1b2· · · bnon a poset S.Let t = min(n, m) and ≺ is the lexicographic ordering on St.a1a2· · · amis less than b1b2· · · bnif and only if(a1, a2, . . . , at) ≺ (b1, b2, . . . , bt), or(a1, a2, . . . , at) = (b1, b2, . . . , bt) and m < n14 / 1Partial OrdersCSE235Hasse DiagramsAs with relations and functions, there is a convenient graphicalrepresentation for partial orders—Hasse Diagrams.Consider the digraph representation of a partial order—sincewe know we are dealing with a partial order, we implicitly knowthat the relation must be reflexive and transitive. Thus we cansimplify the graph as follows:Remove all self-loops.Remove all transitive edges.Make the graph direction-less—that is, we can assumethat the orientations are upwards.The resulting diagram is far simpler.15 / 1Partial OrdersCSE235Hasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!16 / 1Partial OrdersCSE235Hasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!17 / 1Partial OrdersCSE235Hasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!18 / 1Partial OrdersCSE235Hasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!19 / 1Partial OrdersCSE235Hasse DiagramsExampleOf course, you need not always start with the complete relationin the partial order and then trim everything. Rather, you canbuild a Hasse directly from the partial order.ExampleDraw a Hasse diagram for the partial ordering{(a, b) | a | b}on {1, 2, 3, 4, 5, 6,
View Full Document
Unlocking...