Partial Orders Section 8 6 of Rosen Fall 2008 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline Motivating example Definitions Partial ordering comparability total ordering well ordering Principle of well ordered induction Lexicographic orderings Hasse Diagrams Extremal elements Lattices Topological Sorting CSCE 235 Fall 2008 Partial Orders 2 Motivating Example 1 Consider the renovation of Avery Hall In this process several tasks were undertaken Remove Asbestos Replace windows Paint walls Refinish floors Assign offices Move in office furniture CSCE 235 Fall 2008 Partial Orders 3 Motivating Example 2 Clearly some things had to be done before others could begin Asbestos had to be removed before anything except assigning offices Painting walls had to be done before refinishing floors to avoid ruining them etc On the other hand several things could be done concurrently Painting could be done while replacing the windows Assigning offices could be done at anytime before moving in office furniture This scenario can be nicely modeled using partial orderings CSCE 235 Fall 2008 Partial Orders 4 Partial Orderings Definitions Definitions A relation R on a set S is called a partial order if it is Reflexive Antisymmetric Transitive A set S together with a partial ordering R is called a partially ordered set poset for short and is denote 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 CSCE 235 Fall 2008 Partial Orders 5 Partial Orderings Notation We use the notation a b when a b R a b when a b R and a b preccurlyeq prec The notation is not to be mistaken for less than The notation is used to denote any partial ordering CSCE 235 Fall 2008 Partial Orders 6 Comparability Definition Definition The elements a and b of a poset S are called comparable if either a b or b a When for a b S we have neither a b nor b a we say that a b are incomparable Consider again our renovation example Remove Asbestos ai for all activities ai except assign offices Paint walls Refinish floors Some tasks are incomparable Replacing windows can be done before after or during the assignment of offices CSCE 235 Fall 2008 Partial Orders 7 Total orders Definition Definition If S is a poset and every two elements of S are comparable S is called a totally ordered set The relation is said to be a total order Example The relation less than or equal to over the set of integers Z since for every a b Z it must be the case that a b or b a What happens if we replace with The relation is not reflexive and Z is not a poset CSCE 235 Fall 2008 Partial Orders 8 Well Orderings Definition Definition S is a well ordered set if It is a poset Such that is a total ordering and Such that every non empty subset of S has a least element Example The natural numbers along with N is a well ordered set since any nonempty subset of N has a least element and is a total ordering on N However Z is not a well ordered set Why Is it totally ordered CSCE 235 Fall 2008 Z Z but does not have a least element Yes Partial Orders 9 Outline Motivating example Definitions Partial ordering comparability total ordering well ordering Principle of well ordered induction Lexicographic orderings Hasse Diagrams Extremal elements Lattices Topological Sorting CSCE 235 Fall 2008 Partial Orders 10 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 Given 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 in S and Induction Step For every y S if P x is true for all x y then P y is true CSCE 235 Fall 2008 Partial Orders 11 Principle of Well Ordered Induction Proof Proof S well ordered Basis Step Induction Step x S P x Suppose that it is not the case the P x holds for all x S y P y is false A x S P x is false is not empty S is well ordered A has a least element a Since P x0 is true and P a is false a x0 P x holds for all x S and x a then P a holds by the induction step This yields a contradiction QED CSCE 235 Fall 2008 Partial Orders 12 Outline Motivating example Definitions Partial ordering comparability total ordering well ordering Principle of well ordered induction Lexicographic orderings Idea on A1 A2 A1 A2 An St strings Hasse Diagrams Extremal elements Lattices Topological Sorting CSCE 235 Fall 2008 Partial Orders 13 Lexicographic Orderings Idea Lexigraphic ordering is the same as any dictionary or phone book ordering We use alphabetic ordering Starting with the first character in the string Then the next character if the first was equal etc If a word is shorter than the other than we consider that the no character of the shorter word to be less than a CSCE 235 Fall 2008 Partial Orders 14 Lexicographic Orderings on A1 A2 Formally lexicographic ordering is defined by two other orderings Definition Let A1 1 and A2 2 be two posets The lexicographic ordering on the Cartesian product A1 A2 is defined by a1 a2 a 1 a 2 if a1 1a 1 or a1 a 1 and a2 2 a 2 If we add equality to the lexicographic ordering on A1 A2 we obtain a partial ordering CSCE 235 Fall 2008 Partial Orders 15 Lexicographic Ordering on A1 A2 An Lexicographic ordering generalizes to the Cartesian Product of n set in a natural way Define on A1 A2 An by a1 a2 an b1 b2 bm If a1 b1 or of there is an integer i 0 such that a1 b1 a2 b2 ai bi and ai 1 bi 1 CSCE 235 Fall 2008 Partial Orders 16 Lexicographic Ordering on Strings Consider the two non equal strings a1a2 am and b1b2 bn on a poset S Let t min n m and let be the lexicographic ordering on St a1a2 am is less than b1b2 bn if and only if a1 a2 at b1 b2 bt or a1 a2 at b1 b2 bt and m n CSCE 235 Fall 2008 Partial Orders 17 Outline Motivating example Definitions Partial ordering comparability total ordering well ordering Principle of well ordered induction Lexicographic orderings Hasse Diagrams Extremal elements Lattices Topological Sorting CSCE 235 Fall 2008 Partial Orders 18 Hasse Diagrams Like relations and functions partial orders have a convenient graphical representation Hasse Diagrams Consider the digraph representation of a partial order Because we are dealing with a partial order we know that the relation must be reflexive and transitive Thus we can …
View Full Document
Unlocking...