!"!#"$%&$&lec4W.1Albert R Meyer, Feb. 24, 2010 Mathematics for Computer ScienceMIT 6.042J/18.062JPartial Orders lec4W.3Albert R Meyer, Feb. 24, 2010 {1}{1,3,5,15}{1,2}{1,3} {1,5}{1,2,5,10}{1,2,3,5,10,15,30}proper subset relationlec4W.4Albert R Meyer, Feb. 24, 2010 meansB has everything that A hasand more:proper subset relationA BBAlec4W.5Albert R Meyer, Feb. 24, 2010 properties of A B implies B Aasymmetrylec4W.6Albert R Meyer, Feb. 24, 2010 binary relation R on set Ais asymmetric:aRb impliesNOT(bRa) for all a,b A is asymmetriclec4W.7Albert R Meyer, Feb. 24, 2010 properties of [A B and B C] implies A C transitivity!"!#"$%&!&lec4W.8Albert R Meyer, Feb. 24, 2010 binary relation R on set Ais transitive:aRb and bRc implies aRc for all a,b,c A is transitivelec4W.9Albert R Meyer, Feb. 24, 2010 strict partial orders transitive & asymmetriclec4W.11Albert R Meyer, Feb. 24, 2010 Subject Prerequisites subjectc is a directprerequisite for subject dcdlec4W.12Albert R Meyer, Feb. 24, 2010 Direct Prerequisites 18.016.042 6.046 6.840 lec4W.13Albert R Meyer, Feb. 24, 2010 18.01 is indirect prerequisiteof 6.042 and 6.840 18.01 6.042 6.046 6.840 Indirect Prerequisites lec4W.14Albert R Meyer, Feb. 24, 2010 another indirect prereq18.01 6.042 6.046 6.840 Indirect Prerequisites!"!#"$%&#&lec4W.15Albert R Meyer, Feb. 24, 2010 3 more indirect prerequisites( is a special case of )18.01 6.042 6.046 6.840 Indirect Prerequisites lec4W.16Albert R Meyer, Feb. 24, 2010 If subjects c, d are mutualprereq’scd and dcthen no one can graduate! Comm. on Curricula ensures: if cd, then NOT(d c)asymmetryIndirect Prerequisites lec4W.17Albert R Meyer, Feb. 24, 2010 better be a strict partial order on MIT subjectsIndirect Prerequisites lec4W.18Albert R Meyer, Feb. 24, 2010 $&!&$%&&&&&&&#& &’&&&&&&&&&&&&&$’&#%&partial order: properly divides on {1,2,3,5,10,15,30} lec4W.19Albert R Meyer, Feb. 24, 2010 same shape as example lec4W.20Albert R Meyer, Feb. 24, 2010 proper subset {1}{1,3,5,15}{1,2}{1,3} {1,5}{1,2,5,10}{1,2,3,5,10,15,30}!"!#"$%&(&lec4W.21Albert R Meyer, Feb. 24, 2010 $&!&$%&&&&&&&#& &’&&&&&&&&&&&&&$’&#%&partial order: properly divides on {1,2,3,5,10,15,30} lec4W.22Albert R Meyer, Feb. 24, 2010 same shape as example isomorphiclec4W.23Albert R Meyer, Feb. 24, 2010 p.o. has same shape as Theorem:Every strict partial order is isomorphic to a collection of subsets partially ordered by .lec4W.24Albert R Meyer, Feb. 24, 2010 $&)$*&subsets from divides !&)$+!*&#&)$+#*&’&)$+’*&$’)$+#+’+$’*&$%&)$+!+’+$%*&#%&)$+!+#+’+$%+$’+#%*&lec4W.25Albert R Meyer, Feb. 24, 2010 proof: map each element, a,to the set of elements below it a b A| bRa OR b=a{}p.o. has same shape as lec4W.26Albert R Meyer, Feb. 24, 2010 weak partial orders same as a strict partialorder R, except that aRa always holds reflexivity!"!#"$%&’&lec4W.27Albert R Meyer, Feb. 24, 2010 weak partial orders same as a strict partialorder R, except that aRa always holdsyexamples:• is weak p.o. on sets • is weak p.o. on Rlec4W.28Albert R Meyer, Feb. 24, 2010 Reflexivityrelation R on set Ais reflexive iffaRa for all a Alec4W.29Albert R Meyer, Feb. 24, 2010 binary relation R on set Ais antisymmetric iff it is asymmetric except foraRa case. antisymmetrylec4W.33Albert R Meyer, Feb. 24, 2010 weak partial orders transitiveantisymmetric& reflexive lec4W.34Albert R Meyer, Feb. 24, 2010 Team Problems Problems13MIT OpenCourseWare http://ocw.mit.edu 6.042J / 18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...