\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

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

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

\begin{document}
\maketitle

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

\item Rosen 2.3:19, but determine whether $f$ is injective,
  surjective, bijective, and invertible.  If $f$ is not invertible,
  what is the largest domain and co-domain in which $f$ is invertible). 

$f$ is defined over $\mathcal{R} \rightarrow \mathcal{R}$.
\begin{itemize}
\item[a)]
$f(x) = 2x + 1$
\begin{enumerate}
\item
We prove that $f$ is injective by applying the definition:
$f(x_1) = f(x_2) \Rightarrow 2x_1 + 1 = 2x_2 + 1 \Rightarrow x_1 = x_2$, therefore it is injective.

\item
Surjective:
$\forall b \in \mathrm{co-domain}(f)$, $b = 2a + 1 \Rightarrow 2a=b-1 \Rightarrow a = \frac{b-1}{2}$.\\
$b \in \mathcal{R} \Rightarrow \frac{b-1}{2} \in \mathcal{R} \Rightarrow a \in \mathcal{R} = \mathrm{domain}(f)$.\\
Thus, $\forall b \in \mathrm{co-domain}(f) \Rightarrow (\exists a \in \mathrm{domain}(f),  b=f(a))$
Therefore, $f$ is surjective.

\item
Bijective: $f$ is both injective and surjective, thus it is surjective.

\item $f$ is bijective thus it is invertible: $f^{-1}(y) = x$.  We
  know that $y = 2x+1 \Rightarrow x={y - 1 \over 2}$.  Thus,
  $f^{-1}(y) = {y - 1 \over 2}$.
\end{enumerate}

\item[b)]
$f(x) = x^2 + 1$

\begin{enumerate}
\item
Surjective:
For some element $b \in \mathrm{co-domain}(f)$, $b = a^2 + 1
\Rightarrow \pm \sqrt{b-1} = a$, for some element $a \in
\mathcal{R} = \mathrm{domain}(f)$. But, if $b < 1$, $\sqrt{b-1}$
is not defined. Therefore, $f$ is not surjective.

Could have also proved that $f$ is not
surjective by using a proof by counter-example: $-4=f(x)$ has
no such pre-image.

If we were to restrict the co-domain to the set of all reals
greater than or equal to~1, $\sqrt{b-1}$ will be defined. Thus,
$\forall b \in \mathcal{R} \geq 1 \Rightarrow (\exists a \in
\mathrm{domain}(f), b=f(a))$. Therefore, on the restricted
co-domain, $f$ is surjective.

\item
We try to prove that $f$ is injective by applying the definition:
$f(x_1) = f(x_2) \Rightarrow x_1^2 + 1 = x_2^2 + 1$.  Now remember the
trick mentioned repeatedly in class: we move the same `powers' to the
same side: $f(x_1) = f(x_2) \Rightarrow x_1^2 - x_2^2 = 1-1 = 0
\Rightarrow (x_1 - x_2)(x_1 + x_2) = 0$.  Now assume $x_1 \neq x_2$
and dividing by $(x_1 - x_2)$, we get: $f(x_1) = f(x_2) \Rightarrow
x_1 + x_2 = 0$ which is possible for an infinity of pair of values
$x_1, x_2 \in \rm{domain}(f)$ with $x_1 = -x_2$ such as 2,-2 or
10,-10.  Therefore, $f$ is not injective.

Could have also proved that $f$ is not
injective by using a proof by counter-example: $4=f(x)$ has
two pre-images $x = -2$ and $x = 2$.

If we were to restrict the domain to the set of all reals
greater or equal to~1, the function can only be satisfied when
$x_1 = x_2$. Therefore, on the restricted domain, $f$ is
injective.

\item
Bijective:
No, because $f$ is not injective.

On the restricted co-domain and domain, $f$ will be bijective.

\item For the restricted domain, $f$ is bijective thus it is
invertible: $f^{-1}(y) = x.$ We know that $y = x^2 + 1
\Rightarrow x = \sqrt{y-1}$. Thus, $f^{-1}(y) = \sqrt{y-1}$.
(Note that really $x = \pm \sqrt{y-1}$. Though, because the restricted domain, $x$ must be positive).
\end{enumerate}
\end{itemize}

\item
Let $f(x) = x - 4$ and $g(x) = (x+1)^2 + 1$.  What is $f \circ g$?

Formally, you need first to make sure that
\begin{enumerate}
\item $f$, $g$ are functions.
\item $\rm{rng}(g) \subseteq \rm{domain}(f)$.
\end{enumerate}
Then you can proceed with the calculations:
$f \circ g = f(g(x)) = f((x+1)^2+1) = (x+1)^2 + 1 - 4 = x^2 + 2x + 1 + 1 - 4 = x^2 + 2x - 4$.

\item  (Parts from Rosen 8.1:3)
Let:
\begin{itemize}
\item
$S = \{1,2,3,4\}$, and let $R_1$ and $R_2$ be defined on $S$.

\item
$R_1 = \{(1,1),(2,2),(3,3),(4,4)\}$

\item
$R_2 = \{(1,2), (2,3), (3,4)\}$
\end{itemize}

What is:
\begin{itemize}
\item
The 0-1 matrix representation of $R_1$?

$M = \left( \begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{array} \right)$

\item
Is $R_1$ irreflexive?  No, it is reflexive because $\forall i M_{i,i} = 1$

\item
Is $R_1$ transitive?  Yes, because $\forall i,j,k (M_{i,j} = 1) \land (M_{j,k} = 1) \land (M_{i,k} = 1)$.

\item
Is $R_1$ asymmetric?  No, because $M_{1,1} = M_{1,1}$

\item
Is $R_1$ antisymmetric? Yes, because $\forall i,j (M_{i,j} \land M_{j,i}) \rightarrow (i=j)$

\item
The 0-1 matrix representation of $R_2$?

$\left( \begin{array}{cccc}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0
\end{array} \right)$

\item
The 0-1 matrix representation of $R_1 \cup R_2$?

$N = \left( \begin{array}{cccc}
1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{array} \right)$

\item
Is $R_1 \cup R_2$ irreflexive?  No, it is reflexive because $\forall i N_{i,i} = 1$

\item
Is $R_1 \cup R_2$ transitive?  No, because $N_{1,2} = 1 \land N_{2,3} = 1$, but $N_{1,3} = 0$.

\item
Is $R_1 \cup R_2$ antisymmetric?  Yes, because $\forall i,j (N_{i,j} \land N_{j,i}) \rightarrow (i = j)$.

\item
Is $R_1 \cup R_2$ asymmetric?  No, because $N_{1,1} = N_{1,1}$.

\item
Is $R_1 \cup R_2$ symmetric?  No, because $N_{1,2} \not= N_{2,1}$.

\item
The 0-1 matrix representation of $R_1 \circ R_2$?  (Note: You apply $R_2$ then $R_1$.)

Using the graphical representation:

\begin{center}
\includegraphics[scale=0.6]{recitation8_composition.pdf}
\end{center}

$M_{R_1 \circ R_2} = \left( \begin{array}{cccc}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0
\end{array} \right)$

You can also compute $M_{R_1 \circ R_2}$ by doing the bit matrix
product of $M_{R_2} \cdot M_{R_1}$.

$M_{R_1 \circ R_2} = \left( \begin{array}{cccc}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0
\end{array} \right)
\cdot
\left( \begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{array} \right) = \left( \begin{array}{cccc}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0
\end{array} \right)$

\end{itemize}

\item No Quiz...

\end{itemize}

\end{document}
