\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fullpage}
\usepackage{multicol}

\title{Week 9 Recitation}
\author{Robert Woodward}

\begin{document}
\maketitle

\begin{itemize}

\item Questions about lecture / homework so far?

\item
Rosen 8.4.25(b). Use Algorithm~1 (Given on page 550) to compute
the transitive closure of the relation
$\{(2,1),(2,3),(3,1),(3,4),(4,1),(4,3)\}$ on the set
$\{1,2,3,4\}$.

\begin{itemize}
\item
We note the matrix of a relation $R^x$ resulting from the composing the relation $R$
with itself $x$ times: $M_{R^x}$, alternatively: $M_R^{[x]}$.

\item
We note the relations composition operator $\circ$ and the matrix product operator $\cdot$, alternatively, $\odot$.
\end{itemize}

$M_R = M_{R^1} = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right]$

$M_{R^2} = M_{R^1 \circ R^1} = M_{R^1} \cdot M_{R^1} = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right] \cdot \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right] = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
\end{tabular} \right]$

$M_{R^3} = M_{R \circ R^2} = M_{R^2} \cdot M_{R^1} = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
\end{tabular} \right] \cdot \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right] = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right]$

$M_{R^4} = M_{R \circ R^3} = M_{R^3} \cdot M_{R^1} = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right] \cdot \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right] = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
\end{tabular} \right]$

\begin{eqnarray*}
M_{R^*} & = & M_{R^1} \lor M_{R^2} \lor M_{R^3} \lor M_{R^4}\\
 & = & \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right] \lor \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
\end{tabular} \right] \lor \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right] \lor \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
\end{tabular} \right]\\
 & = & \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 \\
\end{tabular} \right]
\end{eqnarray*}

\item (On request):
Rosen 8.4.27(b). Use Warshall's algorithm to compute
the transitive closure of the relation
$\{(2,1),(2,3),(3,1),(3,4),(4,1),(4,3)\}$ on the set
$\{1,2,3,4\}$.

$M_R = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right]$

Fix $k = 1$:

\begin{multicols}{2}
\includegraphics[scale=0.5]{week9_warshall_k1}

\columnbreak

$W_1 = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right]$
\end{multicols}

Fix $k = 2$:

\begin{multicols}{2}
\includegraphics[scale=0.5]{week9_warshall_k2}

\columnbreak

$W_2 = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{tabular} \right]$
\end{multicols}

\newpage

Fix $k = 3$:

\begin{multicols}{2}
\includegraphics[scale=0.5]{week9_warshall_k3}

\columnbreak

$W_3 = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & \textbf{1} \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & \textbf{1} \\
\end{tabular} \right]$
\end{multicols}


Fix $k = 4$:

\begin{multicols}{2}
\includegraphics[scale=0.5]{week9_warshall_k4}

\columnbreak

$W_4 = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 0 & \textbf{1} & 1 \\
1 & 0 & 1 & 1 \\
\end{tabular} \right]$
\end{multicols}

\item
Rosen 8.5.3

To be an equivalence relation, a relation must be:
\begin{itemize}
\item
Reflexive

\item
Symmetric

\item
Transitive
\end{itemize}
Consider a function $f$:$\mathbb{Z}\longrightarrow \mathbb{Z}$.\\
Now, consider the set $F$ of all such functions, which becomes a quite
abstract notion.
\[F = \{ f \;|\; f:\mathbb{Z}\longrightarrow \mathbb{Z}\}.\]
We are going to define a relation on this set $F$, let call it $R$
\[R \subseteq F \times F.\]
Two functions $f,g \in F$ are related by $R$ iff $(f,g) \in R$.  We write $f R g$.

The question is to determine whether or not each of the following relations
on the set $F$ is an equivalence relation.
\begin{itemize}
\item[a)] Consider the relation: $\{(f,g) | f(1) = g(1)\}$. This means
  $(f,g)$ is an element of $R$ if and only if $f(1)$ and $g(1)$
  evaluate to the same value in $\mathcal{Z}$.

This relation is reflexive because $\forall f\in F, f(1) = f(1)$.

This relation is symmetric because $\forall f,g \in F, f R g
\rightarrow f(1) = g(1) \rightarrow g(1) = f(1) \rightarrow g R f$.

This relation is transitive because $f R g$ and $g R h$, 
$\rightarrow (f(1) = g(1)) \wedge (g(1) = h(1))
\rightarrow f(1) = h(1) \rightarrow f R h$.

Therefore, $R$ is an equivalence relation.

\item[b)] Consider the relation: $\{(f,g) | (f(0) = g(0)) \lor (f(1) = g(1))\}$.

  This relation is reflexive and symmetric (by similar argument to part~a), but it is
  \emph{not} transitive.

  Indeed, if $$(f R g) \wedge (g R h)
  \Rightarrow (f(0) = g(0) \lor f(1) = g(1)) \wedge (g(0) = h(0) \lor
  g(1) = h(1)).$$
  Consider the counterexample where $$(f(0)=g(0))
  \wedge (f(1)\not= g(1))$$ and $$(g(0)\not= h(0)) \wedge (g(1) = h(1)).$$
  We notice that $(f(0)=g(0)\not= h(0)) \wedge (f(1)\not=
  g(1) = h(1)) \Rightarrow (f(0)\not= h(0)) \wedge (f(1) \not= h(1))
  \Rightarrow (f,h) \notin R$, and thus the relation is not
  transitive.
\end{itemize}

\item
Rosen 8.5.41(a): Is this collection of subsets of $\{1,2,3,4,5,6\}$ a partition?  $\{1,2\}, \{2,3,4\}, \{4,5,6\}$.

The non-empty set subsets $A_1, A_2, \ldots, A_k$ are a partition 
of a set $A$ if and only if: 
\begin{itemize}
\item
$\cup_{i = 1}^k A_i = A$

\item
$\forall i \not= j, A_i \cap A_j = \emptyset$

\item
$\forall i, A_i \not= \emptyset$
\end{itemize}

For our partition:
\begin{itemize}
\item
$\cup_{i = 1}^k A_i = \{1,2\} \cup \{2,3,4\} \cup \{4,5,6\} = \{1,2,3,4,5,6\} = A$

\item
$(\{1,2\} \cap \{2,3,4\} = \{2\} \not= \emptyset)$,
$(\{2,3,4\} \cap \{4,5,6\} = \{4\} \not= \emptyset)$,
$(\{1,2\} \cap \{4,5,6\} = \emptyset)$.

\item
$(\{1,2\} \not= \emptyset)$, $(\{2,3,4\} \not= \emptyset)$
$(\{4,5,6\} \not= \emptyset)$.
\end{itemize}

Because $\forall i \not= j, A_i \cap A_j \not= \emptyset$, the two sets do not form a partition of $A$.

\newpage

\item
Rosen 8.5.41(b): Is this collection of subsets of $\{1,2,3,4,5,6\}$ a partition?  $\{1\}, \{2,3,6\}, \{4\}, \{5\}$.

For our partition:
\begin{itemize}
\item
$\cup_{i = 1}^k A_i = \{1\} \cup \{2,3,6\} \cup \{4\} \cup \{5\} = \{1,2,3,4,5,6\} = A$

\item
$(\{1\} \cap \{2,3,6\} = \emptyset)$, 
$(\{1\} \cap \{4\} = \emptyset)$, 
$(\{1\} \cap \{5\} = \emptyset)$, 
$(\{2,3,6\} \cap \{4\} = \emptyset)$, 
$(\{2,3,6\} \cap \{5\} = \emptyset)$, 
$(\cap \{4\} \cap \{5\} = \emptyset)$.

\item
$(\{1\} \not= \emptyset)$,
$(\{2,3,6\} \not= \emptyset)$,
$(\{4\} \not= \emptyset)$,
$( \{5\} \not= \emptyset)$,
\end{itemize}

Therefore, the two sets form a partition of $A$.


\item Quiz (Last 10 minutes)
\end{itemize}

{\bf Extra material:}
\begin{itemize}
\item
Rosen 8.5.1(a)

Our relation is:
$\left( \begin{tabular}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{tabular} \right)$

Our relation is reflexive, symmetric, and transitive. Therefore, it is
an equivalence relation.

\item
Rosen 8.5.1(b)

Our relation is:
$\left( \begin{tabular}{cccc}
1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 \\
\end{tabular} \right)$

It is \emph{not} reflexive (why?) and is \emph{not} transitive (why?). Therefore, it is
\emph{not} an equivalence relation.

Notice that for
transitivity, in this case, it helps to draw the directed graph
of the relation.

\end{itemize}

\end{document}