\documentclass{article}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{color}
\usepackage{pdfsync}




\definecolor{plum}{rgb}{.5,0,1}
\newcommand{\blank}{\framebox(20,10){}}



\theoremstyle{definition}
\newtheorem{prob}{Problem}


\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}


\title{Problem Set 1: A Set-Theory diagnostic}
\date{Due: Tuesday, February 9}
\author{Your name:}





\begin{document}
\maketitle

\pagenumbering{gobble}

\begin{prob}[13]
What goes in the \, $\blank$ \, to make the strongest possible true statement? Your choices are on the right.
\end{prob}

\begin{tabular}{c c c c | c}
	(a) & $A \subset B \textrm{ and } B \subset C $& $\blank$ & $ A \subset (B \cup C)$ \quad & \quad $\Rightarrow \quad \Leftarrow \quad \Leftrightarrow \quad \textrm{ None}$ \\
	(b) & $A \subset B \textrm{ and } B \subset C $& $\blank$ &$ A \subset (B \cap C)$ \quad & \quad $\Rightarrow \quad \Leftarrow \quad \Leftrightarrow \quad \textrm{ None}$ \\
	(c) & $A \subset B \textrm{ or } B \subset C $& $\blank$ &$ A \subset (B \cup C)$ \quad & \quad $\Rightarrow \quad \Leftarrow \quad \Leftrightarrow \quad \textrm{ None}$ \\
	(d) & $A \subset B \textrm{ or } B \subset C $& $\blank$ &$ A \subset (B \cap C)$ \quad & \quad $\Rightarrow \quad \Leftarrow \quad \Leftrightarrow \quad \textrm{ None}$ \\
	(e) & $A \setminus  (A\setminus B) $& $\blank$ &$ B$ \quad & \quad $\subset \quad \supset \quad = \quad \textrm{ None}$ \\
	(f) & $A \setminus  (B\setminus A)  $& $\blank$ &$ A\setminus B $ \quad & \quad $\subset \quad \supset \quad = \quad \textrm{ None}$ \\
	(g) & $A \cap (B\setminus C) $& $\blank$ &$ (A \cap B) \setminus  (A \cap C) $ \quad & \quad $\subset \quad \supset \quad = \quad \textrm{ None}$ \\
	(h) & $A \cup (B\setminus C) $& $\blank$ &$ (A \cup B) \setminus  (A \cup C)$ \quad & \quad $\subset \quad \supset \quad = \quad \textrm{ None}$ \\
	(i) & $A \subset C \textrm{ and } B \subset D $& $\blank$ &$ (A \times B) \subset (C \times D)$ \quad & \quad $\Rightarrow \quad \Leftarrow \quad \Leftrightarrow \quad \textrm{ None}$ \\
	(j) & $(A \times B) \cup (C \times D) $& $\blank$ &$ (A \cup C) \times (B \cup D)$ \quad & \quad $\subset \quad \supset \quad = \quad \textrm{ None}$ \\
	(k) & $(A \times B) \cap (C \times D) $& $\blank$ &$ (A \cap C) \times (B \cap D)$ \quad & \quad $\subset \quad \supset \quad = \quad \textrm{ None}$ \\
	(l) & $A \times (B\setminus C) $& $\blank$ &$ (A \times B)\setminus  (A \times C)$ \quad & \quad $\subset \quad \supset \quad = \quad \textrm{ None}$ \\
	(m) & $(A \times B) \setminus  (C \times D) $& $\blank$ &$ (A\setminus C) \times (B \setminus D)$ \quad & \quad $\subset \quad \supset \quad = \quad \textrm{ None}$ 
\end{tabular}

\begin{prob}[4]
Complete the following as in the previous problem, assuming the collection $\mathcal{A}$ is nonempty.
\end{prob}

\begin{tabular}{c c c c | c}
	(n) & $x \in \bigcup_{A \in \mathcal{A}}A $ & $\blank$ & $x \in A$ for at least one $A \in \mathcal{A}$ \quad & \quad $\Rightarrow \quad \Leftarrow \quad \Leftrightarrow \quad \textrm{ None}$ \\
	(o) & $x \in \bigcup_{A \in \mathcal{A}}A $ & $\blank$ & $ x \in A$ for every $A \in \mathcal{A}$ \quad & \quad $\Rightarrow \quad \Leftarrow \quad \Leftrightarrow \quad \textrm{ None}$ \\
	(p) & $x \in \bigcap_{A \in \mathcal{A}}A $ & $\blank$ & $x \in A$ for at least one $A \in \mathcal{A}$ \quad & \quad $\Rightarrow \quad \Leftarrow \quad \Leftrightarrow \quad \textrm{ None}$ \\
	(q) & $x \in \bigcap_{A \in \mathcal{A}}A $ & $\blank$ & $ x \in A$ for every $A \in \mathcal{A}$ \quad & \quad $\Rightarrow \quad \Leftarrow \quad \Leftrightarrow \quad \textrm{ None}$ \\
\end{tabular}

\begin{prob}[6]
Let $f: A \to B$ and $g : B \to C$. Complete the following as in the previous problem. Note that ``injective" has been abbreviated ``inj." Similar abbreviations have been made for ``surjective" and ``bijective."
\end{prob}

\begin{tabular}{c c c c | c}
	(r) & $g \circ f$ is injective, then $f$ is & $\blank$ &  & \quad inj. \quad surj. \quad bij. \quad none. \\
	(s) & $g \circ f$ is injective, then $g$ is & $\blank$ & & \quad inj. \quad surj. \quad bij, \quad none.  \\
	(t) & $g \circ f$ is surjective, then $f$ is & $\blank$ & & \quad inj. \quad surj. \quad bij. \quad none.  \\
	(u) & $g \circ f$ is surjective, then $g$ is & $\blank$ & & \quad inj. \quad surj. \quad bij. \quad none.  \\
	(v) & \begin{tabular}{c} 
			Let $A_0 \subset A$. If $A_0 = f^{-1}(B_0)$ \\ for some $B_0 \subset B$, then $f^{-1}f(A_0)$ 
		\end{tabular}& $\blank$ & $A_0$ &  $\subset \quad \supset \quad = \quad \textrm{ None}$ \\
	(w) & \begin{tabular}{c} 
			Let $B_0 \subset B$. If $B_0 \subset f(A)$ \\ then $ff^{-1}(B_0)$ 
		\end{tabular} & $\blank$ & $B_0$ &  $\subset \quad \supset \quad = \quad \textrm{ None}$
	\end{tabular}

\begin{prob}[24] 
Let $A$ and $B$ be sets.
	\begin{enumerate}
		\item[a.] Consider the maps 
			\begin{align*}
				p_1: & A \times B \to A, \quad (a,b) \mapsto a \\
				p_2: & A \times B \to B, \quad (a,b) \mapsto b.
			\end{align*}
			Show that for any set $C$, the map 
				$$(A \times B)^{C}  \to A^C \times B^C, \quad f \mapsto (p_1 \circ f, p_2 \circ f)$$
			is a bijection. (\emph{Hint:} Define the inverse map.) Informally speaking, giving a map \emph{to a product} is ``the same thing" as giving a map \emph{to each factor}. 				This is called the \emph{universal property of the product}.
		\item[b.] Recall that $A \coprod B \equiv (A \times \{0 \}) \cup (B \times \{1\})$. Consider the maps
			\begin{align*}
				i_1: & A \to A \coprod B, \quad a \mapsto (a,0) \\
				i_2: & B \to A \coprod B, \quad b \mapsto (b,1).
			\end{align*}
			Show that for any set $C$, the map
				$$C^{A \coprod B} \to C^{A} \times C^{B}, \quad f \mapsto (f \circ i_1, f \circ i_2)$$
			is a bijection. Informally speaking, giving a map \emph{from a sum} is ``the same thing" as giving a map \emph{from each factor}. This is called the \emph{universal property of the sum}.
	\end{enumerate}
\end{prob}

\begin{prob}[23]
Let $A$ and $B$ be sets, and assume that $f: A \to B$ is injective, and $g: B \to A$ is injective. The goal of this problem is to show that this implies $A$ and $B$ are in bijection. For finite sets this may be intuitive (and if not, convince yourself as a warmup). This is a theorem which is commonly known as the {\color{plum} Cantor-Schr\"oder-Bernstein Theorem}, named after a few mathematicians that contributed to its proof / dissemination.

Let $h:A \to A$ be the composite map $g \circ f$. Inductively define a sequence of subsets $C_n \subset A$ for $n \in \N$, as follows:
$$C_0 = A \setminus g(B), \quad C_{n+1} = h(C_n).$$ Let $C$ be the union of all the $C_n$s: $$C = \bigcup_{n \in \N} C_n .$$
	\begin{enumerate}
		\item[a.] Show that $C = C_0 \cup h(C)$.
		\item[b.] Show that $A \setminus C =  g(B \setminus f(C))$.
		\item[c.] Use (b) to define a bijection between $A$ and $B$.
		\item[d.] Let $a$ and $b$ be real numbers with $a < b$. Show that there exists a bijection between $\R$ and the open interval $(a,b) = \{ x \in \R: a < x < b \}.$ (\emph{Hint:} You may use trigonometry.)
		\item[e.] Let $U$ be any subset of $\R$ containing an open interval. Use (c) and (d) to show that there exists a bijection between $U$ and $\R$.
	\end{enumerate}
\end{prob}



\end{document}