\documentclass[11pt]{article} % 

\setlength{\oddsidemargin}{-0.15in}
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

%old macro syntax 
\def\red#1{\textcolor{red}{#1}}
\def\blue#1{\textcolor{blue}{#1}}

\newcommand{\cP}{\mathcal{P}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\N}{{\bf N}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\R}{{\bf R}}
\newcommand{\Q}{{\bf Q}}
\newcommand{\points}[1]{{\it (#1 Points)}}
\newcommand{\tpoints}[1]{{\bf #1 Total points.}}
\newcommand{\im}{\mathop{\mbox{Im}}\xspace}
\begin{document} 
\openup 1 \jot
\noindent
{\bf Math 214  Foundations of Mathematics\quad 
Homework 9
\hfill Your name}

\newenvironment{answer}{\medskip \noindent}{}


\bigskip
Six points for each question unless specified otherwise.

\begin{enumerate}


\item Let $f_1: A_1 \rightarrow B_1$ and $f_2: A_2 \rightarrow B_2$ be functions.
Show that $f: A_1 \times A_2 \rightarrow B_1 \times B_2$ defined by
$f(a_1,a_2) = (f_1(a_1), f_2(a_2))$ for every pair $(a_1, a_2) \in A_1 \times A_2$,
is a function.
 
(a) Show that if $f_1, f_2$ are injective. Then $f$ is injective.

(b) Show that if $f_1, f_2$ are surjective. Then $f$ is surjective.

\item (a) Let $f: A \rightarrow B$ be a function. 
Define a relation $R$ on $A$ by 
$(a_1,a_2) \in R$ if $f(a_1) = f(a_2)$. 

\ \ \ Show that $R$ is an equivalence relation.

(b) Suppose $S \subseteq A \times B$.  Define a relation 
$\hat S$ on $A$ by
$(a_1,a_2) \in \hat S$ if there is $b \in B$ such that 

\quad
$(a_1,b), (a_2,b) \in S$. Determine whether $\hat S$ is reflexive, symmetric, transitive.



\item  Construct $f: A\rightarrow B$ and $g: B \rightarrow A$ such that
$g\circ f = i_A$ and $f\circ g \ne i_B$, where $i_A$ is the identity function
on $A$ and  $i_B$ is the identity function on $B$ in each of the following cases.

(a) $A = \{1\}$, $B = \{1,2\}$.

(b) $A = B = \N$.

\item Let $\alpha=
 \pmatrix{
    1 & 2 & 3 & 4 & 5 \cr
    2 & 3 & 4 & 5 & 1\cr}$ and $\beta=
  \pmatrix{
    1 & 2 & 3 & 4 & 5 \cr
    3 & 5 & 2 & 4 & 1\cr}$ be permutations in $S_5$. \\
 Determine $\alpha\circ \beta$, $\beta\circ \alpha$,  and $\beta^{-1}$. 


\item Let $A = \{2^a3^b: a, b \in \N\}$. Construct a bijection from 
$\N \times \N$ to $A$. 

In such a case, we say that $\N\times \N$ and $A$
has the same cardinality, denoted by $|\N\times \N| = |A|$.


\item Show that $f: \R \rightarrow (-1,1)$ defined by
$f(x) = \frac{x}{1+|x|}$ is a bijection, i.e.,  $|(-1,1)| = |\R|$.

\item (a) Construct (with proof) a bijection from $f: \{0\} \cup  \N \rightarrow \N$.
 
 (b) Construct (with proof) a bijection from $g: \Q \rightarrow \Q - \{0\}$.


Hint for (b).  Partition the domain into $A_1 \cup A_2$ with $A_1 = \{0, 1, 2, \dots\}$,
and partition the co-domain into $\N \cup A_2$.
Construct $f: \Q \rightarrow \Q - \{0\}$ 
by $f(x) =
\left\{ \begin{array}{ll}
 x+1  & \hbox{ if } x \in A_1,\\ 
  x & \hbox{ if }  x \in A_2.\end{array}\right.$

\item Show that $f:(0,1]\rightarrow (0,1)$ defined by
$$f(x) = \left\{ \begin{array}{ll} 
 \frac{1}{n+1} & \hbox{ if } x = \frac{1}{n}, \\
x & \hbox{ otherwise}, \end{array} \right.$$
is a bijection.
 
 \item (Extra credits) Construct a bijection 
 $f: \Q \times \Z_{16} \rightarrow \Z \times \Z_{3}$, and describe $f^{-1}$.
 
\end{enumerate}
\end{document}