Notes Partial Orders Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Section 8 6 of Rosen cse235 cse unl edu Partial Orders I Notes Motivating Introduction Consider the recent renovation of Avery Hall In this process several things had to be done I Remove Asbestos I Replace Windows I Paint Walls I Refinish Floors I Assign Offices I Move in Office Furniture Partial Orders II Motivating Introduction Clearly some things had to be done before others could even begin Asbestos had to be removed before anything painting had to be done before the floors to avoid ruining them etc On the other hand several things could have been done concurrently painting could be done while replacing the windows and assigning office could have been done at anytime Such a scenario can be nicely modeled using partial orderings Notes Partial Orderings I Notes Definition Definition A relation R on a set S is called a partial order if it is reflexive antisymmetric and transitive A set S together with a partial ordering R is called a partially ordered set or poset for short and is denoted S R Partial orderings are used to give an order to sets that may not have a natural one In our renovation example we could define an ordering such that a b R if a must be done before b can be done Partial Orderings II Notes Definition We use the notation a4b to indicate that a b R is a partial order and a b when 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 Comparability Notes Definition The elements a and b of a poset S 4 are called comparable if either a 4 b or b 4 a When a b S such that neither are comparable we say that they are incomparable Looking back at our renovation example we can see that Remove Asbestos ai for all activities ai Also Paint Walls Refinish Floors Some items are also incomparable replacing windows can be done before after or during the assignment of offices Total Orders Notes Definition If S 4 is a poset and every two elements of S are comparable S is called a totally ordered set The relation 4 is said to be a total order Example The set of integers over the relation less than equal to is a total order Z since for every a b Z it must be the case that a b or b a What happens if we replace with Well Orderings Notes Definition S 4 is a well ordered set if it is a poset such that 4 is a total ordering and such that every nonempty subset of S has a least element Example The natural numbers along with N is a well ordered set since any subset of N will have a least element and is a total ordering on N as before However Z is not a well ordered set Why Is it totally ordered Principle of Well Ordered Induction Well ordered sets are the basis of the proof technique known as induction 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 all x S if Basis Step P x0 is true for the least element of S and Induction Step For every y S if P x is true for all x y then P y is true Notes Principle of Well Ordered Induction Notes Proof Suppose 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 the induction step This yields a contradiction Lexicographic Orderings I Notes Lexicographic ordering is the same as any dictionary or phone book we use alphabetical order starting with the first character in the string then the next character if the first was equal etc you can consider no character for shorter words to be less than a Lexicographic Orderings II Formally lexicographic ordering is defined by combining two other orderings Definition Let A1 41 and A2 42 be two posets The lexicographic ordering 4 on the Cartesian product A1 A2 is defined by a1 a2 a01 a02 if a1 1 a01 or if a1 a01 and a2 2 a02 If we add equality to the lexicographic ordering on A1 A2 we obtain a partial ordering 4 Notes Lexicographic Orderings III Notes Lexicographic ordering generalizes to the Cartesian product of n sets in the natural way Define 4 on A1 A2 An by a1 a2 an b1 b2 bn if a1 b1 or if there is an integer i 0 such that a1 b1 a2 b2 ai bi and ai 1 bi 1 Lexicographic Orderings I Notes Strings Consider the two non equal strings a1 a2 am and b1 b2 bn on a poset S Let t min n m and is the lexicographic ordering on S t a1 a2 am is less than b1 b2 bn if and only if I a1 a2 at b1 b2 bt or I a1 a2 at b1 b2 bt and m n Hasse Diagrams As with relations and functions there is a convenient graphical representation for partial orders Hasse Diagrams Consider the digraph representation of a partial order since we know we are dealing with a partial order we implicitly know that the relation must be reflexive and transitive Thus we can simplify the graph as follows I Remove all self loops I Remove all transitive edges I Make the graph direction less that is we can assume that the orientations are upwards The resulting diagram is far simpler Notes Hasse Diagram Notes Example a4 a5 a2 a3 a1 Remove Self Loops Hasse Diagram Notes Example a4 a5 a2 a3 a1 Remove Transitive Loops Hasse Diagram Notes Example a4 a5 a2 a3 a1 Remove Orientation Hasse Diagram Notes Example a4 a5 a2 a3 a1 Hasse Diagram Hasse Diagrams Notes Example Of course you need not always start with the complete relation in the partial order and then trim everything Rather you can build a Hasse directly from the partial order Example Draw 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 60 which form the basis of the ancient Babylonian base 60 numeral system Hasse Diagrams Notes Example Answer 60 12 4 20 6 2 30 10 3 1 15 5 Extremal Elements I Notes Summary We will define the following terms I A maximal minimal element in a poset S 4 I The maximum greatest minimum least element of a poset S 4 I An upper lower bound element of a subset A of a poset S 4 …
View Full Document
Unlocking...