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

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{areflexive} if for every $a \in A$, $\neg(aRa)$.
\item\emph{asymmetric} if for every $a,b\in A$, $aRb$ implies $\neg(bRa)$.
\item \emph{anti-symmetric} if for every $a,b \in A$ $aRb$ and $bRa$ implies $a =
b$.
\item a \emph{partial order} if it is reflexive, transitive and
anti-symmetric.  
\item a \emph{strict partial order} if it is areflexive and transitive.
\item a \emph{total order} if it is a partial order and for every
$a \neq b \in A$ either $aRb$ or $bRa$.
\end{itemize}
If $R$ is a partial order, then the set $A$ is called a \emph{partially
ordered set}.  The set, $A$, together with the partial order, $R$, is called a 
\emph{poset}, $(A, R)$.

In this case,
\begin{itemize}
\item $a$ is a \emph{minimal element} of $A$ if $\not\exists b\in A [b R a\wedge b\neq a]$
\item $a$ is a \emph{maximal element} of $A$ if $\not\exists b\in A [aR b\wedge
b\neq a]$

\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{anti-chain} iff its elements are
pairwise incomparable.
\end{itemize}

A \emph{topological sort} of a finite poset $(A, R)$ is a total ordering
of all the elements of $A$, $a_1, a_2, \cdots, a_n$ in such a way that for all
$i < j$, either $a_i R a_j$ or $a_i$ and $a_j$ are incomparable.




\begin{theorem*}
Given any finite poset $(A, R)$ for which the longest chain
has length $t$, $A$ can be partitioned into $t$ antichains.
\end{theorem*}

\begin{theorem*}[Dilworth]
For all $t$, every poset with $n$ elements 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*}


\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*}

\section{Graphs}

A {\em simple graph} is a pair of sets $(V, E)$ called \emph{vertices} and
\emph{edges}, respectively. An edge $\{a,b\} \in E$ is a set  where $a, b \in
V$ and $a \neq b$.

A \emph{directed graph} or \emph{digraph} is a pair of sets of $(V,E)$
where $E \subseteq V\times V$.  In other words, an edge $(a,b) \in E$ is
an \emph{ordered pair} of vertices.

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

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

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

\begin{theorem*}
If undirected graph $G$ has Euler tour, then $G$ is connected and every
vertex has even degree.
\end{theorem*}

A \emph{Hamiltonian path} of an undirected graph $G$ is  simple path that
traverses every vertex exactly once. 

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

A derived variable $f : Q \to \reals$ is \emph{strictly decreasing} iff
\[
q \rightarrow q' \text{  implies  } f(q') < f(q).
\]

\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 $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are posets, then the
\emph{lexicographic partial order}, $\lexle$, on $P_1 \cross P_2$ is
defined by the condition that
\begin{equation*}
(p_1,p_2) \lexle (q_1,q_2) \ \eqdef\quad p_1 \prec_1 q_1\text{ or
}(p_1=q_1 \land p_2 \preceq_2 q_2).
\end{equation*}

The \emph{coordinatewise partial order}, $\coordle$, on $P_1
\cross P_2$ is defined by the condition that
\begin{equation*}
(p_1,p_2) \coordle (q_1,q_2) \ \eqdef\quad (p_1 \preceq_1 q_1 \land p_2
\preceq_2 q_2).
\end{equation*}

A poset $(P,\preceq)$ is \emph{well-founded} iff every nonempty subset $S
\subseteq P$ has a \emph{minimal element}.

\begin{lemma*}
Suppose $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are posets.  Then
\begin{enumerate}

\item so are $(P_1 \cross P_2,\lexle)$ and $(P_1 \cross
P_2,\coordle)$.  Moreover,

\item if $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are both
well-founded, then so are $(P_1 \cross P_2,\lexle)$ and $(P_1 \cross
P_2,\coordle)$.

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

\begin{lemma*}
A poset is well-founded iff it has no infinite 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}
