\documentclass[12pt,english]{amsart}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{geometry}
\geometry{verbose,tmargin=.8in,bmargin=1in,lmargin=1in,rmargin=1in}
\usepackage[all]{xy}
\usepackage{bussproofs}
\usepackage{enumitem}

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

\newcounter{problems}
\theoremstyle{definition}
\newtheorem{problem}[problems]{Problem}

\theoremstyle{remark}
\newtheorem*{solution}{Solution}



\title{Math 301: Homework 5}



\begin{document}
\maketitle


\begin{problem}
	Let $f:X\rightarrow Y$ and $g:Y \rightarrow Z$ be functions.
	\begin{enumerate}[label=(\alph*)]
		\item Show that if $f$ and $g$ are surjective, then $g\circ f$ is surjective.
		\begin{solution}
		\end{solution}
		\item Show that if $g\circ f$ is surjective, then $g$ is surjective.
		\begin{solution}
			\end{solution}
	\end{enumerate} 
\end{problem}

\begin{problem}
	Let $f:X\rightarrow Y$ be a function and $V\subset Y$. Prove or find a counterexample for each of the following assertions.
	\begin{enumerate}[label=(\alph*)]
		\item $g(V)\subset f^{-1}(V)$ for every left inverse $g$ of $f$.
		\begin{solution}
			\end{solution}
		\item $ f^{-1}(V)\subset g(V)$ for every left inverse $g$ of $f$. 		
		\begin{solution}
			\end{solution}
		\item $ f^{-1}(V) \subset g(V)$ for every right inverse $g$ of $f$. 
		\begin{solution}
			\end{solution}
		
		\item $g(V)\subset f^{-1}(V)$ for every right inverse $g$ of $f$.   
		\begin{solution}
			\end{solution}
	\end{enumerate}
\end{problem}


\begin{problem} $\ $
	\begin{enumerate}[label=(\alph*)]
		\item Let $f:X\rightarrow Y$ be a function. Suppose that $f$ has a left inverse $g_L$ and a right inverse $g_R$. Show that $g_L=g_R$.
		\begin{solution}
		\end{solution}
		\item Let $f:X\rightarrow Y$ be a bijection. Show that a function $g:Y\rightarrow X$ is a right inverse of $f$ if and only if it is a left inverse of $f$. Moreover, show that such function is unique. In this case, we denote this function $f^{-1}:Y\rightarrow X$.
		\begin{solution}
		\end{solution}
		\item Let $f:X\rightarrow Y$ be a function. Show that if $f$ has a two-sided inverse, then it is bijective.
		\begin{solution}
		\end{solution}
	\end{enumerate}
	  
\end{problem}



\begin{problem}
	Let $X,Y,Z$ be sets. Find a bijection (with proof) between $X\times (Y\times Z)$ and $X\times Y \times Z$.
\end{problem}
\begin{solution}
\end{solution}
\begin{problem}
	For each of the following pairs of sets $X,Y$, construct a bijective function (with proof) $f:X\rightarrow Y$.
	\begin{enumerate}[label=(\alph*)]
		\item $X=\mathbb{Z}, Y=\mathbb{N}$
		\begin{solution}
		\end{solution}
		\item $X=\mathbb{R}, Y=(-1,1)$
		\begin{solution}
		\end{solution}
	\end{enumerate}
\end{problem}

\begin{problem}
	Let $f:X \rightarrow \mathcal{P}(X)$ be a function where $\mathcal{P}(X)$ is the power set of $X$. By considering the set $B=\{x\in X| x\not \in f(x)\}$, prove that $f$ is not surjective.
\end{problem}
\begin{solution}
\end{solution}
\begin{problem}
	Given $m\in \mathbb{N}$, define $m^n$ for all $n\in \mathbb{N}$ by recursion on $n$, and prove that $2^2=4$.
\end{problem}
\begin{solution}
\end{solution}


\end{document}
