DOC PREVIEW
MIT 6 042J - Partial Orders

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 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 21 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 21 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 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 7 Partial Orders Partial orders are a kind of binary relation that come up a lot. The familiar ≤ order on numbers is a partial order, but so is the containment relation on sets and the divisibility relation on integers. Partial orders have particular importance in computer science because they capture key concepts used, for example, in solving task scheduling problems, ana-lyzing concurrency control, and proving program termination. 7.1 Axioms for Partial Orders The prerequisite structure among MIT subjects provides a nice illustration of par-tial orders. Here is a table indicating some of the prerequisites of subjects in the the Course 6 program of Spring ’07: Direct Prerequisites Subject 18.01 6.042 18.01 18.02 18.01 18.03 8.01 8.02 6.001 6.034 6.042 6.046 18.03, 8.02 6.002 6.001, 6.002 6.004 6.001, 6.002 6.003 6.004 6.033 6.033 6.857 6.046 6.840 Since 18.01 is a direct prerequisite for 6.042, a student must take 18.01 before 6.042. Also, 6.042 is a direct prerequisite for 6.046, so in fact, a student has to take both 18.01 and 6.042 before taking 6.046. So 18.01 is also really a prerequisite for 109110 CHAPTER 7. PARTIAL ORDERS 6.046, though an implicit or indirect one; we’ll indicate this by writing 18.01 6.046.→ This prerequisite relation has a basic property known as transitivity: if subject a is an indirect prerequisite of subject b, and b is an indirect prerequisite of subject c, then a is also an indirect prerequisite of c. In this table, a longest sequence of prerequisites is 18.01 18.03 6.002 6.004 6.033 6.857→ → → → → so a student would need at least six terms to work through this sequence of sub-jects. But it would take a lot longer to complete a Course 6 major if the direct prerequisites led to a situation1 where two subjects turned out to be prerequisites of each other! So another crucial property of the prerequisite relation is that if a b, then it is not the case that b a. This property is called asymmetry. → →Another basic example of a partial order is the subset relation, ⊆, on sets. In fact, we’ll see that every partial order can be represented by the subset relation. Definition 7.1.1. A binary relation, R, on a set A is: • transitive iff [a R b and b R c] IMPLIES a R c for every a, b, c ∈ A, • asymmetric iff a R b IMPLIES NOT(b R a) for all a, b ∈ A, • a strict partial order iff it is transitive and asymmetric. So the prerequisite relation, , on subjects in the MIT catalogue is a strict par-→tial order. More familiar examples of strict partial orders are the relation, <, on real numbers, and the proper subset relation, ⊂, on sets. The subset relation, ⊆, on sets and ≤ relation on numbers are examples of re-flexive relations in which each element is related to itself. Reflexive partial orders are called weak partial orders. Since asymmetry is incompatible with reflexivity, the asymmetry property in weak partial orders is relaxed so it applies only to two different elements. This relaxation of the asymmetry is called antisymmetry: Definition 7.1.2. A binary relation, R, on a set A, is • reflexive iff a R a for all a ∈ A, • antisymmetric iff a R b IMPLIES NOT(b R a) for all a =� b ∈ A, • a weak partial order iff it is transitive, reflexive and antisymmetric. Some authors define partial orders to be what we call weak partial orders, but we’ll use the phrase “partial order” to mean either a weak or strict one. For weak partial orders in general, we often write an ordering-style symbol like � or � instead of a letter symbol like R. (General relations are usually denoted 1MIT’s Committee on Curricula has the responsibility of watching out for such bugs that might creep into departmental requirements.7.2. REPRESENTING PARTIAL ORDERS BY SET CONTAINMENT 111 by a letter like R instead of a cryptic squiggly symbol, so � is kind of like the musical performer/composer Prince, who redefined the spelling of his name to be his own squiggly symbol. A few years ago he gave up and went back to the spelling “Prince.”) Likewise, we generally use � or � to indicate a strict partial order. Two more examples of partial orders are worth mentioning: Example 7.1.3. Let A be some family of sets and define a R b iff a ⊃ b. Then R is a strict partial order. For integers, m, n we write m | n to mean that m divides n, namely, there is an integer, k, such that n = km. Example 7.1.4. The divides relation is a weak partial order on the nonnegative in-tegers. 7.2 Representing Partial Orders by Set Containment Axioms can be a great way to abstract and reason about important properties of objects, but it helps to have a clear picture of the things that satisfy the axioms. We’ll show that every partial order can be pictured as a collection of sets related by containment. That is, every partial order has the “same shape” as such a collection. The technical word for “same shape” is “isomorphic.” Definition 7.2.1. A binary relation, R, on a set, A, is isomorphic to a relation, S, on a set D iff there is a relation-preserving bijection from A to D. That is, there is bijection f : A → D, such that for all a, a� ∈ A, a R a� iff f(a) S f(a�). Theorem 7.2.2. Every weak partial order, �, is isomorphic to the subset relation, on a collection of sets. To picture a partial order, �, on a set, A, as a collection of sets, we simply represent each element A by the set of elements that are � to that element, that is, a ←→ {b ∈ A | b � a} . For example, if � is the divisibility relation on the set of integers, {1, 3, 4, 6, 8, 12}, then we represent each of these integers by the set of integers in A that divides it. So 1 ←→ {1}3 ←→ {1, 3}4 ←→ {1, 4}6 ←→ {1, 3, 6}8 ←→ {1, 4, 8}12 ←→ {1, 3, 4, 6, 12}112 CHAPTER 7. PARTIAL ORDERS So, the fact that 3 | 12 corresponds to the fact that {1, 3} ⊆ {1, 3, 4, 6, 12}. In this way we have completely captured the weak partial order � by the subset relation on the corresponding sets. Formally, we have Lemma 7.2.3. Let � be a weak partial order on a set, A. Then � is isomorphic to the subset relation on the collection of inverse images of elements a ∈ A under the � relation. We leave the proof to Problem 7.3. Essentially the same construction shows that strict


View Full Document

MIT 6 042J - Partial Orders

Documents in this Course
Counting

Counting

55 pages

Graphs

Graphs

19 pages

Proofs

Proofs

14 pages

Proofs

Proofs

18 pages

Proofs

Proofs

18 pages

Quiz 1

Quiz 1

9 pages

Quiz 2

Quiz 2

11 pages

Load more
Download Partial Orders
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 Partial Orders 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 Partial Orders 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?