\documentclass [ reqno, 11pt ] {amsart}

\usepackage [ margin = 1.5in ] {geometry}
%
%%%%%%%%%%%%%% 	hyperref
%\usepackage[bookmarks, 
%	citecolor=black,		%newblue
%	colorlinks=true,
%	linkcolor=black, 		%newblue
%	urlcolor=black,
%	pdftitle={ homework }, 
%	pdfauthor={Zach Norwood} ]{hyperref}
%%%%%%%%%%%%%

%\usepackage [mathlf,						% lining figures (not old-style) in math mode
%textlf,
%%onlytext
%] {MinionPro}

\newcommand\nakedfootnote[1]{%
  \begingroup
  \renewcommand\thefootnote{}\footnote{#1}%
  \addtocounter{footnote}{-1}%
  \endgroup
}

%\usepackage {amssymb} 		% conflicts with Minion
\usepackage {amsthm, setspace}
\usepackage {amsmath}
\usepackage [T1] {fontenc}
\usepackage[shortlabels]{enumitem}
%\usepackage{mathrsfs}	% for mathscr
\usepackage[activate=false]{microtype}
%\usepackage{tikz-cd}
%\usepackage{pgfplots}
%\usepackage{tikz}
%\tikzstyle{every node} = [circle, draw, fill, inner sep=0pt, minimum width=4pt]
\usepackage{stmaryrd}

\title{Math 3110: Homework 1}
%\author{Zach Norwood}
\date{Due Wednesday, 30 January 2019}

\theoremstyle {definition}
\newtheorem {problem} {Problem}


% % % % % % % % % % % % % % % % % % % % % % %
% below are macros from your input file(s)  %
% % % % % % % % % % % % % % % % % % % % % % %

\newcommand{\subs}{\subseteq}
\newcommand{\wo}{\setminus}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}

\begin{document}
\maketitle
\thispagestyle{empty}

\noindent
You will be graded on both the accuracy and the clarity of your solutions.
One purpose of the homework is to give you an opportunity to practice your proof-writing skills.

You are welcome\,---\,encouraged, even!\,---\,to collaborate on homework, but you should not 
copy solutions from any source, nor should you submit anything that you don't understand.

\begin{problem}
Which of the following statements are true?
Give a short explanation for each of your answers.
\begin{enumerate} [(a)]
 \item For every $n\in\mathbf{N}$, there is an integer $m\in\mathbf{N}$ such that $m>n$.
 \item For every $m\in\mathbf{N}$, there is an integer $n\in\mathbf{N}$ such that $m>n$.
 \item There is an $m\in\mathbf{N}$ such that for every $n\in\mathbf{N}$, $m\ge n$.
 \item There is an $n\in\mathbf{N}$ such that for every $m\in\mathbf{N}$, $m\ge n$.
 \item There is an $n\in\mathbf{R}$ such that for every $m\in\mathbf{R}$, $m\ge n$.
 \item For every pair $x<y$ of integers, there is an integer $z$ such that $x< z < y$.
 \item For every pair $x<y$ of real numbers, there is a real number $z$ such that $x< z < y$.
\end{enumerate}
\end{problem}

For a function $f\colon X\to Y$, we define the following two things:
\begin{enumerate} [(i)]
 \item The \textbf{image} of a set $A\subseteq X$ under $f$ is the set
  \begin{align*}
  f[A]	&=	\{ f(x) : x \in A \} \\
  	&=	\{ y\in Y : \text{there exists some $x\in A$ such that $y = f(x)$} \}.
  \end{align*}
 \item The \textbf{preimage} of a set $B\subs Y$ under $f$ is the set
  \[ f^{-1}(B) = \{ x\in X : f(x) \in B \}. \]
\end{enumerate}
\begin{problem}
Determine whether each of the following statements must be true for all functions $f\colon X\to Y$
and all sets $A_1,A_2\subs X$ and $B_1,B_2\subs Y$.
For true statements, give a proof. For false statements, give a \emph{specific counterexample},
i.e., specific functions and sets for which the statement fails.
\begin{enumerate} [(a)]
 \item $f[ A_1 \cup A_2 ] = f[A_1] \cup f[A_2]$.
 \item $f[ A_1 \cap A_2 ] = f[A_1] \cap f[A_2]$.
 \item $f^{-1}( A_1 \cup A_2 ) = f^{-1}(A_1) \cup f^{-1}(A_2)$.
 \item $f^{-1}( A_1 \cap A_2 ) = f^{-1}(A_1) \cap f^{-1}(A_2)$.
\end{enumerate} 
\end{problem}

\begin{problem}
 Suppose that $f\colon X\to Y$ and $g\colon Y\to X$ are functions and that the composite $g\circ f$ is
 the identity function $\operatorname{id}\colon X\to X$. (The identity function sends every element to itself:
 $\operatorname{id}(x) = x$.) Show that $f$ must be a one-to-one function and that $g$ must be an
 onto function.
\end{problem}

\begin{problem} 
\hfill
\begin{enumerate} [(a)]
 \item Prove that $\sqrt 3$ is irrational.
 \item What goes wrong when you try to adapt your argument from part (a) to show that $\sqrt4$ is 
 irrational (which is absurd)? Give a clear explanation using full sentences.
\end{enumerate}
\end{problem}

\begin{problem} [adapted from Abbott 1.2.13]
For $A\subs \R$ we'll use $A^c$ to denote the \textbf{complement} of $A$, i.e., $\R\wo A$.
 \begin{enumerate} [(a)]
 \addtolength{\itemsep}{4pt}
  \item Show the binary form of De Morgan's Law. That is,
  show that $(A\cap B)^c = A^c \cup B^c$ for any sets $A,B\subs\R$.
  \item Use induction to show the following more general version of De Morgan's Law:
  \[ (A_1 \cup A_2 \cup \cdots \cup A_n)^c = A_1^c \cap A_2^c \cap \cdots \cap A_n^c. \]
  \item It is tempting to appeal to induction to conclude that
  \begin{equation}	\label{eq:dm}	\tag{$\ast$}
  \left( \bigcup_{k=1}^\infty A_k \right)^c = \bigcap_{k=1}^\infty A_k^c,
  \end{equation}
  but induction does not apply here. Induction is used to prove that a particular
  statement holds for every nonnegative integer $n\in\N$, but this does not imply the validity
  of the infinite case. To illustrate this point, find an example of a collection of sets
  $B_1$, $B_2$, \dots where $\bigcap_{k=1}^n B_k\ne\emptyset$ is true for every $n\in\N$,
  yet $\bigcap_{k=1}^\infty B_k =\emptyset$.
  \item Nevertheless, the infinite version of De Morgan's Law in \eqref{eq:dm} is true.
  Provide a proof.
 \end{enumerate}
\end{problem}

\end{document}




































