
\newpage\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{xcolor}

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge
21-128 problem sheet 5
}

Solutions to starred (*) exercises are due at the beginning of recitation on

\textbf{Thursday 15th October 2015}

Please submit answers to separate questions on separate sheets of paper.

\end{center}

\subsubsection*{Problem 1 --- 4.22 *}
Verify that the function $f : (0,1) \to \mathbb{R}$ defined by
$$f(x) = \frac{2x-1}{2x(1-x)} \quad \text{for all } x \in (0,1)$$
is a bijection.

\subsubsection*{Problem 2 --- 4.29}
Consider three functions $f,g,h : \mathbb{R} \to \mathbb{R}$, defined for all $x \in \mathbb{R}$ by
$$f(x) = \frac{x}{1+x^2}, \quad g(x) = \frac{x^2}{1+x^2}, \quad h(x) = \frac{x^3}{1+x^2}$$
\begin{enumerate}[(a)]
\item Determine which of these functions are injective.
\item Prove that $f$ and $g$ are not surjective.
\item Graph all three functions.
\end{enumerate}

\subsubsection*{Problem 3 --- 4.30 *}
Given real numbers $a,b,c,d$, let $f : \mathbb{R}^2 \to \mathbb{R}^2$ be defined by $f(x,y) = (ax+by,cx+dy)$ for all $(x,y) \in \mathbb{R}^2$. Prove that $f$ is injective if and only if $f$ is surjective.

\newpage
\subsubsection*{Problem 4 --- 4.34 *}
Let $f : A \to B$ and $g : B \to C$ be functions, and define $h = g \circ f$. Determine which of the following statements are true, giving proofs for the true statements and counterexamples for the false statements:
\begin{enumerate}[(a)]
\item If $h$ is injective, then $f$ is injective.
\item If $h$ is injective, then $g$ is injective.
\item If $h$ is surjective, then $f$ is surjective.
\item If $h$ is surjective, then $g$ is surjective.
\end{enumerate}

\subsubsection*{Problem 5 --- 4.36}
Consider functions $f : A \to B$ and $g : B \to A$. Prove that
\begin{enumerate}[(a)]
\item If $f \circ g$ is the identity function on $B$, then $f$ is surjective.
\item If $g \circ f$ is the identity function on $A$, then $f$ is injective.
\end{enumerate}

\textit{To remind you: given a set $X$, the identity function on $X$ is the function $\mathrm{id}_X : X \to X$ defined by $\mathrm{id}_X(x)=x$ for all $x \in X$.}

\subsubsection*{Problem 6 --- 4.37}
Consider a function $f : A \to A$. Prove that if $f \circ f$ is injective, then $f$ is injective.

\subsubsection*{Problem 7 --- 4.45 *}
Let $A$ be a set and let $f : A \to A$ be a function. Prove that if $A$ is finite, then $f$ is injective if and only if $f$ is surjective; and that if $A$ is infinite, then this equivalence need not hold.

\subsubsection*{Problem 8 --- 4.47}
Prove that the set of all natural numbers, the set of all even natural numbers, and the set of all odd natural numbers all have the same cardinality.

\subsubsection*{Problem 9 --- 4.51 *}
Construct an explicit bijection from the open interval $(0,1)$ to the closed interval $[0,1]$.

\subsubsection*{Problem 10 *}
Fix a prime number $p \in \mathbb{N}$, and define
$$S = \{ (x,y,z) \in \mathbb{N}^3 : x^2+4yz=p \}$$
Prove that the function $f : S \to S$ defined for all $(x,y,z) \in S$ by
$$f(x,y,z) = \begin{cases} (x+2z, z, y-x-z) & \text{if } x < y - z \\ (2y-x, y, x-y+z) & \text{if } y-z < x < 2y \\ (x-2y, x-y+z, y) & \text{if } x>2y \end{cases}$$
is a bijection and is its own inverse (i.e.\ $f^{-1}=f$).

[\textit{Optional:} Prove that if $p=4k+1$ for some $k \in \mathbb{N}$, then $f(x,y,z)=(x,y,z)$ for exactly one triple $(x,y,z) \in S$.]

\subsubsection*{Problem 11 *}
Let $f : A \to B$ be a function.
\begin{enumerate}[(a)]
\item Prove that there exists a set $X$ and functions $p : A \to X$ and $i : X \to B$, with $p$ surjective and $i$ injective, such that $f = i \circ p$.
\item Prove that there exists a set $Y$ and functions $j : A \to Y$ and $q : Y \to B$, with $j$ injective and $q$ surjective, such that $f = q \circ j$.
\end{enumerate}

\end{document}