%%%%%%%%%%%%%%%%%%%%%%%%
%                       	    Preamble                                 %
%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{report}
\usepackage[left=1in,right=1in,top=1in,bottom=1in]{geometry}
\setlength{\headheight}{23pt}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{verbatim}
\usepackage{url}
\usepackage{yfonts}
\usepackage{fancyhdr}
\pagestyle{fancy}
\usepackage[colorlinks]{hyperref}
\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{shapes,decorations,calc,arrows}

\begin{document}


%%%%%%%%%%%%%%%%%%%%%%%%
%                         	     Header                                    %
%%%%%%%%%%%%%%%%%%%%%%%%
\fancyhead{}
\fancyfoot{}
\lhead{\large \textbf{Math 461}}
\chead{\Large \textbf{Homework 1}}
\rhead{\large \textbf{DUE 9/8/2023}}
\cfoot{\thepage}
%\rfoot{\tiny{\copyright Mark Iwen 2023}}


%%%%%%%%%%%%%%%%%%%%%%%%
%                       Custom Commands                           %
%%%%%%%%%%%%%%%%%%%%%%%%

%\renewcommand{\theenumii}{\roman{enumii}}
%\renewcommand{\labelenumii}{(\theenumii)}
\newcommand{\supp}{\text{supp}}
\newcommand{\Aut}{\text{Aut}}
\newcommand{\Gal}{\text{Gal}}
\newcommand{\Inn}{\text{Inn}}
\newcommand{\Irr}{\text{Irr}}
\newcommand{\Ker}{\text{Ker}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\D}{\mathbb{D}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\<}{\left\langle}
\renewcommand{\>}{\right\rangle}
\renewcommand{\Re}[1]{\text{Re}\ #1}
\renewcommand{\Im}[1]{\text{Im}\ #1}
\renewcommand{\mod}[1]{(\operatorname{mod}#1)}
\newcommand{\mb}[1]{\mathbb{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\ran}[1]{\operatorname{ran}#1}
%\renewcommand{\span}{\text{span}}

\newcommand{\e}{\mathbf{e}}
\renewcommand{\u}{\mathbf{u}}
\renewcommand{\v}{\mathbf{v}}
\newcommand{\w}{\mathbf{w}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\y}{\mathbf{y}}
\newcommand{\0}{\mathbf{0}}


%%%%%%%%%%%%%%%%%%%%%%%%
%                 		    Document                                %
%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\underline{\textbf{Exercises:}}} (\S $2$ and \S $3$)



\begin{enumerate}

\item Let $f\colon A \to B$ be a function.
	\begin{enumerate}
	\item For $A_0\subset A$ and $B_0\subset B$, show that $A_0 \subset f^{-1}(f(A_0))$ and $f(f^{-1}(B_0)) \subset B_0$.
	
	\item Show that $f$ is injective if and only if $A_0=f^{-1}(f(A_0))$ for all subsets $A_0\subset A$.
	
	\item Show that $f$ is surjective if and only if $f(f^{-1}(B_0))=B_0$ for all subsets $B_0\subset B$.
	
	\end{enumerate}

\item Let $f\colon A \to B$ be a function, $A_j \subset A$ for all $j \in \Z$, and $B_j \subset B$ for all $j \in \Z$.  Prove the following:
	\begin{enumerate}
	
	\item$A' \subset A_0  \implies f(A') \subset f(A_0)$
	
	\item $B' \subset B_0 \implies f^{-1}(B') \subset f^{-1}(B_0)$
	
	\item $f(\cup_{j \in \Z} A_j) = \cup_{j \in \Z}  f(A_j)$
	
	\item $f^{-1}(\cup_{j \in \Z} B_j) = \cup_{j \in \Z}  f^{-1}(B_j)$
	
	\item $f(\cap_{j \in \Z} A_j) \subset \cap_{j \in \Z}  f(A_j)$, where equality holds if $f$ is injective.
	
	\item $f^{-1}(\cap_{j \in \Z} B_j) = \cap_{j \in \Z}  f^{-1}(B_j)$ always
	
	\end{enumerate}


\item Let $C$ be a relation on a set $A$. For a subset $A_0\subset A$, the \textbf{restriction} of $C$ to $A_0$ is the relation defined by the subset $D:=C\cap (A_0\times A_0)$.
	\begin{enumerate}
	\item For $a,b\in A$, show that $aDb$ if and only if $a,b\in A_0$ and $aCb$.
	
	\item Show that if $C$ is an equivalence relation on $A$, then $D$ is an equivalence relation on $A_0$.
	
	\item Show that if $C$ is an order relation on $A$, then $D$ is an order relation on $A_0$.
	
	\item Show that if $C$ is a partial order relation on $A$, then $D$ is a partial order relation on $A_0$.
	\end{enumerate}
	
\item Let $f: A \rightarrow B$ be onto.  Define a relation on $A$ by setting $a \sim a'$ if $f(a) = f(a')$.  Show that $\sim$ is an equivalence relation.  Furthermore, show that there is a bijection between the equivalence classes of $\sim$ and $B$.
	
\item We say two sets $A$ and $B$ have the same \textbf{cardinality} if there is a bijection of $A$ with $B$. In this exercise, you will prove the \emph{Schr\"oder--Bernstein Theorem}: if there exist injections $f\colon A\to B$ and $g\colon B\to A$, then $A$ and $B$ have the same cardinality.
	\begin{enumerate}
	\item Suppose $C\subset A$ and that there is an injection $f\colon A\to C$. Define $A_1:=A$, $C_1:=C$, and for $n>1$ recursively define $A_n:=f(A_{n-1})$ and $C_n:=f(C_{n-1})$. Show that
		\[
			A_1\supset C_1 \supset A_2 \supset C_2 \supset A_3\supset \cdots
		\]
	and that $f(A_n\setminus C_n)=A_{n+1}\setminus C_{n+1}$ for all $n\in \N$.	
	
	\item Using the notation from the previous part, show that $h\colon A\to C$ defined by
		\[
			h(x):=\begin{cases} f(x) & \text{if $x\in A_n\setminus C_n$ for some $n\in \N$}\\
			 x & \text{otherwise} \end{cases}
		\]
	is a bijection. [\textbf{Hint:} draw a picture.]
	
	\item Prove the Schr\"oder--Bernstein Theorem.
	\end{enumerate}
	
	
\end{enumerate}


	


\end{document}​