Partial OrdersSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSection 8.6 of [email protected] Orders IMotivating IntroductionConsider the recent renovation of Avery Hall. In this processseveral things had to be done.IRemove AsbestosIReplace WindowsIPaint WallsIRefinish FloorsIAssign OfficesIMove in Office-Furniture.Partial Orders IIMotivating IntroductionClearly, some things had to be done before others could evenbegin—Asbestos had to be removed before anything; painting hadto 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 the windowsand assigning office could have been done at anytime.Such a scenario can be nicely modeled using partial orderings.Partial 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 short and isdenoted(S, R)Partial orderings are used to give an order to sets that may nothave a natural one. In our renovation example, we could define anordering such that (a, b) ∈ R if a must be done before b can bedone.Partial 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 “les s than equal to.”Rather, ≺ is used to denote any partial ordering.Latex notation: \preccurlyeq, \prec.ComparabilityDefinitionThe elements a and b of a poset (S, 4) are called comparable ifeither a 4 b or b 4 a. When a, b ∈ S such that neither arecomparable, we say that the y 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 be donebefore, after or during the assignment of offices.Total OrdersDefinitionIf (S, 4) is a poset and every two elements of S are comparable, Sis called a totally ordered set. The relation 4 is said to be a totalorder.ExampleThe set of integers over the relation “less than equal to” is a totalorder; (Z, ≤) since for every a, b ∈ Z, it must be the case thata ≤ b or b ≤ a.What happens if we replace ≤ with <?Well-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?Principle 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 ≺ y thenP (y) is true.Principle 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. Lexicographic Orderings ILexicographic ordering is the same as any dictionary or phonebook—we use alphabetical order starting with the first character inthe string, then the next character (if the first was equal) etc. (youcan consider “no character” for shorter words to be less than “a”).Lexicographic Orderings IIFormally, lexicographic ordering is defined by combining two otherorderings.DefinitionLet (A1, 41) and (A2, 42) be two posets. The lexicographicordering 4 on the Cartesian product A1× A2is defined by(a1, a2) ≺ (a01, a02)if a1≺1a01or if a1= a01and a2≺2a02.If we add equality to the lexicographic ordering ≺ on A1× A2, weobtain a partial ordering 4.Lexicographic Orderings IIILexicographic ordering generalizes to the Cartesian product of nsets 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 t hata1= b1, a2= b2, . . . , ai= biand ai+1≺ bi+1Lexicographic Orderings IStringsConsider the two non-equal strings a1a2· · · amand b1b2· · · bnon aposet S.Let t = min(n, m) and ≺ is the lexicographic ordering on St.a1a2· · · amis less than b1b2· · · bnif and only ifI(a1, a2, . . . , at) ≺ (b1, b2, . . . , bt), orI(a1, a2, . . . , at) = (b1, b2, . . . , bt) and m < nHasse DiagramsAs with relations and functions, there is a convenient graphicalrepresentation for partial orders—Hasse Diagrams.Consider the digraph representation of a partial order—since weknow we are dealing with a partial order, we implicitly know t hatthe relation must be reflexive and transitive. Thus we can simplifythe graph as follows:IRemove all self-loops.IRemove all transitive edges.IMake the graph direction-less—that is, we can assume thatthe orientations are upwards.The resulting diagram is far simpler.Hasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!Hasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!Hasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!Hasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!Hasse DiagramsExampleOf course, you need not always start with the complete relation inthe partial order and then trim everything. Rather, you can build aHasse directly from the partial order.ExampleDraw a Hasse diagram for the partial ordering{(a, b) | a | b}on {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} (these are the divisors of 60which form the basis of the ancient Babylonian base-60 numeralsystem)Hasse DiagramsExample Answer12 3 54 6 10 1512 20 3060Extremal Elements ISummaryWe will define t he following terms:IA maximal/minimal element in a poset (S, 4).IThe maximum (greatest)/minimum (least) element of a poset(S, 4).IAn upper/lower bound element of a subset A of a
View Full Document
Unlocking...