\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

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

\title{Recitation 8}
\author{Taylor Spangler}

\begin{document}
\maketitle

\begin{itemize}
\item (3 min max) Questions about last week's quiz?
\item Questions about lecture / homework so far?

\item Today we're looking at Relations.
\item First, a few definitions:
\begin{enumerate}
\item \textbf{Reflexive}: $(a,a) \in R$ for all $a\in A$
\item \textbf{Symmetric}: $\forall a,b \in A$, $(a,b) \in R \rightarrow (b,a) \in R$
\item \textbf{Antisymmetric}:$a,b \in A$, $(a,b)\in R$ and $(b,a)\in R$ then $a=b$
\item \textbf{Transitive}: $a,b,c \in A$, $(a,b) \in R$ and $(b,c)\in R$ then $(a,c) \in R$
\item \textbf{Irreflexive}: $\forall a\in A$, $(a,a)\notin R$
\item \textbf{Asymmetric}: $(a,b)\in R$ then $(b,a) \notin R$
\item \textbf{Equivalence Relation}: A relation that is \textit{reflexive}, \textit{symmetric}, and \textit{transitive}.
\end{enumerate}
\item First let's look at problem 9.1.3 a, determine whether the following relation is symmetric, antisymmetric, reflexive, and/or transitive, over \{1,2,3,4\}
\begin{enumerate}
\item $R =  \{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)\}$
\item Is it reflexive? \textbf{No, there is no (4,4) element}
\item Is it symmetric? \textbf{No, there are no (4,2), or (4,3) elements}
\item Is it Antisymmetric? \textbf{No, (2,3) and (3,2) are elements}
\item Is it Transitive? \textbf{Yes}
\end{enumerate}
\item How about 9.1.3 b: over \{1,2,3,4\}
\begin{enumerate}
\item $S =  \{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$
\item Is it reflexive? \textbf{Yes}
\item Is it symmetric? \textbf{Yes}
\item Is it Antisymmetric? \textbf{No, (2,1) and (1,2) are elements}
\item Is it Transitive? \textbf{Yes}
\end{enumerate}

\item What is the relation $S\cup R$?
\begin{displaymath}
S\cup R = \{(1,1),(1,2),(2,1),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4),(4,4)\}
\end{displaymath}
\begin{enumerate}
\item Antisymmetric?: \textbf{No, no (1,2) and (2,1)}
\item Symmetric? \textbf{No, no (4,2) element}
\item Reflexive? \textbf{Yes}
\item Transitive? \textbf{No} (1,2) and (2,4), but no (1,4)
\end{enumerate}
\item What is the relation $S\cap R$?
\begin{displaymath}
S\cup R = \{(1,1),(2,2),(3,3),(4,4)\}
\end{displaymath}
\begin{enumerate}
\item Antisymmetric? \textbf{Yes}
\item Symmetric? \textbf{Yes}
\item Reflexive? \textbf{Yes}
\item Transitive? \textbf{Yes}
\end{enumerate}

\item Represent S as a bit matrix:
$M_S = \left[ \begin{tabular}{ccccc}
1 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{tabular} \right]$

\item
Rosen 9.4.25(b). Use Algorithm~1 (Given on page 603) 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 Rosen 9.4.27(b)
\begin{eqnarray*}
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]
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]
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]
W_3 = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 \\
\end{tabular} \right]
\end{eqnarray*}
\begin{eqnarray*}
W_4 = \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*}

So the transitive closure looks like \{(2,1),(2,3),(2,4),(3,1),(3,3),(3,4),(4,1),(4,3),(4,4)\}
Is this transitive? \textbf{Yes}

\item The following are relations on \{1,2,3,0\} are they equivalence relations?
\begin{itemize}
\item \{(0,0),(1,1),(2,2),(3,3)\} \textbf{Yes} this one is fairly obvious, as everything just relates back to itself.
\item \{(0,2),(2,0),(2,2),(2,3),(3,2),(3,3)\} \textbf{No}, missing (0,0) (I removed it this is not identical to 9.5 \#1), so not reflexive.
\item  \{(0,0),(1,1),(1,2),(2,1),(2,2),(3,3)\} \textbf{Yes}
\end{itemize}

\item Problem number 47 from 9.5: \{0\}, \{1,2\},\{3,4,5\}
\begin{itemize}
\item So here we'll have $(a,b)$ iff $a$ and $b$ are in the same subset
\item So, $(0,0)$ is an element.
\item (1,1),(1,2),(2,1),(2,2) are elements.
\item (3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5) are also elements.
\item So our equivalence relation is: \{(0,0),(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)\}
\end{itemize}

\end{itemize}

\end{document}