\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.5in
\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{Lecture Overview}

Relations\\
\\
Operations on Relations\\
\\
Equivalence Relations and Partitions\\
\\
Partial Orders


\pagetitle{Relations}

\noindent
Relationship between elements of sets

\noindent
Binary relation {\em 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$.\\
\\
\\
The relation ``is taking a class'' as a subset of
$\{students~at~MIT\}\times\{classes~at~MIT\}$.\\
A relation from students to classes\\
\\
\\

%\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$.\\
``is living in the same room''\\
$\{students~at~MIT\}\times\{students~at~MIT\}$

{\bf irreflexive} --- if for every $a \in A$, $a\not\sim_R a$.\\
``parent'',
on the set \{people\}

{\bf transitive} ---
if for every $a,b,c\in A$,\\ $a\sim_R b$ and $b\sim_R c$
implies $a\sim_R c$.\\
``can drive from first to second city''

{\bf symmetric} ---\\
if for every $a,b\in A$, $a\sim_R b$ implies $b\sim_R a$.\\
``is living in the same room''

{\bf antisymmetric} ---
if for every $a,b\in A$,\\ $a\sim_R b$ and
$b\sim_R a$ implies $a=b$.\\
$A=\naturals$ and $a\sim_R b$ iff $a\le b$.

{\bf asymmetric} ---
if for every $a,b\in A$,\\ $a\sim_R b$ implies
$\neg(b\sim_R a)$.\\
$A=\naturals$ and $a\sim_R b$ iff $a < b$.


\pagetitle{Properties of Relations, Ex.}

Relation on computers,\\
``are connected (directly) by wire''\\
symmetric but not transitive\\

\noindent
$A= \Re^2$ and define $a\sim_R b$ iff $d(a,b)=1$.\\
is only symmetric.\\

\noindent
``likes''\\
not symmetric, not antisymmetric, not transitive, not (even) reflexive, 
not irreflexive, not asymmetric.


\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 
$\{ (0,a), (0, c), (1, c), (2, b), (1,a) \}$. \\
from $\{0,1,2,3\}$ to $\{a,b,c\}$ 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{/a/class/6.042/spring00/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{Paths in Directed graphs }

\begin{center}
\mbox{\includegraphics{/a/class/6.042/spring00/archive/lectures/figures/dividehasse}}
\end{center}


\Huge
A \emph{path} in a relation $R$ is a sequence $a_0,\ldots,a_k$ with
$k \ge 0$ such that $(a_i,a_{i+1}) \in R$ for every $i < k$.  We
call $k$ the \emph{length} of the path.


\pagetitle{Operations on Relations,\\ Inverse}

If $R$ is a relation on $A \times B$, then $R^{-1}$ is a relation on
$B\times A$ given by $R^{-1} = \set{(b,a) \mid (a,b) \in R}$.  It's
just the relation ``turned backwards.''

Inverse of ``parent-of'' is ``child-of.''


\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. 

\[\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}
\]
Multiply by:
\[\begin{array}{r|ccc}
& d&  e&  f\\
\hline
a& 1&  1&  1\\
b& 0&  1&  0\\
c& 0&  0&  1\\
\end{array}
\]

\pagetitle{Composition of Relations $R^k$}

Useful Lemma: $\forall k \geq 1$ $R^k=$\\
$\{(a,b) \mid \mbox{ there is a length $k$ path from $a$ to $b$ in $R$}\}$

``Proof'' by example, consider the relation $R$,
$(a,b)$, $(b,d)$, $(d,e)$ or:

\[\begin{array}{r|ccccc}
  &a  &b  &c  &d  &e \\
\hline
a &0  &1  &0  &0  &0 \\
b &0  &0  &0  &1  &0 \\
c &0  &0  &0  &0  &0 \\
d &0  &0  &0  &0  &1 \\
e &0  &0  &0  &0  &0 \\
\end{array}\]

Or, $a$ $\rightarrow$ $b$ $\rightarrow$ $d$ $\rightarrow$ $e$ and an additional
node $c$

So, $R^2$ (according to the relation composition definition) will be\\
(Note that matrix multiplication gives\\
1st line and 4th column results in 1\\
2nd line and 5th column results in 1)

\[\begin{array}{r|ccccc}
  &a  &b  &c  &d  &e  \\
\hline
a &0  &0  &0  &1  &0  \\
b &0  &0  &0  &0  &1  \\
c &0  &0  &0  &0  &0  \\
d &0  &0  &0  &0  &0  \\
e &0  &0  &0  &0  &0  \\
\end{array}\]

\noindent
Proof: induction on $k$\\
Base case: $k=1$ then we have $R$\\
Step: assume for $R^k$ and prove for $R^{k+1}$.\\
If there is a path $a_0,\ldots,a_{k+1}$ in $R$ then
there is a path $a_0,\ldots,a_k$ in $R$ and\\
a tuple $(a_k,a_{k+1})$ in $R$.\\
By induction $(a_0,a_k)\in R^k$.\\
By definition of composition of $R^{k} \circ R$
$(a_0,a_{k+1}) \in R^{k+1}$.\\
Still to show that if $(a,b) \in R^{k+1}$ then a path
$a_0,\ldots,a_{k+1}$ exists in $R$...

\pagetitle{Closure of Relation\\ Reflexive Closure}

The {\em reflexive closure} of $R$ is\\ $S=R \cup \{(a,a) \mid a \in A\}$\\
\[\begin{array}{r|ccccc}
  &a  &b  &c  &d  &e  \\
\hline
a &0  &1  &1  &0  &0  \\
b &0  &0  &0  &1  &0  \\
c &0  &0  &0  &0  &0  \\
d &0  &0  &0  &0  &1  \\
e &0  &0  &0  &0  &0  \\
\end{array}\]

is changed to:
\[\begin{array}{r|ccccc}
  &a  &b  &c  &d  &e  \\
\hline
a &1  &1  &1  &0  &0  \\
b &0  &1  &0  &1  &0  \\
c &0  &0  &1  &0  &0  \\
d &0  &0  &0  &1  &1  \\
e &0  &0  &0  &0  &1  \\
\end{array}\]


\pagetitle{Closure of Relation\\ Symmetric Closure}
The {\it symmetric closure} of $R$ is $S=R \cup  R^{-1}$.\\
\[\begin{array}{r|ccccc}
  &a  &b  &c  &d  &e  \\
\hline
a &0  &1  &1  &0  &0  \\
b &0  &0  &0  &1  &0  \\
c &0  &0  &0  &0  &0  \\
d &0  &0  &0  &0  &1  \\
e &0  &0  &0  &0  &0  \\
\end{array}\]

Is changed to:
\[\begin{array}{r|ccccc}
  &a  &b  &c  &d  &e  \\
\hline
a &0  &1  &1  &0  &0  \\
b &1  &0  &0  &1  &0  \\
c &1  &0  &0  &0  &0  \\
d &0  &1  &0  &0  &1  \\
e &0  &0  &0  &1  &0  \\
\end{array}\]


\pagetitle{Closure of Relation\\ Transitive Closure}
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$}\}$.

\[\begin{array}{r|ccccc}
  &a  &b  &c  &d  &e  \\
\hline
a &0  &1  &0  &0  &0  \\
b &0  &0  &0  &1  &0  \\
c &0  &0  &0  &0  &0  \\
d &0  &0  &0  &0  &1  \\
e &0  &0  &0  &0  &0  \\
\end{array}\]

Or,\\
$a$ $\rightarrow$ $b$ $\rightarrow$ $d$ $\rightarrow$ $e$ and an additional
node $c$

Is changed to:
\[\begin{array}{r|ccccc}
  &a  &b  &c  &d  &e  \\
\hline
a &0  &1  &0  &1  &1  \\
b &0  &0  &0  &1  &1  \\
c &0  &0  &0  &0  &0  \\
d &0  &0  &0  &0  &1  \\
e &0  &0  &0  &0  &0  \\
\end{array}\]

\pagetitle{Closure of Relation, Cont.}
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).
So we need to show:

\noindent
Lemma:
The {\em reflexive closure} of $R$ is\\ $S=R \cup \{(a,a) \mid a \in A\}$

Lemma:
The {\it symmetric closure} of $R$ is $S=R \cup  R^{-1}$.

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$}\}$.

We may show that \emph{any} relation satisfying (i) and (ii)
will have at least the ones in our choice of closure matrix.

\pagetitle{Computing Transitive Closure}

\noindent
Recall $R^i$, $i \geq 1$  implies there is a path of length $i$.

\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 {\rm 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$.

\end{document}

