
\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

Six 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}

