Partial Orders Section 8 6 of Rosen Spring 2010 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 Spring 2010 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 Spring 2010 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 Spring 2010 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 Spring 2010 Partial Orders 5 Partial Orderings Notation We use the notation apb when a b R apb when a b R and a b preccurlyeq prec The notation p is not to be mistaken for less than The notation p is used to denote any partial ordering CSCE 235 Spring 2010 Partial Orders 6 Comparability Definition Definition The elements a and b of a poset S p are called comparable if either apb or bpa When for a b S we have neither apb nor bpa we say that a b are incomparable Consider again our renovation example Remove Asbestos p ai for all activities ai except assign offices Paint walls p Refinish floors Some tasks are incomparable Replacing windows can be done before after or during the assignment of offices CSCE 235 Spring 2010 Partial Orders 7 Total orders Definition Definition If S p is a poset and every two elements of S are comparable S is called a totally ordered set The relation p 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 Spring 2010 Partial Orders 8 Well Orderings Definition Definition S p is a well ordered set if It is a poset Such that p 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 Spring 2010 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 Spring 2010 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 xpy then P y is true CSCE 235 Spring 2010 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 xpa then P a holds by the induction step This yields a contradiction QED CSCE 235 Spring 2010 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 Spring 2010 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 Spring 2010 Partial Orders 14 Lexicographic Orderings on A1 A2 Formally lexicographic ordering is defined by two other orderings Definition Let A1 p1 and A2 p2 be two posets The lexicographic ordering p on the Cartesian product A1 A2 is defined by a1 a2 p a 1 a 2 if a1p1a 1 or a1 a 1 and a2p2 a 2 If we add equality to the lexicographic ordering p on A1 A2 we obtain a partial ordering CSCE 235 Spring 2010 Partial Orders 15 Lexicographic Ordering on A1 A2 An Lexicographic ordering generalizes to the Cartesian Product of n set in a natural way Define p on A1 A2 An by a1 a2 an p b1 b2 bm If a1 p b1 or of there is an integer i 0 such that a1 b1 a2 b2 ai bi and ai 1p bi 1 CSCE 235 Spring 2010 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 p be the lexicographic ordering on St a1a2 am is less than b1b2 bn if and only if a1 a2 at p b1 b2 bt or a1 a2 at b1 b2 bt and m n CSCE 235 Spring 2010 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 Spring 2010 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
View Full Document
Unlocking...