\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}


\begin{document}

\homework{14: Review}{Due Monday, Week 9}

This set is different from other sets.  For one, it is due on \textbf{Monday}, week 9, instead of Friday, week 8!  This is because of Thanksgiving.  For another, this set isn't focused only on the material of the past week!  Instead, it's designed to function as a \textbf{review} of the quarter so far.  The idea here is to give you all a chance to practice some of the skills/problems that we worked on in earlier weeks, because (as you may have noticed!) they keep coming up in class!

Do \textbf{three} of the \textbf{six} problems below! 

\begin{enumerate}
\item Composing functions!
\begin{enumerate}
\item Suppose that $f_1, f_2, \ldots f_n$ are all injective functions from $\mathbb{R} \to \mathbb{R}$.  Prove that the composition
\begin{align*}
f_1 \circ f_2 \circ \ldots \circ f_n : \mathbb{R} \to \mathbb{R}
\end{align*}
is an injective function.
\item Suppose that $g_1, g_2, \ldots g_n$ are all surjective functions from $\mathbb{R} \to \mathbb{R}$.  Prove that the composition
\begin{align*}
g_1 \circ g_2 \circ \ldots \circ g_n : \mathbb{R} \to \mathbb{R}
\end{align*}
is a surjective function.
\end{enumerate}

\item In class, we claimed that the following five operations were the only ones we could perform with only a compass and straightedge:
\begin{itemize}
\item Given any two distinct points $A, B$, we can draw the line through both $A$ and $B$.
\item Given any two distinct points $A, B$, we can draw the circle centered at $A$ that passes through $B$.
\item Given any two lines $l_1, l_2$ that intersect at some unique point, we can label that point of intersection.
\item Given any two circles $C_1, C_2$ that intersect at one or two points, we can label those points of intersection.
\item Given any circle $C$ and line $l$ that intersect at one or two points, we can label those points of intersection.
\end{itemize}
However, another natural operation that you might want to think a compass can do is ``transfer'' lengths!  That is: suppose that your compass could stay open at some distance, after you place its two points on the plane!  This would let you ``transfer'' that length to somewhere else on your paper, and draw more circles of that radius.

Prove that you do not need to add this property to the list above!  That is, using only the five properties above, prove the following claim:
\begin{claim}
(``Non-Collapsing Compass:'')  Given any point $A$ and any two other points $B, C$, we can draw a circle around $A$ with radius equal to the distance between $B$ and $C$.  (In other words, we can ``transfer'' the circle centered at $B$ through $C$ over to $A$!)
\end{claim}
\item Righting wrongs!  To answer this problem,
\begin{enumerate}
\item Go through your old HW and quizzes!  
\item Find \textbf{one} problems that you attempted, but did not get full credit on.  (I.e. 0 or .5 scores on attempted work.)  You cannot use a problem here that you have already retried on the earlier resubmission set.
\item Attach your old work (you should have it still in LaTeX!)
\item Attach a paragraph explaining why your old attempt didn't work / your proof was flawed / etc.
\item Then, \textbf{fix} your problem by attaching a new and correct solution!
\end{enumerate}
You need all of the parts above to receive credit here.
\item Define the \textbf{complement} of any set $X \subseteq \mathbb{R}$ as the following:
\begin{align*}
X^c := \{a \in \mathbb{R} ~|~ a \notin X\}.
\end{align*}
Let $A, B$ be subsets of $\mathbb{R}$.  Show that the following three statements are \textbf{equivalent}: that is, show that if any one of them holds, then the others must hold as well!  Use definitions here, and be clear about what you're doing.
\begin{enumerate}
\item $A \subseteq B$.
\item $A \cap B^c = \emptyset$.
\item $A^c \cup B = \mathbb{R}$.
\end{enumerate}
\item Prove or disprove the following statement: there is an equivalence relation $\sim$ on $\mathbb{R}$ such that the following two conditions hold.
\begin{itemize}
\item Every equivalence class of $\sim$ contains uncountably many elements.
\item Also, there are uncountably many distinct equivalence classes of elements of $\mathbb{R}$ under $\sim$.
\end{itemize}

\item Recall the following definition for a measure:
\begin{defn}
We say that any function $\mu$ that takes subsets of $\mathbb{R}$ to $\mathbb{R}^{\geq 0} \cup \{\infty\}$ is a \textbf{measure}\footnote{Strictly speaking, a Lebesgue measure.} if it satisfies the following properties:
\begin{itemize}
\item \textbf{Base cases}: $\mu(\emptyset) = 0$, $\mu([0,1]) = 1$.
\item \textbf{Translation}:  For any set $A$ that $\mu$ is defined on and any $x \in \mathbb{R}$, we have $\mu(A) = \mu(A+x)$.
\item \textbf{Scaling}:  For any set $A$ that $\mu$ is defined on and any $\lambda \in \mathbb{R}^+$, we have $\mu(\lambda \cdot A) = \lambda \cdot \mu(A)$.
\item \textbf{Subadditive}: If $A \subseteq B$ are sets that $\mu$ is defined on, then $\mu(A) \leq \mu(B)$.
\item \textbf{Additive}: If $\{A_i\}_{i=1}^\infty$ is a collection of disjoint sets that $\mu$ is defined on, then $\sum_{i=1}^\infty \mu(A_i) = \mu \left( \bigcup_{i=1}^n A_i \right)$.
\end{itemize}
Suppose you are given a function $\nu$ that satisfies all of the properties of being a measure, except that you aren't sure about the \textbf{scaling} property.  That is: you know that $\nu$ satisfies all of the other properties of being a measure, but you haven't been able to check if it satisfies scaling yet!

Suppose that you know that $\nu$ is defined on all of the closed intervals of $\mathbb{R}$.  You don't know what $\nu$ is yet on those intervals, but assume that it's defined on all of those closed intervals.

Prove that $\nu([a,b]) = b-a$ for any $a, b \in \mathbb{R}$.
\end{defn}
\end{enumerate}


\end{document}