\documentclass[11pt]{article} %
\setlength{\oddsidemargin}{-0.15in}
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}
\newcommand{\cP}{{\cal P}}
\newcommand{\N}{{\bf N}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\R}{{\bf R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\points}[1]{{\it (#1 Points)}}
\newcommand{\tpoints}[1]{{\bf #1 Total points.}}
%old macro syntax
\def\red#1{\textcolor{red}{#1}}
\def\blue#1{\textcolor{blue}{#1}}
\begin{document}
\noindent
{\large\bf Math 214 Foundations of Mathematics\quad
Homework 8 \hfill Your name}
%\newcommand{\Not}[1]{#1{\bf \kern-0.6em/}}
\newcommand{\Not}[1]{#1\kern-0.6em/}
\medskip
Five points for each problem unless specified otherwise.
\begin{enumerate}
\item Determine the largest sets $A, B \subseteq \R$ such that
$f:A\rightarrow B$ defined by $f(x) = \sqrt{3x-1}$ is a function.
Determine whether the resulting function is injective.
\item Consider $h: \Z_{16}\to \Z_{24}$ by
$h([a]_{16})=[3a]_{24}$ for each $a\in \Z$.
(a) Prove that $h$ is a function.
(b) Is $h$ injective? surjective? bijective?
[Note: In (a), one has to show that if $[a]_{16} = [b]_{16}$,
then $[a]_{24} = f([a]_{16})= f([b]_{16}) = [b]_{24}$.]
\item Let $f: \R \times \R \rightarrow \R \times \R$ where, for
$(a,b)\in \R\times \R$, $f(a,b) = (2a+7, 3b - 3)$.
Prove that $f$ is a bijective function and find $f^{-1}$.
[Note: To prove $f$ is well-defined, one has to show that every $(x,y) \in \R\times \R$,
$f(x,y) = (u,v)$ is an element in $\R \times \R$. To prove that $f$ is surjective,
one has to show that for every $(u,v) \in R\times \R$ there is $(x,y) \in \R\times \R$
such that $f(x,y) = (u,v)$. In such a way, $f^{-1}(u,v) = (x,y)$.]
\item Define $f: \N \rightarrow \Z$ by
$f(n) = \cases{ n/2 & $\hbox{ if } n \hbox{ is even}$,\cr
(1-n)/2 & $\hbox{ if } n \hbox{ is odd}$. \cr}$
Show that $f$ is a well-defined bijection.
[Note: To show that $f$ is well-defined, one has to show that for every $n \in \N$
$f(n) \in \Z$. You may need to consider two cases: $n$ is even, $n$ is odd.
To prove that $f$ is injective, one has to show that $f(n_1) = f(n_2)$ then
$n_1 = n_2$. You may need to consider four cases: $n_1$ is even or odd, $n_2$ is even
or odd. To prove that $f$ is surjective, one has to show that for every $z \in \Z$,
one can find $n \in \N$ such that $f(n) = z$. You need to consider two cases:
$z > 0$ and $z \le 0$.]
\item Suppose $A$ is a non-empty set. Determine the functions
$f: A \rightarrow A$ that are also equivalence relations.
[Hint: Try the cases when $A = \{1,2\}$ and $A = \{1,2,3\}$, and determine the general
result.]
\item Let $A, B$ and $C$ be nonempty sets and let $f, g$ and $h$ be functions such that
$f: A\to B, g: B\to C$ and $h: B\to C$. For each of the following,prove or disprove:
(a) if $g\circ f=h\circ f$, then $g=h$.
(b) if $f$ is surjective and $g\circ f=h\circ f$, then $g=h$.
[Hint: For (a), consider $f: \{a\} \rightarrow \{a,b\}$, and
$g: \{a,b\} \rightarrow \{a,b\}$.]
\item For nonempty sets $A, B, C$, let $f: A\to B$ and $g: B\to C$ be functions.
(a) Prove that if $g\circ f$ is injective, then $f$ is injective.
(b) Disprove that if $g\circ f$ is injective, then $g$ is injective.
\item For nonempty sets $A$ and $B$ and functions $f : A \rightarrow
B$ and $g: B \rightarrow A$ suppose that $g \circ f = i_A$, the
identity function on $A$.
\begin{enumerate}
\item (4 points) Show that $f$ is injective and $g$ is surjective.
\item (2 points) Show that $f$ is not necessarily surjective.
\item (2 points) Show that $g$ is not necessarily injective.
\end{enumerate}
\item (Extra 6 points)
Let $f: A \rightarrow B$ be a function, and let
$f(X) = \{f(x): x \in X\}$ for any $X \subseteq A$. Suppose
$A_1, A_2\subseteq A$.
(a) Prove that $f(A_1\cap A_2)\subseteq f(A_1)\cap f(A_2)$.
(b) Prove that if $f$ is injective, then $f(A_1)\cap f(A_2) \subseteq f(A_1\cap A_2)$.
(c) Give an example showing that $f(A_1)\cap f(A_2) \not \subseteq f(A_1\cap A_2)$
if $f$ is not injective.
\end{enumerate}
\medskip\noindent
{\bf Relevant definitions and terminology}
\medskip
\begin{itemize}
\item A relation
$f:A\rightarrow B$ is a well-defined function if for every $a\in A$ there is a unique $b\in B$
such that $(a,b) \in f$, and we write $b = f(a)$.
\item
Let $f: A \rightarrow B$ be a function.
\item The function $f$ is injective if for any $a, b \in A$ such that $a \ne b$,
it follows that $f(a) \ne f(b)$ in $B$. The function is not injective if
there are $a, b \in A$ such that $a \ne b$, but $f(a) = f(b)$ in $B$.
\item The function $f$ is surjective if for every $b \in B$ there is $a \in A$ such that
$f(a) = b$. The function is not surjective if there is $b \in B$ such that $f(a) \ne b$
for any $a \in A$.
\item
The function $f$ is bijective if $f$ is injective and surjective.
\item
For any function $R \subseteq A \times B$, $R^{-1} = \{(b,a): (a,b) \in R\}$.
If $f:A\rightarrow $ is a bijective function , then $f^{-1} = \{(b,a): (a,b) \in f\}$
is a function (bijection) and we write $b^{-1}(b) = a$.
\item
Suppose $X \subseteq A$. Then $f(X) = \{f(x): x \in X\} \subseteq B$.
\item
Suppose $g: B \rightarrow C$ is a function. Then
$g\circ f: A\rightarrow C$ is the composite function such that $g\circ f(a) = g(f(a))$.
\end{itemize}
\end{document}