\documentclass{article}
\usepackage{amssymb, mathrsfs, enumitem}
\usepackage{tikz-cd}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig, colortbl}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\theoremstyle{definition}
\newtheorem{prop}{Proposition}
\newtheorem{fact}{Fact}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\renewcommand{\today}{}


\addtolength{\topmargin}{-.875in}
\addtolength{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\la}{\Leftarrow}
\newcommand{\ra}{\Rightarrow}
\renewcommand{\iff}{\Leftrightarrow}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}

\newcommand{\inv}[1]{#1^{-1}}

\newcommand{\eps}{\epsilon}
\newcommand{\N}{\mathbb{N}}

\newcommand{\ba}{\backslash}


\begin{document}
\title{Math 127 Homework}
\author{Mary Radcliffe}
\date{Due 21 March 2019}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).

For these problems, $X, Y, Z$ always represent sets.
\begin{enumerate}

\item (*)\begin{enumerate}
\item Prove that there exists an injection $f:X\to Y$ if and only if there exists a surjection $g:Y\to X$.
\item Use part (a) to show that there exists a bijection $f:X\to Y$ if and only if there exists a bijection $g:Y\to X$.
\end{enumerate}

\item Let $f:X\to Y$.
\begin{enumerate}
\item If $g$ is a left inverse to $f$, is it necessarily injective? surjective? Give a proof of those properties $g$ must possess, and a counterexample to the others.
\item If $h$ is a right inverse to $f$, is it necessarily injective? surjective? Give a proof of those properties $h$ must possess, and a counterexample to the others.
\end{enumerate}

\item (*) Your friend writes the following.
\begin{quote}
Suppose that $f:X\to Y$ is injective, but not surjective. Then there does not exist a bijection between $X$ and $Y$.
\end{quote}
Give an example to show that your friend is wrong, in general. What condition(s) could you put on the sets $X$ and/or $Y$ to make the statement true?

\item (*) Prove that if $f:X\to Y$ and $g:Y\to Z$ are both bijections, then $g\circ f$ is a bijection, and $\inv{(g\circ f)} = \inv f \circ \inv g$. 

\item Let $f:X\to Y$ be a function, and let $A\subseteq X$. In general, it is not true that $\inv f(f(A))=A$. Is it true when $f$ is an injection? surjection? bijection?

\item (*) Show that for any finite set $X$, there exists an injection $i:X\to \mathcal{P}(X)$, but that there does not exist a bijection. Explain why this implies that $|\mathcal{P}(X)|>|X|$.

\item Carefully prove Claims 1 and 2 from the proof of Lemma 1 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Finite%20Cardinality.pdf}{Finite Cardinality Notes}.

\item Prove Corollary 3 to Lemma 1 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Finite%20Cardinality.pdf}{Finite Cardinality Notes}.

\item (*) Let $X$ and $Y$ be finite sets. Prove that $f:X\to Y$ is injective if and only if $\forall A\subseteq Y, |\inv f(A)|\leq |A|$.

\item Let $X$ and $Y$ be finite sets. Prove that $f:X\to Y$ is surjective if and only if $\forall A\subseteq Y, |\inv f(A)|\geq |A|$.

\end{enumerate}
\end{document}