\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

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

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

\begin{document}
\maketitle

\begin{itemize}

\item Problem 2.2:31: Show that for $A$ and $B$ subsets
  of some universal set $U$, 
\[A\subseteq B \Leftrightarrow \bar B \subseteq \bar A\]
\begin{tabular}{rlr}
$A\subseteq B \Leftrightarrow$ & &  \\
\multicolumn{1}{r}{$\forall x,$} & $x \in A \rightarrow x \in B$ & Definitionof set inclusion\\

& $ \Leftrightarrow x \notin A \vee x \in B \Leftrightarrow$ & Implication rule\\

& $ x \in B\vee x \notin A  \Leftrightarrow $ &  Commutativity\\

& $x \notin B\rightarrow x \notin A \Leftrightarrow $ & Implication rule\\

& $ x \in \bar B\rightarrow x \in\bar A \Leftrightarrow $ & Definition of set complement\\

$\bar B \subseteq \bar A$ && by definition of a set inclusion\\
& &  QED
\end{tabular}

\item 2.2.37 c: Show that if $A$ is a subset of universal set $U$
\[A \oplus U = \bar{A}\]
\begin{tabular}{rlr}
$\forall x,$ & $x \in  A \oplus U$  $\Leftrightarrow$ &\\
& $((x \in A) \lor (x \in U)) \land \neg ((x \in A) \land (x \in U)) \Leftrightarrow$ & definition of symmetric \\
&&difference $\oplus$ on page 137\\
& $((x \in A \cup U)) \land \neg ((x \in A \cap U)) \Leftrightarrow$ &Definition set union, intersection\\

& $(x \in U) \land \neg(x \in A) \Leftrightarrow$ & Domination,
  identity laws\\
& $ \neg(x \in A) \land (x \in U)  \Leftrightarrow$ & Commutative law (logic)\\
& $ (x \notin A) \land (x \in U)  \Leftrightarrow$ & Moving negation inward\\
& $ x \in \bar A $ & Definition of set absolute complement\\
\end{tabular}
We showed that $\forall x,\; x \in A \oplus U \Leftrightarrow x \in \bar{A}$. Thus, $A \oplus U = \bar{A}$. \hfill $\Box$

\item Suppose that $A \cup B = \emptyset$, what can you conclude?\\
Answer: we conclude that $(A = \emptyset) \land (B = \emptyset)$.

We formally prove  that:
\[A \cup B = \emptyset \Leftrightarrow (A = \emptyset) \land (B = \emptyset)\]

First we consider prove the following statement:
\[A \cup B = \emptyset \rightarrow (A = \emptyset) \land (B = \emptyset)\]

The proof is by contradiction. We assume the antecedent and negate the conclusion. 
\begin{tabular}{rlr}
(1) & $A \cup B = \emptyset$ & given\\
(2) & $\neg((A = \emptyset) \land (B = \emptyset))$ & negating the conclusion\\
(3) & $(A \neq \emptyset) \lor (B \neq \emptyset)$ & moving negation inward\\
(4) & $(A \neq \emptyset) \lor (B \neq \emptyset)$ & moving negation inward\\
\end{tabular}


We continue the proof using a proof by cases.  Expression~(4) states
that, at least one of the following cases must hold and both can also
hold:
\begin{enumerate}[(a)]
\item There is at least an element in $A$, assume we have $x \in A$
\item There is at least an element in $B$, assume we have $y \in B$
\end{enumerate}

Case (a) above: $x \in A \Rightarrow x \in \{A \cup B\}$ by definition of set union $A\cup B \neq \emptyset$, which contradicts the premise~(1).  

Case (b) can be shown to yield the same contradiction (exchanging $A$
for $B$ in the above case).

WLOG, we can conclude that
\[A \cup B = \emptyset \Rightarrow (A = \emptyset) \land (B = \emptyset)\]

Proving the implication in the opposite direction is straightforward
by definition of set union:
\[(A = \emptyset) \land (B = \emptyset) \Rightarrow A \cup B = \emptyset\]

\mbox{}$\Box$


\item Now let's look at functions, say we have the following function: $f:\mathbb{R}\rightarrow \mathbb{R}$ where $f(x) = \lfloor \frac{x}{2} \rfloor$
\begin{itemize}
\item First what does the graph of this function look like?
\item is $f$ one-to-one (i.e., injective)? No, for example both 1 and 1.1 are assigned 0.
\item Is $f$ onto $\mathbb{R}$ (i.e., surjective)? No, the floor function only maps to integers, so only integers would be mapped to.
\end{itemize}
\item Let $A = \{1,2,3,4\}$, $ B = \{a,b,c\}$, and $ C = \{2,7,10\}$

Consider the following two functions: $g:A\rightarrow B$ and $f:B\rightarrow C$ where $g:  \{(1,b),(2,a),(3,a),(4,b)\}$ and $f: \{(a,10),(b,7),(c,2)\}$
\begin{itemize}
\item Find $f\circ g$.  Answer: $\{(1,7),(2,10),(3,10),(4,7)\}$
\item Find$f^{-1}$.   Answer: $\{(10,a),(7,b),(2,c)\}$

\item Is $g^{-1}$ a function? Answer: No, because $a$ has two pre-images 
 but in a function, each element of the domain must be 
  mapped to \textit{exactly one} element in the co-domain.
\item Find $f\circ f^{-1}$.  Answer: $\{(10,10),(7,7),(2,2)\}$
\end{itemize}

\item Prove or disprove: $\forall x,y \in \mathbb{R}, \lfloor x \times y\rfloor \leq \lfloor x \rfloor \times \lfloor y\rfloor$
\begin{itemize}
\item let $x$ = 3.5, and $y$ = 1.5. $\lfloor 3.5\times 1.5\rfloor =
  \lfloor 5.25\rfloor = 5$, but $\lfloor 3.5 \rfloor \times \lfloor
  1.5\rfloor = 4$
\item $5\neq 4$, therefore the statement does not hold.  This is a proof with a counterexample.

\end{itemize}
\item Prove or disprove  for all $x,y \in \mathbb{R}, \lceil x \times y\rceil \leq \lceil x \rceil \times \lceil y\rceil$
\begin{itemize}

\item Here the same example works $\lceil 3.5\times 1.5\rceil = \lceil 5.25\rceil = 6 $,
  but $\lceil 3.5 \rceil \times \lceil 1.5\rceil = 4 \times 2 =8$
\end{itemize}

\item Show that the function $f: \mathbb{R} \rightarrow \mathbb{R^+}$
  where $f(x) = |x|$ is not invertible, but if the domain is
  restricted to the set of nonnegative real numbers (i.e., $f:
  \mathbb{R^+} \rightarrow \mathbb{R^+}$), the resulting function is
  invertible.

For a function to be invertible, it must be bijective (i.e., a
one-to-one correspondance).

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: Every element in codomain ( $\mathbb{R^+}$) is a positive
number, then for $\forall b \in \mathit{codomain}(f) \exists a \in
\mathbb{R} b = |a|$.  Thus, $b$ has necessarily a preimage.  Thus, the
range and the codomain are equal, we can conclude that $f$ is
surjective.

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

However, 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 Now a quick review of membership, 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\}$ \hfill {\em Trick question: watch out!}

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}


\end{itemize}

\end{document}
