\documentclass[12pt]{article}
\usepackage{latex-macros/course}
%\setlength{\topmargin}{0.5in}
%\setlength{\headsep}{1cm}
\setlength{\itemsep}{0 cm}
%\setlength{\topsep}{0 cm}

\begin{document}
\paper{qua1}{Quiz 1 Appendix}{Appendix}

\tableofcontents
\newpage

\section{Induction}

\begin{axiom*}[Induction]
\Rule{P(0), \quad \forall m \in \naturals\ P(m) \implies P(m+1)}
{\forall n \in \naturals\; P(n).}
\end{axiom*}

\begin{axiom*}[Strong Induction]
\Rule{P(0), \quad \forall n \in \naturals\, \forall m \le n\ P(m) \implies
P(m+1)}
{\forall n \in \naturals\; P(n)}
\end{axiom*}

\begin{axiom*}[Least Number Principle]
Every nonempty subset, $S \subseteq \naturals$, has a smallest element.
\end{axiom*}

\section{Relations}
\subsection{Equivalence Relations}

A binary relation, $R$, on a set $A$ is
\begin{itemize}
\item\emph{reflexive} if for every $a \in A$, $aRa$.

\item\emph{symmetric} if for every $a,b\in A$, $aRb$ implies  $bRa$.

\item\emph{transitive} if for every $a,b,c\in A$, $aRb$ and $bRc$ implies
$a R c$.
\end{itemize}

$R$ is an \emph{equivalence relation} iff it is reflexive, symmetric and
transitive.

\subsection{Partial Order}
A binary relation, $R$, on a set $A$ is
\begin{itemize}
\item\emph{irreflexive} if for every $a \in A$, $\neg(aRa)$.
\item\emph{asymmetric} if for every $a,b\in A$, $aRb$ implies $\neg(bRa)$.
\item \emph{antisymmetric} if for every $a,b \in A$, [$a\neq b \land
aRb$] implies $\neg(bRa)$.
\item a \emph{weak partial order} if it is reflexive, transitive, and antisymmetric.
\item a \emph{strict partial order} if it is transitive and asymmetric.
\item a \emph{partial order} if it is transitive and antisymmetric.
\item a \emph{total order} if it is a partial order and for every
$a \neq b \in A$ either $aRb$ or $bRa$.

\item $a$ is a \emph{minim\textbf{um} element} of $A$ iff $\forall b\in A\
(aRb \lor a=b)$

\item $a$ is a \emph{minim\textbf{al} element} of $A$ if $\neg\exists b\in
A\ (b R a \land b\neq a)$
\item \emph{maximum} and \emph{maximal} are defined similarly
\item  a subset of $A$ is a \emph{chain} iff it is totally ordered by $R$.
\item elements $a_1,a_2 \in A$ are \emph{incomparable} iff neither
$a_1Ra_2$ nor $a_2Ra_1$ holds.
\item a subset of $A$ is an \emph{antichain} iff its elements are
pairwise incomparable.
\end{itemize}

A \emph{topological sort} of a partial order, $R$, is a total ordering,
$T$, on the domain of $R$ such that $a_1Ra_2$ implies $a_1Ta_2$ for all
$a_1,a_2 \in A$.

\begin{theorem*}
If the longest chain in a partial order is of finite size $t$, then the
domain can be partitioned into $t$ antichains.
\end{theorem*}

\begin{theorem*}[Dilworth]
For all $t$, every partial order with domain of size $n$ must have either
a chain of size greater than $t$ or an antichain of size at least $n / t$.
\end{theorem*}

\subsection{Operations}

If $R$ is a relation on $A \times B$, then the \emph{inverse of $R$} is
the relation on $B\times A$ given by 
\[R^{-1} = \set{(b,a) \mid (a,b) \in R}.\]

The \emph{composition} of relations $R_1 \subseteq A \times B$ and $R_2
\subseteq B \times C$ is the relation
\begin{displaymath}
  R_2 \circ R_1 =\{(a,c) \mid
  (\exists b) ((a,b) \in R_1) \wedge ((b,c) \in R_2)\}.
\end{displaymath}

A \emph{path} in a relation $R$ is a sequence $a_0,\dots,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.


Let $R$ be a relation on the set $A$ and $n \in \naturals$.  Then
\[
R^n =
\begin{cases}
R & \mathrm{if}\ n=1\\
R^{n-1} \circ R & \mathrm{if}\ n>1
\end{cases}
\]

\begin{lemma*}
$R^n = \{(a,b) \mid 
\mbox{ there is a length $n$ path from $a$ to $b$ in $R$}\}$.
\end{lemma*}

\[
R^* = \bigcup_{n=1}^{\infty} R^n
\]

\iffalse

\subsection{Closure}
The \emph{closure} of relation $R$ with respect to property $P$ is the relation
$S$ that 
\begin{enumerate}
\item\label{contains} contains $R$, 
\item\label{P} has property $P$, and 
\item  is contained in \emph{any} relation satisfying (\ref{contains}) and
(\ref{P}).  That is, $S$ is the ``smallest''relation satisfying
(\ref{contains}) and (\ref{P}).
\end{enumerate}

\begin{lemma*}
Let $R$ be a relation on the set $A$.
\begin{itemize}
\item The reflexive closure of $R$ is $S=R \cup \set{(a,a), \forall a \in A}$.\\
\item The symmetric closure of $R$ is $S=R \union R^{-1}$.
\item The transitive closure of a relation $R$ is the set 
\[
S = \{(a,b) \in A\times A 
\mbox{ given there is a path from $a$ to $b$ in $R$}\}.
\]
\end{itemize}
\end{lemma*}

The \emph{reflexive and transitive closure} (also called the \emph {connectivity
relation}) of $R$ is 
\[
R^* = \{(a,b) \in A\times A \mid 
\mbox{ there exists a path from $a$ to $b$ in $R$}\}.
\] or, equivalently, $R^* = \bigcup_{n=1}^\infty R^n.$ 

\begin{lemma*}
If $R$ is a reflexive relation on $A$ then $R^* = R^{\card{A}} $.
\end{lemma*}
\fi

\section{Graphs}

A {\em simple graph} is a pair of sets $(V, E)$, where $V$ is a
nonempty set whose elements are called {\em vertices} and $E$ is a set
of 2-element subsets of $V$ called {\em edges}.

A \emph{directed graph} or \emph{digraph} is a pair of sets $(V, E)$,
where $V$ is a nonempty set whose elements are called {\em vertices}
and $E$ is a subset of $V \times V$ whose elements are called {\em
(directed) edges}.

\begin{theorem*}
The sum of the degrees of the vertices in a simple graph equals twice the
number of edges.
\end{theorem*}


\iffalse
\begin{theorem*}[Handshake]
In every graph, there are an even number of vertices of odd degree.
\end{theorem*}
\fi

An \emph{Euler tour} of an undirected graph $G$ is a cycle that
traverses every edge of $G$ exactly once.

\begin{theorem*}
An undirected graph $G$ has an Euler tour iff $G$ is connected and every
vertex has even degree.
\end{theorem*}

A \emph{Hamiltonian cycle} is a cycle that traverses every vertex in a
graph exactly once.  Similarly, a \emph{Hamiltonian path} is a path
that visits every vertex exactly once.

A graph is \emph{planar} if it can be drawn in a plane so that no
edges cross.

\begin{theorem*}
A graph is planar if and only if it has no subgraph homeomorphic to
$K_{3,3}$ or $K_5$.
\end{theorem*}

\subsection{Common Graphs}

The \emph{empty graph} or \emph{anticlique} on $n$ vertices, 
is the graph $A_n = (\{v_1, v_2, \dots, v_n\},\emptyset)$. 

The \emph{line graph} on $n$ vertices is the graph 
$L_n = (\{v_1, v_2, \dots, v_n\}, \{\{v_1,v_2\}, \{v_2,v_3\}, \dots,
\{v_{n-1},v_n\}\})$.

The \emph{cycle} on $n$ vertices $C_n$ is the $L_n$ plus the edge $\{v_n,v_1\}$.

The \emph{wheel} on $n \geq 4$ vertices $W_n$ is the graph consisting of
$C_{n-1}$ plus an additional vertex connected to every other vertex.

The \emph{complete graph} or \emph{clique} on $n$ vertices, $K_n$
has an edge between every pair of vertices. 

\subsection{Graph Coloring}

The minimum number of colors needed to color the vertices of a
graph $G$ so that no two adjacent vertices are the same is called the
\emph{chromatic number} and is written $\chi(G)$. 

\begin{lemma*}
A graph with maximum degree $d_{max}$ can be colored with $d_{max}$ + 1 colors.
\end{lemma*}

\subsection{Trees}

A \emph{tree} is any simple graph $G=(V,E)$, such that any of these (equivalent)
conditions hold:
\begin{itemize}
\item $G$ is connected and $\card{E} = \card{V}-1$.
\item $G$ is connected, but removing any edge from $G$ leaves a
      disconnected graph.
\item $G$ is connected and acyclic.
\item There is a unique simple path between any two distinct vertices of $G$.
\end{itemize}

A rooted tree is called \emph{finite-path} iff it has no infinite
simple paths away from the root.


\section{State Machines}

A \emph{state machine} has three parts:
\begin{enumerate}
\item a nonempty set, $Q$, whose elements are called \emph{states},
\item a nonempty subset $Q_0 \subseteq Q$, called the set of \emph{start states},
\item a binary relation, $\delta$, on $Q$, called the \emph{transition
relation}.
\end{enumerate}

An \emph{invariant} is a predicate $P$ such that for every transition
$q \rightarrow r$, $P(q)$ implies $P(r)$.

% An \emph{invariant} for a state machine is a predicate, $P$, on states,
% such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$
% (that is, $(q,r)\in \delta)$ for some state, $r$, then $P(r)$ holds.

\begin{theorem*}[Invariant Theorem]
Let $P$ be an invariant predicate for a state machine.  If $P$ holds
for all start states, then $P$ holds for all reachable states.
\end{theorem*}

If $\preceq$ is a reflexive partial order with domain, $A$, then a derived
variable $f : Q \to A$ is  \emph{weakly decreasing} iff
\[
q \rightarrow r \qimplies f(q) \preceq f(r),
\]
and is \emph{strictly decreasing} iff
\[
q \rightarrow r \text{  implies  } f(q) \prec f(r),
\]
where $a \prec b$ means $a \preceq b \land a \neq b$.

\begin{theorem*}
If $f : Q \to \naturals$ is a strictly decreasing derived variable of a
state machine, then the length of any execution starting at a start state
$q$ is at most $f(q)$.
\end{theorem*}

\subsection{Well-founded Partial Orders}

\def\lexle{\mathrel{\preceq_{\text{lex}}}}
\def\lex<{\mathrel{\prec_{\text{lex}}}}
\def\coordle{\mathrel{\preceq_{\text{c}}}}
\def\coord<{\mathrel{\prec_{\text{c}}}}

If $\preceq_1$ and $\preceq_2$ are partial orders, then the
\emph{lexicographic partial order}, $\lexle$, and the \emph{coordinatewise
partial order}, $\coordle$, on $\domain{\preceq_1}
\cross \domain{\preceq_2}$ are defined by the conditions that
\begin{eqnarray*}
(p_1,p_2) \lexle (q_1,q_2) &\eqdef& p_1 \prec_1 q_1\text{ or }(p_1=q_1
\land p_2 \preceq_2 q_2),\\
(p_1,p_2) \coordle (q_1,q_2) & \eqdef & (p_1 \preceq_1 q_1 \land p_2
\preceq_2 q_2).
\end{eqnarray*}

A partial order, $\preceq$, is \emph{well-founded} iff every nonempty
subset of the domain has a \emph{minimal element}.

\begin{lemma*}
If $\preceq_1$ and $\preceq_2$ are partial orders, then
\begin{enumerate}

\item so are $\lexle$ and $\coordle$.  Moreover,

\item if $\preceq_1$ and $\preceq_2$ are both
well-founded, then so are $\lexle$ and $\coordle$, and

\item if $preceq_1$ and $preceq_2$ are both totally
ordered, then so is $\lexle$.
\end{enumerate}
\end{lemma*}

\begin{lemma*}
A poset is well-founded iff it has no infinite strictly decreasing chain.
\end{lemma*}

\begin{theorem*}
\textbf{Fundamental Theorem for two-person games of perfect information}:
For games in which every play is finite and ends in win or lose, there is
a winning strategy for one of the players.
\end{theorem*}

\end{document}
