\documentclass[12pt]{amsart}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\topmargin}{0pt}
\setlength{\marginparsep}{0pt}
\setlength{\marginparwidth}{1in}

\newcommand{\ZZ}{\mathbf{Z}}
\newcommand{\NN}{\mathbf{N}}
\newcommand{\RR}{\mathbf{R}}
\newcommand{\QQ}{\mathbf{Q}}
\newcommand{\CC}{\mathbf{C}}

\newcommand{\on}{\operatorname}
\newcommand{\ra}{\rightarrow}

\author{Math 25}

\title{Homework 1  --- due Sep 26th}

\begin{document}

\maketitle

%\setcounter{section}{0}
\setlength{\baselineskip}{18pt}

There are three parts to this assignment (plus a fourth ``optional''
one which won't be graded). Please return the three parts \emph{separately}.

\section{Sets and maps}

\subsection{} Prove the following statements (here $X,Y$ and $Z$ are
three sets):
\begin{enumerate}
\item $(X \cap Y) \times Z = (X \times Z) \cap (Y \times Z)$;
\item $X \setminus (Y \cup Z) = (X \setminus Y) \cap (X \setminus Z)$;
\item $X \setminus (Y \cap Z) = (X \setminus Y) \cup (X \setminus Z)$.
\end{enumerate}

\subsection{} Let $f : A \ra B$ be a map and let $Y,Z$ be two subsets
of $B$. Prove the following:
\begin{enumerate}
\item $f^{-1}(Y \cap Z) = f^{-1}(Y) \cap f^{-1}(Z)$;
\item $f^{-1}(Y \setminus Z) = f^{-1}(Y) \setminus f^{-1}(Z)$ if $Z
  \subset Y$.
\end{enumerate}

\subsection{} Let $f : A \ra B$ be a map and let $Y,Z$ be two subsets
of $A$. Determine whether the following are true or false (give
  a proof or a counterexample):
\begin{enumerate}
\item $f(Y \cup Z) = f(Y) \cup f(Z)$;
\item $f(Y \cap Z) = f(Y) \cap f(Z)$.
\end{enumerate}
If you're looking for a counterexample, look for something simple,
for example sets with only a few elements.

\subsection{} If $A,B$ are two sets, let $A^B$ be the set of all maps
$f:B \ra A$. Construct a bijection between $A^{B \times C}$ and
$(A^B)^C$.

\section{Finite sets}

\subsection{} Show that if $A$ and $B$ are finite sets, then
$\on{Card}(A^B)=\on{Card}(A)^{\on{Card}(B)}$. 

Note that this holds even if one of $A$ or $B$ is empty. Here is why
(the following is for your information, and will not be graded):
given two non-empty sets $A,B$, 
you can attach to a map $f:A \ra B$ its graph
$G(f) \subset A \times B = \{ (a,f(a))\ a \in A\}$. Show that a subset
$G
\subset A \times B$ is the graph of some map if and only if for any $a
\in A$, $\on{Card} ((\{a\} \times B) \cap G) = 1$. This definition of a
``map'' still makes sense if $A$ or $B$ is empty. 
How many maps are there from the empty set to itself?

\subsection{} \label{pascal}
Let $\binom{n}{k}$ be the number of parts of
$\{1,\cdots,n\}$ which have exactly $k$ elements. Prove that
\[ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}, \]
by constructing bijections between certain sets.
Show also that
\[ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\cdots+\binom{k-1}{k-1}
\qquad\text{and that}\qquad \binom{n}{k}=\frac{n!}{k!(n-k)!}. \]

\subsection{} Given $n, p \geq 1$, compute $\on{Card}\{
(x_1,\cdots,x_n) \in \NN^n,\ \sum_{i=1}^n x_i = p \}$.

Hint: let $h(n,p)$ be the above cardinal. What is $h(1,p)$?
Find a formula for $h(n,p)$ in terms of the $h(n-1,q)$ with $q \leq
p$ and use exercise \ref{pascal}.

\subsection{The marriage lemma, after H. Weyl} Let $W$ and $M$ be two
finite sets. To every $m \in M$ is associated a subset $W_m \subset
W$. Show that the following are equivalent:
\begin{enumerate}
\item there exists an injective map $f:M \ra W$ such that $f(m) \in
  W_m$ for every $m \in M$;
\item for every non-empty subset $X \subset M$, $\on{Card}(\cup_{m \in
  X} W_m) \geq \on{Card}(X)$.
\end{enumerate}
(recall that $\cup_{m \in X} W_m$ stands
for the set of $w \in W$ such that there exists $m \in X$ with $w
\in W_m$).

Conclusion: if there are men and women and if every man knows some of
the women, it is possible to marry each man to a woman he knows if and
only if for all $n$, any given $n$ men know at least $n$ women between each
other. 

\section{Denumerable sets and cardinals}

\subsection{} Finish the proof that if $A$ and $B$ are two denumerable
sets then so is $A \times B$.

\subsection{} Show that $\QQ$ is denumerable (construct an explicit
bijection between $\QQ$ and $\ZZ_{\geq 1}$).

\subsection{} Show that if $A$ is any set, then $\on{Card}(P(A)) =
\on{Card}(\{0,1\}^A)$. 

\subsection{} Let $E$ be an infinite set and let $D$ be a countable
subset, such that $E \setminus D$ is still infinite. Prove that
$\on{Card}(E) = \on{Card}(E \setminus D)$.

\subsection{} Let $A$ and $B$ be two sets such that there exist two
maps $f_i,f_s : A \ra B$ with $f_i$ injective and $f_s$
surjective. Show that $\on{Card}(A) = \on{Card}(B)$.

Hint: you will need to use the \emph{axiom of choice}: if $I$ is a set
and $\{E_i\}_{i \in I}$ is a collection of subsets of a set $E$
indexed by $I$ then there exists $f:I \ra E$ such that $f(i) \in E_i$
for all $i \in I$. Sounds obvious, doesn't it?

\section{Supplementary exercises}

These exercises are harder and will \emph{not} be graded. They are
good practice though (especially the first one).

\subsection{} 
The purpose of this exercise is to show that 
$\on{Card}(\NN) \neq \on{Card}(\RR)$.

\begin{enumerate}
\item Show that for any real number $0 \leq \alpha \leq 1$,
there exists a sequence $\{x_i\}_{i \geq 1}$ with $x_i \in \{0,1\}$
such that $\alpha=\sum_{i=1}^\infty x_i 2^{-i}$.

Hint: if $0 \leq \alpha \leq 1$, then either $0 \leq \alpha \leq 1/2$
or $0 \leq \alpha-1/2 \leq 1/2$. Suppose that you have $\{x_i\}_{1
  \leq i \leq n}$ such that $0 \leq \alpha - x_1 2^{-1} - \cdots -  x_n 2^{-n}
\leq 1/2^{n}$. Show that there exists $x_{n+1} \in \{0,1\}$ such
that $0 \leq \alpha - x_1 /2 - \cdots -  x_{n+1} 2^{-(n+1)}
\leq 1/2^{n+1}$.

\item Use this to define a surjective map $\{0,1\}^{\NN} \ra [0,1]$;

\item Show that the map $\{0,1\}^{\NN} \ra [0,1]$ which sends $\{x_i\}_{i
  \geq 1}$ to $\sum_{i=1}^\infty x_i 3^{-i}$ is injective;

\item Show that $\on{Card}(P(\NN)) = \on{Card}(\{0,1\}^{\NN}) =
\on{Card}([0,1]) = \on{Card}(\RR)$;

\item Show that $\on{Card}(\NN) \neq \on{Card}(\RR)$.
\end{enumerate}

\subsection{} Construct a map $f:\RR \ra P(\NN)$ such that:
\begin{enumerate}
\item for any $x \in \RR$, $f(x)$ is infinite;
\item for any $x \neq y \in \RR$, $f(x) \cap f(y)$ is finite.
\end{enumerate}

\subsection{Sperner's lemma} Let $A$ be a collection of elements of
$P(\{1,\cdots,n\})$ such that for any $X, Y \in A$, one has $X \not \subset Y$.
\begin{enumerate}
\item Show that $\sum_{X \in A} \on{Card}(X)!(n-\on{Card}(X))! \leq n!$;
\item prove Sperner's lemma: $\on{Card}(A) \leq \binom{n}{\lfloor n/2 \rfloor}$.
\end{enumerate}

\subsection{A theorem of \'E. Borel} Let $C(\RR,\RR)$ be the set of
continuous functions from $\RR$ to $\RR$. Show that
$\on{Card}(C(\RR,\RR)) = \on{Card}(\RR)$. 
\end{document}