\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

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

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

\begin{document}
\maketitle

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

\item Reminder for homework
\begin{enumerate}
\item
Never use an example as a proof. You may use counter-example only to
disprove.

\item
If you are typing in \LaTeX\, always verify that you are using the
correct symbols and that displays properly when printed!  If you are
running over the margin, you may consider to split your expressions
into a new line.

\item
Follow the homework guidelines, it specifies that your homework {\em
must\/} be single sided, whether it is handwritten or printed. Some
students still disregard this and other guidelines.  Penalties are
being applied.  
\end{enumerate}

\item
Rosen 2.1:31 -- Explain why $A \times B \times C$ and $(A \times B)
\times C$ are not the same.

The elements in $A \times B \times C$ are ordered pairs $(x,y,z)$ where
$x \in A$, $y \in B$ and $z \in C$.

The elements in $(A \times B) \times C$ are ordered pairs $(w,z)$ where
$w \in A \times B$ and $z \in C$. This means an element in $w$ looks
like $(x,y)$, where $x \in A$ and $y \in B$. Therefore, an element in
$(A \times B) \times C$ looks like $((x,y),z)$.

Therefore, the ordered pairs are different.

\begin{quote}
\emph{Note:} In the past, many students used some variation of the following incorrect notation,
which does not mean anything:
\[(A \times B \times C) = (a, b, c), \mathrm{~where~} a \in A, b \in B \mathrm{~and~} c \in C.\]
Correct notation:
\[a \in A, b \in B, c \in C, \mathrm{~and~} (a,b,c) \in (A \times B \times C).\]
The first expression is not a well-formed statement, while the second one is.
\end{quote}

\item
(Similar to 2.1:26) Suppose that $A \cup B = \emptyset$, what can
you conclude? (Prove formally)

Answer: we conclude that $(A = \emptyset) \land (B = \emptyset)$.

The proof is by contradiction. Assume $\neg [(A = \emptyset) \land (B
= \emptyset)]$ $\Rightarrow$ $(A \not= \emptyset)$ or $(B \not=
\emptyset)$ $\Rightarrow$ there is at least an element $a \in A$ or at
least an element $b \in B$.  Without loss of generality, assume it is
$a \in A$, then $a \in A \cup B$, but $A \cup B = \emptyset$,
contradiction! Therefore, $A =\emptyset$ and $B = \emptyset$.

Remember that WLOG is the proof by cases.  What we did above is a
condensed version of the following two cases:
\begin{enumerate}
\item
$A$ is not empty and $B$ is empty $\Rightarrow$ $\exists a \in A$ etc.
\item
$A$ is empty and $B$ is not empty: same as previous case but inverting
$A$ and $B$.
\end{enumerate}
Because the two cases are so similar, we can condense them into one
and add the statement WLOG.

\item
(Similar to 2.1:8) Determine whether these statements are true or false.
\begin{enumerate}
\item
$\{a,b\} \subseteq \{\{a,b\}\}$

False, because neither $a$ nor $b$ is an element in $\{\{a,b\}\}$.

\item
$\{a,b\} \in \{\{a,b\}\}$

True, because there the element $\{a,b\}$ is in $\{\{a,b\}\}$

\item
$\{a,b,c\} \subset \{a,b,c\}$

False, because the sets are equal, and the statement is wondering if it is a strict subset.

\item
$\{a,b,c\} \subseteq \{a,b,c\}$

True, because the sets are equal.

\item
$\{\} \subseteq \{a,b,c\}$

True, because the empty set $\emptyset = \{\}$ is a subset of all sets.

\item
$\emptyset \in \{a,b,c\}$

False, because the element $\emptyset$ is not in the set $\{a,b,c\}$.

\item
$\{a\} \subset \{a,a\}$

False, the set $\{a,a\}$ is really $\{a\}$
because, in a set, elements are \emph{not} repeated.  Therefore, $\{a\}
\subset \{a,a\}$ is \emph{false} because $\{a\} \not
\subset \{a\}$ (Note that $\{a\} \subseteq \{a\}$ though).
\end{enumerate}

\item
Rosen 2.3:25.  Show that the function $f(x) = |x|$ from the set of real numbers to the set of nonnegative real numbers
is not invertible, but if the domain is restricted to the set of nonnegative real numbers, the resulting function is invertible.

For a function to be invertible, it needs to be: bijective.

Therefore, we need to check if this is one-to-one (injective) and onto (surjective).

\begin{enumerate}
\item
Injective: No, $f(x_1) \not= f(x_2) \Rightarrow |x_1| \not= |x_2| \Rightarrow \pm x_1 \not= \pm x_2$

Now, if the domain is restricted to the set of nonnegative real numbers.
Is $f(x)$ injective?

$f(x_1) = f(x_2) \Rightarrow |x_1| = |x_2| \Rightarrow x_1 = x_2$.
Therefore, on the restricted domain $f(x)$ is injective.

\item
Surjective: For some element $b \in \mathrm{rng}(f) \Leftrightarrow b = |a|$, with $a \in \mathcal{R}$
$\Leftrightarrow$ $b$ is positive.

Thus, the range is the set of all nonnegative real numbers.
Because the range and the codomain are the same, we can conclude that $f$ is surjective.

\item
Bijective: No, because it is not injective.

Though, on the restricted domain, it is bijective because it is both injective and surjective.

\item
Invertible: Again, only on the restricted domain.
\end{enumerate}

\item
Rosen 2.2:19


Proving the statement: $(A \setminus B) \subseteq (A \cap \bar B)$.\\
$\forall x,\; x \in (A \setminus B)$ $\Rightarrow$ $(x \in A) \land (x
\notin B)$ $\Rightarrow$ $(x \in A) \land x \in \bar B$ $\Rightarrow$
$x \in (A \cap \bar B)$.

Proving the statement: $(A \cap \bar B) \subseteq (A \setminus B)$.\\
$\forall x,\; x \in A \cap \bar B$ $\Rightarrow$ $(x \in A) \land (x
\in \bar B)$ $\Rightarrow$ $(x \in A) \land (x \notin B)$
$\Rightarrow$ $x \in (A \setminus \bar B)$.

$(A \setminus B \subseteq A \cap \bar B)$ $\land$ $(A \cap \bar B
\subseteq A \setminus B)$ $\Leftrightarrow$  $(A \setminus B = A \cap \bar B)$.
\hfill{$\Box$}

\item
Consider $f(n) = 2n+3$, is it bijective from $\mathbb{Z}$ to $\mathbb{Z}$?

\begin{enumerate}
\item
Injective: $f(x_1) = f(x_2) \Rightarrow 2x_1+3 = 2x_2 + 3 \Rightarrow x_1 = x_2$

\item
Surjective: For some element $b \in \mathrm{rng}(f) \Leftrightarrow b = 2 a + 3$, with $a \in \mathcal{Z}$
$\Leftrightarrow b = 2(a+1) + 1 \Leftrightarrow b$ is odd.

Thus, the range is the set of odd integers.
Because the range and the codomain are not the same, we can conclude that $f$ is not surjective.

\item
Bijective: No, because it is not surjective.

\end{enumerate}

\item Rosen 2.2:25

\begin{enumerate}
\item[a.]
$A \cap B \cap C = \{4,6\}$

\item[b.]
$A \cup B \cup C = \{0,1,2,3,4,5,6,7,8,9,10\}$

\item[c.]
$(A \cup B) \cap C = \{4,5,6,8,10\}$

\item[d.]
$(A \cap B) \cup C = \{0,2,4,5,6,7,8,9,10\}$
\end{enumerate}

\item
Rosen 2.3:7b)

\begin{itemize}
\item
Domain: $\mathbb{Z}^+$
\item
Range: $\{0,1,2,3,4,5,6,7,8,9\}$
\end{itemize}

\item Quiz (Last 10 minutes)

\end{itemize}

\end{document}
