DOC PREVIEW
UNL CSCE 235 - Partia lOrders

This preview shows page 1-2-3-4-5 out of 14 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Partial OrdersSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSection 8.6 of [email protected] Orders IMotivating IntroductionConsider the recent renovation of Avery Hall. In this processseveral things had to be done.IRemove AsbestosIReplace WindowsIPaint WallsIRefinish FloorsIAssign OfficesIMove in Office-Furniture.NotesPartial Orders IIMotivating IntroductionClearly, some things had to be done before others could evenbegin—Asbestos had to be removed before anything; painting hadto be done before the floors to avoid ruining them, etc.On the other hand, several things could have been doneconcurrently—painting could be done while replacing the windowsand assigning office could have been done at anytime.Such a scenario can be nicely modeled using partial orderings.NotesPartial Orderings IDefinitionDefinitionA relation R on a set S is called a partial order if it is reflexive,antisymmetric and transitive. A set S together with a partialordering R is called a partially ordered set or poset for short and isdenoted(S, R)Partial orderings are used to give an order to sets that may nothave a natural one. In our renovation example, we could define anordering such that (a, b) ∈ R if a must be done before b can bedone.NotesPartial Orderings IIDefinitionWe use the notationa 4 bto indicate that (a, b) ∈ R is a partial order anda ≺ bwhen 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.NotesComparabilityDefinitionThe elements a and b of a poset (S , 4) are called comparable ifeither a 4 b or b 4 a. When a, b ∈ S such that neither arecomparable, we say that they are incomparable.Looking back at our renovation example, we can see thatRemove Asbestos ≺ aifor all activities ai. Also,Paint Walls ≺ Refinish FloorsSome items are also incom parable—replacing windows can be donebefore, after or during the assignment of offices.NotesTotal OrdersDefinitionIf (S, 4) is a poset and every two elem ents of S are comparable, Sis called a totally ordered set. The relation 4 is said to be a totalorder.ExampleThe set of integers over the relation “less than equal to” is a totalorder; (Z, ≤) since for every a, b ∈ Z, it must be the case thata ≤ b or b ≤ a.What happens if we replace ≤ with <?NotesWell-OrderingsDefinition(S, 4) is a well-ordered set if it is a poset such that 4 is a totalordering and such that every nonempty subset of S has a leastelementExampleThe natural numbers along with ≤, (N, ≤) is a well-ordered setsince any subset of N will have a least element and ≤ is a totalordering on N as before.However, (Z, ≤) is not a well-ordered set. Why? Is it totallyordered?NotesPrinciple of Well-Ordered InductionWell-ordered sets are the basis of the proof technique known asinduction (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 allx ∈ S ifBasis Step: P (x0) is true for the least ele ment of S andInduction Step: For every y ∈ S if P (x) is true for all x ≺ y thenP (y) is true.NotesPrinciple of Well-Ordered InductionProofSuppose 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 theinduction step.This yields a contradiction. NotesLexicographic Orderings ILexicographic ordering is the same as any dictionary or phonebook—we use alphabetical order starting with the first character inthe string, then the next character (if the first was equal) etc. (youcan consider “no character” for shorter words to be less than “a”).NotesLexicographic Orderings IIFormally, lexicographic ordering is defined by combining two otherorderings.DefinitionLet (A1, 41) and (A2, 42) be two posets. The lexicographicordering 4 on the Cartesian product A1× A2is defined by(a1, a2) ≺ (a01, a02)if a1≺1a01or if a1= a01and a2≺2a02.If we add equality to the lexicographic ordering ≺ on A1× A2, weobtain a partial ordering 4.NotesLexicographic Orderings IIILexicographic ordering generalizes to the Cartesian product of nsets in the natural way.Define 4 on A1× A2× · · · × Anby(a1, a2, . . . , an) ≺ (b1, b2, . . . , bn)if a1≺ b1or if there is an integer i > 0 such thata1= b1, a2= b2, . . . , ai= biand ai+1≺ bi+1NotesLexicographic Orderings IStringsConsider the two non-equal strings a1a2· · · amand b1b2· · · bnon aposet S.Let t = min(n, m) and ≺ is the lexicographic ordering on St.a1a2· · · amis less than b1b2· · · bnif and only ifI(a1, a2, . . . , at) ≺ (b1, b2, . . . , bt), orI(a1, a2, . . . , at) = (b1, b2, . . . , bt) and m < nNotesHasse DiagramsAs with relations and functions, there is a convenient graphicalrepresentation for partial orders—Hasse Diagrams.Consider the digraph representation of a partial order—since weknow we are dealing with a partial order, we implicitly know thatthe relation must be reflexive and transitive. Thus we can simplifythe graph as follows:IRemove all self-loops.IRemove all transitive edges.IMake the graph direction-less—that is, we can assume thatthe orientations are upwards.The resulting diagram is far simpler.NotesHasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!NotesHasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!NotesHasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!NotesHasse DiagramExamplea1a2a3a4a5Remove Self-LoopsRemove Transitive LoopsRemove OrientationHasse Diagram!NotesHasse DiagramsExampleOf course, you need not always s tart with the complete relation inthe partial order and then trim everything. Rather, you can build aHasse directly from the partial order.ExampleDraw 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 60which form the basis of the ancient Babylonian base-60 numeralsystem)NotesHasse DiagramsExample Answer12 3 54 6 10 1512 20 3060NotesExtremal Elements ISummaryWe will define the following terms:IA maximal/minimal element in a poset (S , 4).IThe


View Full Document

UNL CSCE 235 - Partia lOrders

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Partia lOrders
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Partia lOrders and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Partia lOrders 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?