Partial Orders CSE235 Partial Orders Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 1 Sections 7 6 of Rosen Partial Orders I Motivating Introduction Partial Orders CSE235 Consider the recent renovation of Avery Hall In this process several things had to be done Remove Asbestos Replace Windows Paint Walls Refinish Floors Assign Offices Move in Office Furniture 2 1 Partial Orders II Motivating Introduction Partial Orders CSE235 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 3 1 Partial Orderings I Definition Partial Orders CSE235 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 4 1 Partial Orderings II Definition Partial Orders CSE235 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 5 1 Comparability Partial Orders CSE235 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 6 1 Total Orders Partial Orders CSE235 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 7 1 Well Orderings Partial Orders CSE235 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 8 1 Principle of Well Ordered Induction Partial Orders CSE235 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 9 1 Principle of Well Ordered Induction Proof Partial Orders CSE235 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 10 1 Lexicographic Orderings I Partial Orders CSE235 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 11 1 Lexicographic Orderings II Partial Orders CSE235 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 4 a01 a02 if a1 1 a01 or if a1 a01 and a2 42 a02 12 1 Lexicographic Orderings III Partial Orders CSE235 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 13 1 Lexicographic Orderings I Strings Partial Orders CSE235 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 a1 a2 at b1 b2 bt or a1 a2 at b1 b2 bt and m n 14 1 Hasse Diagrams Partial Orders CSE235 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 Remove all self loops Remove all transitive edges Make the graph direction less that is we can assume that the orientations are upwards The resulting diagram is far simpler 15 1 Hasse Diagram Example Partial Orders CSE235 a4 a5 a2 a3 a1 Remove Self Loops 16 1 Hasse Diagram Example Partial Orders CSE235 a4 a5 a2 a3 a1 Remove Transitive Loops 17 1 Hasse Diagram Example Partial Orders CSE235 a4 a5 a2 a3 a1 Remove Orientation 18 1 Hasse Diagram Example Partial Orders CSE235 a4 a5 a2 a3 a1 Hasse Diagram 19 1 Hasse Diagrams Example Partial Orders CSE235 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 20 1 Hasse Diagrams Example Answer Partial Orders 60 CSE235 12 4 20 6 2 10 3 1 …
View Full Document
Unlocking...