\documentclass[11pt,letterpaper]{article}
\usepackage{multicol}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
%\usepackage{pstricks, pst-node, pst-plot}

\newcommand{\ds}{\displaystyle}
\newcommand{\bv}{\mathbf}
\newcommand{\lv}{\langle}
\newcommand{\rv}{\rangle}

\begin{document}


\begin{center}\begin{large}\textbf{Math 101 - Problem Set 2\\
Due Tuesday, Sept 19}\end{large}\end{center}



\pagestyle{empty}

\begin{enumerate} 

\item Let $A$ and $B$ be sets. Prove the following.

\begin {enumerate}
\item $A \cap (B-C) = (A \cap B) - (A \cap C)$
\item $A - (A-B ) = A \cap B$
\end{enumerate}

\item Given sets $A$, $B$, and $C$, express each of the following sets in terms of $A$, $B$, and $C$, using the symbols $\cup$, $\cap$, and $-$.
\begin{enumerate}
\item $D = \{x \mid x \in A \textrm{ and } (x \in B  \textrm{ or } x \in C ) \}$
\item $E = \{x \mid (x \in A \textrm{ and } x \in B)  \textrm{ or } x \in C  \}$
\item $F = \{x \mid x \in A \textrm{ and } (x \in B  \implies x \in C ) \}$
\end{enumerate}

\item Let $\mathcal{C}$ be a nonempty collection of sets. Prove the following facts about the power set.

\begin {enumerate}
\item $\displaystyle\bigcap_{X \in \mathcal{C}} \mathscr{P}(X) =  \mathscr{P}\left(\displaystyle\bigcap_{X \in \mathcal{C}}X\right)$
\item $\displaystyle\bigcup_{X \in \mathcal{C}} \mathscr{P}(X) \subseteq \mathscr{P}\left(\displaystyle\bigcup_{X \in \mathcal{C}}X\right)$
\end{enumerate}

\item Complete the following statement. ``If $A$ and $B$ are sets, then $\mathscr{P}(A) \cup \mathscr{P}(B) = \mathscr{P}(A \cup B)$ if and only if \ldots" Prove your assertion.

\item 
Again let $\mathcal{C}$ be a nonempty collection of sets.
\begin{enumerate}
\item Show that $\mathcal{C} \subseteq \mathscr{P}\left(\displaystyle\bigcup_{X \in \mathcal{C} } X \right)$.
\item Give necessary and sufficient conditions under which equality holds in part (a) (i.e. equality holds if and only if\ldots). Prove your assertion. 
\end{enumerate}

\item 
 Let $A$, $B$, $C$, and $D$ be sets.
 \begin{enumerate}

\item Assume $A \subseteq C$ and $B \subseteq D$. Show that $A \times B \subseteq C\times D$.

\item Give an example to show that if $X \subseteq C \times D$, it is not necessarily the case that $X = E \times F$ where $E \subseteq C$ and $F \subseteq D$, respectively.
\end{enumerate}

\item For each of the following subsets of $\mathbb{R} \times \mathbb{R}$, determine whether it is equal to the Cartesian product of two subsets of $\mathbb{R}$. If it is, express it as the Cartesian product of two subsets.
\begin{enumerate}
\item $\{(x,y) \mid x \in \mathbb{Z}\}$
\item $\{(x,y) \mid 0 <y \leq 1\}$
\item $\{(x,y) \mid y > x \}$
\item $\{(x,y) \mid x \notin \mathbb{Z} \textrm{ and } y \in \mathbb{Z} \}$
\end{enumerate}

\newpage
\item Let $A$, $B$, $X$, and $Y$ be sets. Prove the following equalities.

\begin{enumerate}
\item $(A \cap B) \times (X \cap Y) = (A \times X) \cap (B \times Y)$
\item $(A - B) \times X = (A \times X) - (B \times X)$
\end{enumerate}



\item For each of the three properties of equivalence relations (reflexivity, symmetry, and transitivity), come up with an example of a relation that does not have that property, but does have the other two.

\item Here is a ``proof" that every relation $C$ that is both symmetric and transitive is also reflexive: ``Since $C$ is symmetric, $aCb$ implies $bCa$. Since $C$ is transitive, $aCb$ and $bCa$ together imply $aCa$, as desired." Find the flaw in this argument. 

\end{enumerate}
\end{document}