\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{\eps}{\epsilon}
\newcommand{\N}{\mathbb{N}}

\newcommand{\ba}{\backslash}


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

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

Note: the first two problems are repurposed from HW5. You may have already completed these problems.
\begin{enumerate}

\item Given an integer $d$, define the set $A_d=\{n\in\N\ | \ n\hbox{ is divisible by }d\}$.
\begin{enumerate}
\item Suppose $p, q$ are distinct primes. Show that $A_p\cap A_q = A_{pq}$.
\item Suppose $a, b$ are integers with $a|b$. Prove that $A_b\subseteq A_a$.
\end{enumerate}

\item (*) Let $X, Y$ be sets in a universe $\Omega$. \begin{enumerate}
\item Prove that $X\subseteq Y$ if and only if $X\cap Y = X$.
\item Prove that $X\subseteq Y$ if and only if $X\cup Y = Y$.
\end{enumerate}

\item Prove Theorem 3 (De Morgan's Laws, v2) from the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Set%20Theory.pdf}{Set Theory Notes}.

\item Prove the following De Morgan's Law variant for relative complements:
\begin{quote}
Let $B, A_1, A_2, \dots, A_n$ be sets. Then
\begin{itemize}
\item $B\ba\left(\displaystyle\bigcup_{k=1}^n A_k\right) = \displaystyle\bigcap_{k=1}^n(B\ba A_k)$, and
\item $B\ba\left(\displaystyle\bigcap_{k=1}^n A_k\right) = \displaystyle\bigcup_{k=1}^n(B\ba A_k)$
\end{itemize}
\end{quote}

\item (*) Sets $A$ and $B$ are called {\it disjoint} if $A\cap B=\emptyset$. A collection of sets $A_1, A_2, \dots, A_n$ are called {\it pairwise disjoint} if $A_i\cap A_j=\emptyset$ for all $i\neq j$. 

Prove that for any sets $A, B$, $A\cup B = (A\ba B)\cup (B\ba A) \cup (A\cap B)$, and that the sets $A\ba B, B\ba A, A\cap B$ are pairwise disjoint.

\item Prove the following set identities.
\begin{enumerate} 
\item $A\ba B = A\cap B^c$
\item $A\cup (A\cap B)=A$
\item $A\cap (A\cup B)=A$
\item $(B\cup C)\ba A = (B\ba A)\cup (C\ba A)$
\item $(B\cap C)\ba A = (B\ba A)\cap (C\ba A)$
\end{enumerate}

\item (*) Use the Well-Ordering Principle to prove the Archimedean Property: For all $a, b\in\N$, there exists $n\in\N$ such that $na>b$.

\item For each of the following, give an example of a set in $\R$ that meets the description.
\begin{enumerate}
\item Has a supremum, but does not contain a maximum.
\item Contains both a maximum and a minimum.
\item Has neither supremum nor infimum.
\end{enumerate}

\item Use the definition of upper and lower bounds to explain why every number is both a lower and upper bound for $\emptyset$. As a result, we sometimes say that $\sup(\emptyset)=-\infty$ and $\inf(\emptyset)=\infty$; explain this convention.

\item Use the Well-Ordering Principle to prove that $\forall n\in\N$, $n!\leq n^n$.

\item Prove Parts 1, 4 of Proposition 1 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Functions.pdf}{Functions Notes}.

\item (*) Prove Proposition 2 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Functions.pdf}{Functions Notes}.

\item Which of the following function specifications are well-defined? If one is not well-defined, determine a modification to the specification that would rectify the issue.
\begin{enumerate}
\item $g:\Q\to\Q$ defined by $(x+1)g(x)=2$ for all $x$.
\item $f:\Q\to\R$ defined by $(x+\pi)f(x)=1$ for all $x$.
\item $h:\R\to\R$ defined by $h(x)=\sqrt{x}$.
\end{enumerate}

\item Let $f, g, h, \ell: \R\to \R$ be functions with the following specifications:
\[ f(x)=x+2;\quad g(x)=x^2; \quad h(x)=\frac{1}{x^2+1}; \quad \ell(x)=-x.\]
Write a specification, via a single equation, for each of the following:
\begin{enumerate}
\item $f\circ g$.
\item $g\circ f$.
\item $f\circ(g\circ(h\circ \ell))$.
\item $(f\circ g)\circ (h\circ \ell)$.
\end{enumerate}

\item (*) For each of the following functions, determine if it is injective, surjective, both, or neither. Prove that your answers are correct.

\begin{enumerate}
\item $f:\Z\to\N\cup\{0\}$, $f(x) = x^2$.
\item $g:\N\to\Z$, $g(x)=x^2$.
\item $h:\R\to\Z$, $h(x) = \lfloor x\rfloor$ 
\item $f: \N\to \Z$, $f(x) = \left\{\begin{array}{cl} \frac{x}{2} & x\hbox{ is even}\\ -\frac{x-1}{2} & x\hbox{ is odd}\end{array}\right.$
\end{enumerate}

\item Prove that if $f:X\to Y, g:Y\to Z$ are functions on sets $X, Y, Z$, and $g\circ f$ is injective, then $f$ is injective.

\item (*) Prove that if $f:X\to Y, g:Y\to Z$ are functions on sets $X, Y, Z$, and $g\circ f$ is surjective, then $g$ is surjective.
\end{enumerate}
\end{document}