Partial and Total Orders in Discrete Mathematics
Explore the concepts of partial and total orders in discrete mathematics, including definitions, properties, and examples. Learn how these order relations apply to integer and rational numbers, with insights on reflexivity, transitivity, and anti-symmetry. Discover the distinction between partial and total orders and their significance in mathematical structures.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Order relations Section 6.3 in Jenkyns, Stephenson
Order relations Natural order relations that we know on integer numbers: ? ? What is an abstract definition of an order? What are other examples? What is it good for?
Partial order A relation R is a partial order if it satisfies three properties: (think ) Reflexive: ?,??? Transitive: ?,?,?, (??? ???) ??? Anti-symmetric: ?,?, Equivalently: if ? ? then we cannot have both ??? and ??? ??? ??? ? = ?
Partial order Definition: reflexive, transitive, anti-symmetric Equality relation: xRy if ? ? Is it a partial order? A. Yes B. No
Partial order Definition: reflexive, transitive, anti-symmetric Equality relation: xRy if x=y Is it a partial order? A. Yes B. No
Partial order U={1,2,3,4} Relation: 1 2,1 4,3 4 Is it a partial order? A. Yes B. No
Partial order U={1,2,3,4} Relation: 1 2,1 4,3 4,4 2 Is it a partial order? A. Yes B. No
Total order A partial order is a total order if any pair can be compared That is, ?,?,??? ??? Is the usual order on rational numbers a total order? A. Yes B. No
Total order A partial order is a total order if any pair can be compared That is, ?,?,??? ??? ? = ? ? ?1,?2 (?1,?2) if ?1 ?2 and ?1 ?2 Is it a total order? A. Yes B. No
Total order A partial order is a total order if any pair can be compared That is, ?,?,??? ??? Lexicographic order (on pairs): ? = ? ? ?1,?2 (?1,?2) if ?1< ?2; or ?1= ?2 and ?1 ?2 Is it a total order? A. Yes B. No
Lexicographic order It is often useful to define orders on sequences Example: universe = sequences of integers of length n ? = { ?1, ,??:?1, ,?? ?} Lexicographic order: ?1, ,?? (?1, ,??) If for some 1 ? ?, ?1= ?1, ,?? 1= ?? 1,?? ?? That is, we compare the first element that is different
Orders on sequences Which one of the following is the largest one? A. (1,2,5,10) B. (10,5,2,1) C. (5,100,3,3) D. (10,7,100,1000)
Maximal / maximum elements We don t always have the largest element There are two important definitions Maximum element: an element greater than all other elements. x is the maximum of a set A if ? ?,? ? Maximal element: an element which no other element is greater from. x is a maximal element in a set A if ? ? {?},~(? ?)
Maximal / maximum elements U={1,2,3,4} Relation: 1 2,1 4,3 4 Is there a maximal element? A. Yes B. No
Maximal / maximum elements U={1,2,3,4} Relation: 1 2,1 4,3 4 Is there a maximum element? A. Yes B. No
Maximal / maximum elements There could be multiple maximal elements in a set, but the maximal element (if it exists) must be unique Lets prove it
Maximal / maximum elements There could be multiple maximal elements in a set, but the maximal element (if it exists) must be unique Lets prove it Theorem: a maximum element (if it exists) must be unique Proof: assume towards contradiction there are two maximum elements, x and y. x is maximum ? ? y is maximum ? ? Relation is anti-symmetric: ? ? ? ? ? = ?
Minimal / minimum elements Very similar to maximal/maximum Minimum element: an element smaller than all other elements. x is the minimum of a set A if ? ?,? ? Minimal element: an element which no other element is smaller from. x is a minimal element in a set A if ? ? {?},~(? ?)
Maximum/maximal/minimum/minimal ? = ? ? ?1,?2 (?1,?2) if ?1 ?2 and ?1 ?2 This is NOT lexicographical order Which one is larger? A. (10,20) B. (20,10) C. None
Maximum/maximal/minimum/minimal ? = ? ? ?1,?2 (?1,?2) if ?1 ?2 and ?1 ?2 Does it have A. Maximum element B. Maximal elements, but no maximum element C. Neither
Maximum/maximal/minimum/minimal ? = ? ? ?1,?2 (?1,?2) if ?1 ?2 and ?1 ?2 Does it have A. Minimum element B. Minimal elements, but no minimum element C. Neither
Back to total orders Total order means that we can compare any two elements Theorem: in a total order, a maximal element must be the (unique) maximum Proof: let x be a maximal element. For any ? ?, this means that ~(? ?). But since this is a total order, this implies that ? ?.
Sorting Sorting is a basic primitive used by many algorithms Most sorting algorithms are abstract , in the sense that they can apply to any partial order Na ve sorting on n elements requires comparing all pairs of elements, which takes ~n2 comparisons Fast sorting algorithms (for example, quicksort) can do it using only n log n comparisons This can be proven to be tight!
Next class Knights and knaves
