\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{amssymb,amsmath}
\usepackage[pdftex]{graphicx}
\usepackage{verbatim}
\topmargin = 0.1in \textwidth=5.7in \textheight=8.6in
\oddsidemargin = 0.2in \evensidemargin = 0.2in
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\begin{document}
\begin{center}
\large
COMPUTER SCIENCE 20, SPRING 2012 \\
DISCRETE MATHEMATICS FOR COMPUTER SCIENCE\\
\medskip
Class \#9 (Sets)
\end{center}
\paragraph{Homework, due in hard copy Monday 2/13/2012 at 10:10am}
\paragraph{Please write your TF's name on your homework, and list the names of any students with whom you collaborated.}
\begin{enumerate}
\item Prove that for any sets $A$, $B$, $C$, and $D$, if $A\times B$ and $C\times D$ are disjoint, then either $A$ and $C$ are disjoint or $B$ and $D$ are disjoint.\footnote{Credit: from Albert R. Meyer / MIT 6.042.}
\item If $A$ and $B$ are finite sets such that $|A| = m$ and $|B| = n$, then what are the minimum and maximum sizes of each of the following sets. (You don't have to write a formal proof for each one, but you do need to justify your work. How do you know you can attain your given minimum or maximum? Why can't each set be smaller or larger?)
\begin{enumerate}
\item $A \cup B$?
\item $A \cap B$?
\item $A - B$?
\item $\mathcal{P}(A)$?
\end{enumerate}
\begin{comment}
\item Define the new binary operation ``$\circ$'' as
\[
A\circ B:=(A\cup B)\setminus (A\cap B)
\]
for two sets $A$ and $B$. Think about what the operation ``$\circ$'' does to two sets $A$ and $B$; can you express it as a subset of $A\cup B$ with a logical connective? Let $S$ be some arbitrary set and define $G:=\mathcal{P}(S)$. Prove that:
\begin{enumerate}
\item $\forall A\, \forall B[(A\in G\wedge B\in G)\implies A\circ B\in G]$ or in longhand for any two sets $A$ and $B$ in $G$, $A\circ B$ is in $G$.
\item $\exists I\,\forall A[A\in G\implies (A\circ I=A \wedge I\in G) ]$ or in longhand there is some element of $G$, called $I$, such that for all sets $A$ in $G$, we have $A\circ I=A$.
\item $\forall A \,\exists B[ A\in G\implies ( B\in G \wedge A\circ B=\emptyset ) ]$ or in longhand for every element $A$ of $G$, there is a set in $G$, call it $B$, such that $A\circ B=\emptyset$.
\item $\forall A\,\forall B\,\forall C([A\in G\wedge B\in G\wedge C\in G]\implies[(A\circ B)\circ C=A\circ(B\circ C)])$ or in longhand for all sets $A$, $B$, and $C$ in $G$ we have $(A\circ B)\circ C=A\circ (B\circ C)$.\footnote{This terminology is not important for the course but after you complete this step you will have proved $(G,\circ)$ is a group!}
\item There exists (by calculating) $X\in \mathcal{P}(\mathbb{N})$ such that $\{1,2,4\}\circ X=\{3,4\}$.\footnote{Credit: from http://nrich.maths.org/.}
\end{enumerate}
\end{comment}
\end{enumerate}
\end{document}