\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

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

\title{Recitation 8}
\author{Created by Taylor Spangler, Adapted by Beau Christ}
\date{}

\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}.
\item \textbf{Partial Ordering}: A relation \textbf{R} on a set \textbf{S} that is \textit{reflexive, antisymmetric, and transitive}
\end{enumerate}

\item
Rosen 9.4.25(c). 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 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 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 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right] \cdot \left[ \begin{tabular}{ccccc}
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right] = \left[ \begin{tabular}{ccccc}
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right]$

$M_{R^3} = M_{R \circ R^2} = M_{R^2} \cdot M_{R^1} = \left[ \begin{tabular}{ccccc}
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right] \cdot \left[ \begin{tabular}{ccccc}
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right] = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 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 & 1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right] \cdot \left[ \begin{tabular}{ccccc}
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right] = \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\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 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right] \lor \left[ \begin{tabular}{ccccc}
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right] \lor \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right] \lor \left[ \begin{tabular}{ccccc}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right]\\
 & = & \left[ \begin{tabular}{ccccc}
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
\end{tabular} \right]
\end{eqnarray*}

So it was already transitive.

\item Rosen 9.4.27(a)
\begin{eqnarray*}
M_R = \left[ \begin{tabular}{ccccc}
0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
\end{tabular} \right]
W_1 = \left[ \begin{tabular}{ccccc}
0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 \\
\end{tabular} \right]
W_2 = \left[ \begin{tabular}{ccccc}
1 & 1 & 1 & 0 \\
1 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 \\
\end{tabular} \right]
W_3 = \left[ \begin{tabular}{ccccc}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 \\
1 & 1 & 1 & 1 \\
\end{tabular} \right]
\end{eqnarray*}
\begin{eqnarray*}
W_4 = \left[ \begin{tabular}{ccccc}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
\end{tabular} \right]
\end{eqnarray*}

So the transitive closure contains all 16 pairs.
Is this transitive? \textbf{Yes}

\item 9.5.3 a) Is $\{(f,g)\mid f(1) = g(0)$ and $f(0) = g(1)\}$ an equivalence relation on the set of all functions $f:\mathbb{Z} \rightarrow \mathbb{Z}$?
\begin{itemize}
\item So this relation, contains $(f,g)$, if $f(1) = g(0)$ and $f(0) = g(1)$.
\item So is this relation Reflexive? No, $f(0) = f(0)$ and $f(1) = f(1)$, this is only true when $f(0) = f(1)$. But there are other cases, so this is not reflexive.
\item Is this relation Symmetric?Yes, if $f(1) = g(0)$ and $f(0) = g(1)$, then $g(1) = f(0)$and $g(0) = f(1)$. So: if $(f,g)$ then $(g,f)$
\item Is this relation Transitive? Suppose we have $(f,g)$ and $(g,c)$. Then $f(1) = g(0)$ and $f(0) = g(1)$ and $g(1) = c(0)$ and $g(0) = c(1)$. Therefore $f(1) = c(1)$ and $f(0) = c(0)$ so it is not neccessarily true that $f(1) = c(0)$ and $f(0) = c(1)$. So no this is not transitive..
\end{itemize}

\item 9.5.3 b) How about $\{(f,g)\mid f(1) = g(1)$ or $f(0) = g(0)\}$
\begin{itemize}
\item Is it Reflexive? Yes  if $f(1) = g(1)$, then $g(1) = f(1)$, same for $f(0)$ and $g(0)$
\item Is it Symmetric? Yes, again similar to last time.
\item Is it Transitive? No, suppose $f(1) = g(1)$ and $g(0) = c(0)$, but $f(0) \neq c(0)$ and $f(1) \neq c(1)$. Then we have $(f,g)$ and $(g,c)$, but we don't have $(f,c)$.
\end{itemize}

\item Equivalence Relations: 51 - Show that the partition of the set of bit strings of lengh 16 formed by equivalence classes of bit strings of bit strings that agree on the last eight bits is a refinement of the partition formed from the equivalence classes of bit strings that agree on the last 4 bits.
\begin{itemize}
\item 
\end{itemize}

\item Partial orderings, 9.6.1 a)\{(0,0),(1,1),(2,2),(3,3)\}
\begin{itemize}
\item Yes, it is reflexive, antisymmetric, and transitive
\end{itemize}

\item Partial orderings, 9.6.3 b) Let $S$ be the set of all people in the world, and let $aRb$ be the relation $a$ is not taller than $b$. is this a partial ordering?
\begin{itemize}
\item Reflexive: clearly $a$ cannot be taller than $a$, so $(a,a)$.
\item Antisymmetric: Suppose we have $(a,b)$ is it possible to have $(b,a)$ if $b \neq a$? Yes, suppose $a$ and $b$ have the same height, but are different people.
\item Transitive: Yes, if $a$ is not taller than $b$ and $b$ is not taller than $c$ then $a$ is not taller than $c$.
\item So no, it is not antisymmetric, therefore it is not a partial ordering.
\end{itemize}
\end{itemize}

\end{document}