\documentclass[11pt,twoside]{article} \input{../handouts/macros-course} \usepackage{graphics} \textwidth=6.5in %\topmargin=-.15in %\evensidemargin=0.75in %\oddsidemargin=0.7pt %\newcommand {\pindent} {\hspace*{20pt}} \textheight=9.0in \parskip=12pt plus 2pt minus 2pt \pagestyle{empty} \setlength{\parindent}{0in} \renewcommand{\thefootnote}{\fnsymbol{footnote}} \newcommand{\pagetitle}[1]{\newpage {\bf #1} \hfill L5$-$P. \thepage \\ \vspace{-0.5cm} \hrule \vspace{12mm}} \newcommand{\doublespace}{\addtolength{\baselineskip}{.35\baselineskip}} %\newcommand{\remove}[1]{} \begin{document} \renewcommand{\thepage}{\arabic{page}} \Huge \pagetitle{Relations} \noindent Relationship between elements of sets \noindent Binary relation from a set $A$ to a set $B$ is \\ $R \subseteq A\times B$. \\ Or, $a\sim_R b$ or $aRb$ instead of $(a,b)\in R$\\ \\ A binary relation {\em on} a set $A$ is a subset $R\subseteq A^2$\\ A relation from $A$ to $A$. \noindent An $n$-ary relation $R\subseteq A_1\times A_2 \times\cdots\times A_n$. \pagetitle{Properties of Relations} \noindent {\bf reflexive} --- if for every $a\in A$, $a\sim_R a$.\\ {\bf irreflexive} --- if for every $a \in A$, $a\not\sim_R a$.\\ {\bf symmetric} ---\\ if for every $a,b\in A$, $a\sim_R b$ implies $b\sim_R a$.\\ {\bf antisymmetric} --- if for every $a,b\in A$,\\ $a\sim_R b$ and $b\sim_R a$ implies $a=b$.\\ {\bf transitive} --- if for every $a,b,c\in A$,\\ $a\sim_R b$ and $b\sim_R c$ implies $a\sim_R c$.\\ {\bf asymmetric} --- if for every $a,b\in A$,\\ $a\sim_R b$ implies $\neg(b\sim_R a)$. \noindent ``is living in the same room''\\ $\{students~at~MIT\}\times\{students~at~MIT\}$\\ reflexive, symmetric, transitive Relation on computers,\\ ``are connected (directly) by wire''\\ symmetric but not transitive \newpage ``likes''\\ not symmetric, not antisymmetric, not transitive, not (even) reflexive, not irreflexive, not asymmetric. \noindent $A= \Re^2$ and define $a\sim_R b$ iff $d(a,b)=1$.\\ is only symmetric. \pagetitle{Representation} \noindent Lists, Matrices, Graphs \noindent List all pairs \noindent Relation from \\ $A = \{ 0, 1, 2, 3 \}$ to $\{ a,b,c \}$\\ to be the list:\\ $\{ (0,a), (0, c), (1, c), (2, b), (1,a) \}$. \\ \noindent Reflexivity --- contains all pairs $(a,a)$\\ Symmetry --- contains $(a,b)$ then $(b,a)$\\ Transitivity --- contains $(a,b)$ and $(b,c)$ then also $(a,c)$. \pagetitle{Boolean matrices} Used for finite sets $A$, $B$ \\ Rows for elements of $A$, columns for $B$. \\ $1$ in position if the pair is in the relation,\\ $0$ otherwise. The relation from $\{0,1,2,3\}$ to $\{a,b,c\}$ of our first example is represented by the matrix \[\begin{array} {r|ccc} &a& b& c \\ \hline 0&1& 0& 1\\ 1&1& 0& 1\\ 2&0& 1& 0\\ 3&0& 0& 0\\ \end{array}\] \pagetitle{Boolean matrices, Cont.} The divisibility relation over $\{1,2,\ldots,12\}$ \[\begin{array}{r|cccccccccccc} &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12\\ \hline 1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1\\ 2 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1\\ 3 &0 &0 &1 &0 &0 &1 &0 &0 &1 &0 &0 &1\\ 4 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1\\ 5 &0 &0 &0 &0 &1 &0 &0 &0 &0 &1 &0 &0\\ 6 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &1\\ 7 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0\\ 8 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0\\ 9 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0\\ 10&0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0\\ 11&0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0\\ 12&0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1\\ \end{array}\] \noindent Reflexivity --- major diagonal is all 1\\ Symmetry --- matrix symmetric around the major diagonal \pagetitle{Directed graphs -- Digraphs } \noindent Used for relations where $A=B$ \\ in this case a dot represents an element in $A$ and an arrow for every relation.\\ \begin{center} \mbox{\includegraphics{/b/clivadas/6.042/archive/lectures/figures/dividehasse}} \end{center} \noindent Reflexivity: All nodes have self-loops. \\ Symmetry: all edges are bidirectional. \\ Transitivity: Short-circuits, for any sequence of consecutive arrows, there is a single arrow from the first to the last node. \pagetitle{Composition of Relations} \noindent The {\em composition} of relations $R_1 \subseteq A \times B$ and $R_2 \subseteq B \times C$ is the relation\\ $R_2 \circ R_1 =\{(a,c) \mid (\exists b) ((a,b) \in R_1) \wedge ((b,c) \in R_2)\}$. \noindent Examples: \\ Composition of parent-of relation with itself gives grandparent-of. \\ \\ Composition of relations is equivalent to matrix multiplication, with $+$ replaced by $\vee$ (Boolean or) and $*$ replaced by $\wedge$. \\ \newpage Ex: \\ Let $R_1$ be relation (student in-class class-number): \\ \[\begin{array}{r|ccc} & a& b& c\\ \hline s_0 & 1& 0& 1\\ s_1 & 1& 0& 1\\ s_2 & 0& 1& 0\\ s_3 & 0& 0& 0\\ \end{array} \] Let $R_2$ be relation (class-number in-class-rooms class-room) from $\{ a, b, c \}$ to $\{ d,e,f \}$ given by: \[\begin{array}{r|ccc} & d& e& f\\ \hline a& 1& 1& 1\\ b& 0& 1& 0\\ c& 0& 0& 1\\ \end{array} \] Then $R_2 \circ R_1 = \{ (s_0,d), ... \}$, (student in-class-rooms class-room) that is, \\ \[\begin{array}{r|ccc} & d& e& f\\ \hline S_0 & 1& 1& 1\\ S_1 & 1& 1& 1\\ S_2 & 0& 1& 0\\ S_3 & 0& 0& 0\\ \end{array} \] %\noindent %Same as matrix multiply, using Boolean ops and and or. %\\ Relational composition is associative. \\ Just like matrix multiplication. \\ \noindent Lemma: $R_1 \circ (R_2 \circ R_3) = (R_1 \circ R_2) \circ R_3$ \pagetitle{Closure of Relation} Definition: The \emph{closure} of relation $R$ with respect to property $P$ is the relation $S$ that\\ (i) contains $R$,\\ (ii) has property $P$, and\\ (iii) is contained in \emph{any} relation satisfying (i) and (ii).\\ That is, $S$ is the ``smallest'' relation satisfying (i) and (ii). \noindent Lemma:\\ The {\em reflexive closure} of $R$ is\\ $S=R \cup \{(a,a) \mid a \in A\}$\\ Proof: It contains $R$ and is reflexive by design. Furthermore (by definition) any relation satisfying (i) must contain $R$, and any satisfying (ii) must contain the pairs $(a,a)$, so any relation satisfying both (i) and (ii) must contain $S$. The {\it symmetric closure} of $R$ is $S=R \cup R^{-1}$. \pagetitle{Closure of Relation, Cont.} \noindent Lemma: The {\it transitive closure} of a relation $R$ is that set:\\ $S=\{(a,b) \mid \mbox{there is a path from $a$ to $b$ in $R$}\}$. \noindent proof: $S$ is transitive since if $(a,b)\in S$ and $(b,c)\in S$ then there is a path $(a,b)$ and a path $(b,c)$ in $R$, thus there is a path $(a,c)$ in $R$. Is $S$ minimal?\\ Assume there is a transitive relation $T$ containing $R$ that does not contain $S$. \\ $(a,b)\in S$ but $(a,b)\not\in T$.\\ $\exists$ a path $a,a_1,\cdots,a_k,b$ in $R$ where $(a,b)\not\in T$.\\ Consider the shortest such path so $(a,a_k) \in T$ \\ and $(a_k,b)$ is in $R$, by transitivity of $T$ $(a,b)\in T$. \pagetitle{Computing Transitive Closure} \noindent How to find all paths? \noindent Lemma: $R^n = R \circ R^{n-1} = $\\ $\{(a,b) \mid \mbox{ there is a length $n$ path from $a$ to $b$ in $R$}\}$ \noindent Proof: induction on $n$\\ Base case: $n=1$ then we have $R$\\ Step: assume for $R^n$ and prove for $R^{n+1}$.\\ If there is a path $a_0,\ldots,a_{n+1}$ in $R$ then there is a path $a_0,\ldots,a_n$ in $R$ and\\ a tuple $(a_n,a_{n+1})$ in $R$.\\ By induction $(a_0,a_n)\in R^n$.\\ By definition of composition $(a_0,a_{n+1}) \in R^{n+1}$\\ Still to show that if $(a,b) \in R^{n+1}$ then a path $a_0,\ldots,a_{n+1}$ exists in $R$. \noindent Transitive closure of $R$ is $R \cup R^2 \cup R^3 \cdots$. \noindent We only need the first $n$ elements --- \noindent if there is a path from $A$ to $B$, there is a path of length at most $n$ from $A$ to $B$. \pagetitle{Computing Transitive Closure,\\ Cont.} Consider the shortest path from $a$ to $b$ (well ordering).\\ Suppose $k>n$ then some element of $A$ appears twice in the path\\ (cut the loop) and contradict shortest property.\\ \\ So we don't need infinitely many terms. \\ It is enough to take paths of length $n$, namely $R^1\cup R^2\cdots\cup R^n$. \\ In fact we may stop earlier. \pagetitle{Equivalence relations\\ and partitions} \noindent Definition: An {\em equivalence relation} is a relation that is reflexive, symmetric and transitive. \noindent ``roommates'', ``married to'', ``on same Ethernet hub'' \noindent A {\em partition} of a set $A$ is a collection of subsets $\{A_1,\cdots,A_k\}$ such that any two of them are disjoint (for any $i\neq j$, $A_i\cap A_j=\emptyset$) and such that their union is $A$. \\ \\ That is, every element of $A$ is in exactly one subset. \\ \\ Fix an equivalence relation $R$ on $A$. \\ For an element $a\in A$, let [a] denote the set $\{b\in A | a\sim_R b\}$. \\ We call this set the {\em equivalence class of $a$ under $R$}. We call $a$ a {\em representative} of [a]. \pagetitle{Equivalence relations\\ and partitions, Cont.} \noindent Lemma: The sets $[a]$ for $a\in A$ constitute a partition of $A$. That is, for every $a,b\in A$, either $[a]=[b]$ or $[a]\cap [b]=\emptyset$. \noindent $[a]\neq[b]$\\ Let $c \in [b]-[a]$ (or $c \in [a]-[b]$)\\ $[a]\cap[b]\neq \emptyset$\\ Let $d \in [a]\cap [b]$\\ We aim for a contradiction showing that $c \in [a]$\\ $a\sim_R d$, $d\sim_R b$, $b\sim_R c$\\ $d\sim_R c$\\ $a\sim_R d$ and $d\sim_R c$\\ $a\sim_R c$ \pagetitle{Partitions, Integers modulo $m$} \noindent integers (positive, negative and 0) \noindent Definition: If $a$ and $b$ are integers, then $a=b(mod~m)$ if $m|(a-b)$.\\ or $a=b+km$ for some integer $k$. \noindent Theorem: \\ Equality modulo $m$ is an equivalence relation \noindent Proof\\ reflexive: $m|(a-a)=0$, so $a=a~(mod~m)$\\ symmetric: $a=b+km$ then $b=a+(-k)m$\\ transitive: $a=b+k_1m$, $b=c+k_2m$, so $a=c+k_2m+k_1m$\\ \pagetitle{Fast Exponentiation} \noindent Lemma: If $a=x \pmod m$ and $b=y \pmod m$ then $(a+b) = (x+y) \pmod m$.\\ Proof: $m \mid (a-x)$ and $m \mid (b-y)$ so $m \mid ((a-x)+(b-y)) = (a+b)-(x+y)$, \noindent The same fact can be proven for multiplication. Lemma: If $a=x \pmod m$ and $b=y \pmod m$ then $(a\times b) = (x\times y) \pmod m$.\\ To compute $\bmod~b$ of $x^a$ we may compute $x^2$ replace it with $y= x^2 (\bmod~b)$. Then repeat the same, compute $y^2$ replace with $z= y^2 (\bmod~b)$. Be careful, when $a$ is odd... \pagetitle{Partial Orders} \noindent A type of binary relation (two elements). \noindent A binary relation $R \subseteq A \times A$ is a {\bf partial order\/} if it is reflexive, transitive, and antisymmetric. \noindent reflexive: $a R a$\\ transitive: $a R b \wedge b R c \Rightarrow a R c$\\ antisymmetric: $a R b \wedge b R a \Rightarrow a=b$.\\ i.e., $\forall a \neq b, a R b \Rightarrow \neg b R a$.\\ Means NEVER symmetric! \noindent Ordering relation ($a$ before $b$ then $b$ cannot be before $a$). \noindent Definition: a set $A$ together with a partial order $\preceq$ is called a {\bf poset\/} $(A, \preceq)$.\\ \pagetitle{Partial Orders} \noindent Examples of posets:\\ $A=N, R=\leq$, reflexive, transitive, antisymmetric\\ $A=N, R=\geq$, same.\\ $A=N, R=<$, NOT because not reflexive\\ $A=N, R=|$ (divides), easy to check reflexive, transitive, antisymmetric \pagetitle{Directed Acyclic Graph, DAG} Task graph, $A$ is a set of tasks.\\ $aRb$ means ``{\it b} cannot be done until $a$ is finished''. \setlength{\unitlength}{0.027500in}% %\setlength{\unitlength}{0.012500in}% % \begingroup\makeatletter\ifx\SetFigFont\undefined % extract first six characters in \fmtname \def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}% \expandafter\x\fmtname xxxxxx\relax \def\y{splain}% \ifx\x\y % LaTeX or SliTeX? \gdef\SetFigFont#1#2#3{% \ifnum #1<17\tiny\else \ifnum #1<20\small\else \ifnum #1<24\normalsize\else \ifnum #1<29\large\else \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else \huge\fi\fi\fi\fi\fi\fi \csname #3\endcsname}% \else \gdef\SetFigFont#1#2#3{\begingroup \count@#1\relax \ifnum 25<\count@\count@25\fi \def\x{\endgroup\@setsize\SetFigFont{#2pt}}% \expandafter\x \csname \romannumeral\the\count@ pt\expandafter\endcsname \csname @\romannumeral\the\count@ pt\endcsname \csname #3\endcsname}% \fi \fi\endgroup \begin{picture}(220,75)(20,760) \thinlines \put(165,817){\vector( 0,-1){ 20}} \put(240,817){\vector( 0,-1){ 20}} \put(240,787){\vector( 0,-1){ 20}} \put(165,787){\vector( 0,-1){ 20}} \put( 25,797){\vector( 0,-1){ 25}} \put( 85,797){\vector( 0,-1){ 25}} \put(180,787){\vector( 3,-1){ 51}} \put(178,765){\vector( 1, 0){ 53}} \put(153,795){\vector(-4,-1){88}} \put(155,790){\makebox(0.1111,0.7778){\SetFigFont{5}{6}{rm}.}} \put(153,790){\vector(-2,-1){ 32}} \put( 20,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}left sock}}} \put( 20,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}left shoe}}} \put( 80,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}right sock}}} \put(235,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}shirt}}} \put(155,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}underwear}}} \put(235,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}sweater}}} \put(235,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}jacket}}} \put(155,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}belt}}} \put(155,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}pants}}} \put( 80,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}right shoe}}} \end{picture} \noindent We need to find the reflexive and transitive closure in order to have a partial order (resulting in ``must be done before''). \noindent No cycles! no path that ends where it started.\\ otherwise we cannot get dressed. \noindent directed acyclic graph --- directed graph with no cycles. \noindent The transitive reflexive closure of a DAG is a partial order. \pagetitle{Hasse Diagrams} Hasse diagram for a poset $(A,\preceq)$ is a graph:\\ - whose vertices are the elements of $A$, \\ - whose edges (arrows) represent pairs $(a,b)$,\\ where $a \preceq b$ but $a \neq b$, \\ - that contains no ``transitive edges'', \\ - for which all pairs in $\preceq$ are obtainable by transitivity from edges in the diagram. (we need to remove the pants $\rightarrow$ jacket arrow). \setlength{\unitlength}{0.027500in}% %\setlength{\unitlength}{0.012500in}% % \begingroup\makeatletter\ifx\SetFigFont\undefined % extract first six characters in \fmtname \def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}% \expandafter\x\fmtname xxxxxx\relax \def\y{splain}% \ifx\x\y % LaTeX or SliTeX? \gdef\SetFigFont#1#2#3{% \ifnum #1<17\tiny\else \ifnum #1<20\small\else \ifnum #1<24\normalsize\else \ifnum #1<29\large\else \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else \huge\fi\fi\fi\fi\fi\fi \csname #3\endcsname}% \else \gdef\SetFigFont#1#2#3{\begingroup \count@#1\relax \ifnum 25<\count@\count@25\fi \def\x{\endgroup\@setsize\SetFigFont{#2pt}}% \expandafter\x \csname \romannumeral\the\count@ pt\expandafter\endcsname \csname @\romannumeral\the\count@ pt\endcsname \csname #3\endcsname}% \fi \fi\endgroup \begin{picture}(220,75)(20,760) \thinlines \put(165,817){\vector( 0,-1){ 20}} \put(240,817){\vector( 0,-1){ 20}} \put(240,787){\vector( 0,-1){ 20}} \put(165,787){\vector( 0,-1){ 20}} \put( 25,797){\vector( 0,-1){ 25}} \put( 85,797){\vector( 0,-1){ 25}} \put(180,787){\vector( 3,-1){ 51}} \put(178,765){\vector( 1, 0){ 53}} \put(153,795){\vector(-4,-1){88}} \put(155,790){\makebox(0.1111,0.7778){\SetFigFont{5}{6}{rm}.}} \put(153,790){\vector(-2,-1){ 32}} \put( 20,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}left sock}}} \put( 20,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}left shoe}}} \put( 80,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}right sock}}} \put(235,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}shirt}}} \put(155,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}underwear}}} \put(235,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}sweater}}} \put(235,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}jacket}}} \put(155,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}belt}}} \put(155,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}pants}}} \put( 80,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}right shoe}}} \end{picture} \pagetitle{Partial vs. Total Orders} \noindent $a$ and $b$ are {\bf incomparable\/} if neither $a \preceq b$ nor $b \preceq a$. \noindent the shoes in our example \noindent $a$ and $b$ are {\bf comparable\/} if $a \preceq b$ or $b \preceq a$ \noindent A poset $(S, \preceq)$ is {\bf totally ordered\/} if $(\forall a,b \in S) [ a \preceq b \vee b \preceq a ]$. Examples:\\ $S=N, \preceq = \leq$\\ $S=N, \preceq = |$, NOT because neither $3|5$ nor $5|3$\\ $S=P(N), \preceq = \subseteq,$ NOT because neither $\{3\} \subseteq \{5\}$ nor $\{5\} \subseteq \{3\}$\\ Lexicographic order on pairs of natural numbers, defined by:\\ $(a_1,a_2) \preceq (b_1,b_2)$ if and only if either $a_1 < b_1$, or else $a_1 = b_1$ and $a_2 \leq b_2$. \noindent The Hasse diagram of a total order looks like a line. \pagetitle{Topological Sorting} \noindent Definition: A {\bf topological sort\/} of a finite poset $(A, \preceq)$ is a total ordering of all the elements of $A$, $a_1, a_2, \cdots, a_n$ \\ in such a way that $\forall i < j$, either $a_i \prec a_j$ or $a_i$ and $a_j$ are incomparable in $(A, \preceq)$ (equivalently, it is not the case that $a_j \prec a_i$). \noindent Lemma: Every {\it finite }poset $(A,\preceq)$ has a minimal element. \noindent By induction on the number of elements.\\ $n=1$ is clear.\\ Suppose it is true for all size-$n$ posets.\\ Remove an element $a$ from the $n+1$ poset.\\ We still have a poset, use induction hypothesis to have the minimal element $b$.\\ If $a \not\preceq b$ then $b$ is a minimal element of the poset.\\ Otherwise, $a$ is the minimal element of the poset:\\ assume that there is $c \preceq a$ then we have $c \preceq b$ which contradicts the choice of $b$. \pagetitle{Parallel Task Scheduling} \noindent Given a finite poset of tasks, how long does it take to do them all?\\ One time unit for a task,\\ Unlimited number of processors. \noindent Definition: A {\bf chain\/} in a poset is a sequence of elements of the domain, each of which is smaller than the next in the partial order ($\preceq$ and $\neq$). \noindent A longest chain is also known as a {\em critical path}. \\ Let $t$ be the length of the longest chain. \pagetitle{Chains of Posets} Theorem: Given any finite poset $(A, \preceq)$ for which the longest chain has length $t$, it is possible to partition $A$ into $t$ subsets, $A_1, A_2, \cdots, A_t$ such that $(\forall i \in [1,t]) (\forall a \in A_i) (\forall b \preceq a, b \neq a) [ b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} ]$. \noindent proof: Put each $a$ in set $A_i$, where $i$ is the length of the longest chain ending at $a$.\\ \noindent Need to show $(\forall i) ( \forall a \in A_i)$ \\ $(\forall b \preceq a, b \neq q) [ b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} ]$. \\ \\ Proof by contradiction: \\ If $b \not\in A_1 \cup A_2 \cup \cdots \cup A_{i-1}$ then there is a path of length $>i-1$ ending in $b$, \\ which means there is a path of length $>i$ ending in $a$, \\ which means $a \not \in A_i$. \noindent We can schedule the tasks in $t$ time units. \pagetitle{Antichains } \noindent An {\bf antichain\/} is a set of incomparable elements. \noindent (Dilworth) $\forall t$, every poset with $n$ elements must have a chain of size $ > t$ or an antichain of size $\geq \frac{n}{t}$. \noindent Proof: Assume there is no chain of length $> t$. \\ So, longest chain has length $\leq t$. \\ Then by previous result, the $n$ elements can be partitioned into $\leq t$ antichains. \\ (Cannot assume exactly $t$, since could have some empty.) \\ So there is an antichain with $\geq \frac{n}{t}$ elements. \\ As needed. \end{document}