\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

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

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

\begin{document}
\maketitle

\begin{itemize}
\item Questions about lecture / homework so far?

\item
Rosen 8.6.1(a)

A relation $R$ on a set $S$ is a partial order if it is:
\begin{itemize}
\item
Reflexive

\item
Antisymmetric

\item
Transitive
\end{itemize}
Note: That if $R$ satisfies these conditions, the set $S$ with the partial order $R$ is called a
\emph{partially ordered set (poset)} and is denoted $(S,R)$.

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, antisymmetric, and transitive. Therefore, our
relation is a partial order.

\item
Rosen 8.6.1 (b)

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

Our relation is reflexive, and transitive, but is \emph{not} antisymmetric because $(3,4) \in R \land (4,3) \in R$, but $3 \not= 4$.

Therefore,
our relation is \emph{not} a partial order.

\item

Rosen 8.6:33

First draw the relation as a directed graph, then convert it to a hasse diagram:

\begin{center}
\includegraphics[scale=.75]{week10_hasse}
\end{center}

Maximal elements: $\{45,24\}$

Minimal elements: $\{5,3\}$

No greatest element

No least element

Upper bounds of $\{3,5\}$: $\{15,45\}$

Least upper bounds of $\{3,5\}$: 15

Lower bounds of $\{15,45\}$: $\{15,5,3\}$

Greatest lower bound of $\{15,45\}$: 15

Is this poset a latice: No.  Consider the lower bounds of $\{5,3\} = \emptyset$.
Therefore, there is no greatest lower bound of $\{5,3\}$.
\begin{quote}
Recall that a poset in which every pair of elements has both a
least upper bound and a greatest lower bound is called a latice.
\end{quote}


\item
Rosen 8.1.25(b)

Complementary relation $\bar R$ is the set of ordered pairs $\{(a,b) | (a,b) \notin R\}$.

$\bar R = \{(a,b) | a \textnormal{ does not divide } b\}$

\item
Consider:

$R = \left( \begin{tabular}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 \\
\end{tabular} \right)$

$\bar R = \left( \begin{tabular}{cccc}
0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 \\
\end{tabular} \right)$

\item
Rosen 8.3.11 How can the matrix for $\bar R$, the complement of the relation $R$,
be found from the matrix representing $R$, when $R$ is a relation
on a finite set $A$?

The matrix for $\bar R$ can be found from the matrix of $R$ by flipping
all the 1's to 0's, and all the 0's to 1's.
This result is because any element that was in $R$ is not in $\bar R$ (1 $\rightarrow$ 0), and any element that was not in $R$
is in $\bar R$ (0 $\rightarrow$ 1)


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

\end{document}
