Partial Orders I Partial Orders Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics 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 Section 8 6 of Rosen cse235 cse unl edu Partial Orders II Partial Orderings I Motivating Introduction Definition Definition 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 Partial Orderings II 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 Comparability Definition 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 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 Well Orderings Definition 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 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 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 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 What happens if we replace with However Z is not a well ordered set Why Is it totally ordered Principle of Well Ordered Induction Principle of Well Ordered Induction Proof Well ordered sets are the basis of the proof technique known as induction more when we cover Chapter 3 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 Theorem Principle of Well Ordered Induction Since S is well ordered A has a least element a Suppose that S is a well ordered set Then P x is true for all x S if P x0 is true a 6 x0 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 Lexicographic Orderings I P x holds for all x S and x a then P a holds by the induction step This yields a contradiction Lexicographic Orderings II Formally lexicographic ordering is defined by combining two other orderings Definition 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 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 Lexicographic Orderings III Lexicographic Orderings I Strings 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 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 if a1 b1 or if there is an integer i 0 such that a1 b1 a2 b2 ai bi I a1 a2 at b1 b2 bt or I a1 a2 at b1 b2 bt and m n and ai 1 bi 1 Hasse Diagrams Hasse Diagram Example As with relations and functions there is a convenient graphical representation for partial orders Hasse Diagrams a4 a5 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 a2 a3 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 a1 Remove Self Loops The resulting diagram is far simpler Hasse Diagram Hasse Diagram Example Example a4 a5 a4 a5 a2 a3 a2 a3 a1 Remove Transitive Loops a1 Remove Orientation Hasse Diagram Hasse Diagrams Example Example a4 a5 a2 a3 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 a1 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 Diagram Hasse Diagrams Extremal Elements I Example Answer Summary 60 We will define the following terms 12 4 20 6 2 30 10 3 15 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 I The greatest lower least upper bound element of a subset A of a poset S 4 I Lattice 5 1 Extremal Elements I …
View Full Document
Unlocking...