\documentclass[11pt,letterpaper]{article}
\usepackage{multicol}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
%\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 1\\
Due Tuesday, Sept 12}\end{large}\end{center}



\pagestyle{empty}

\begin{enumerate} 


\item Write the negation of the following statements and predicates. Assume that $x$ is a real number.

\begin{enumerate}
\item All cows are brown.
\item $x \leq 2.$
\item All cows are brown and eat grass.
\item $x$ is a prime number greater than 12.
\item There exists a cow that is black and doesn't eat grass.
\item Every square is a rectangle.
\item If $x$ is not an integer, then $x$ is negative.
\item Every nonzero integer is either negative or positive.
\item If $x$ is an odd integer, then $x^2$ will be a positive odd integer.
\item If it is cold or raining, I am wearing long sleeves or a jacket.

\end{enumerate}

\item 

\begin{enumerate}
\item Come up with two statements, $P$ and $Q$ such that $P \implies Q$ is true but $Q \implies P$ is false.

\item Using your statements from (a), write out ``If $\neg Q$, then $\neg P$.'' (\textit{``If $\neg Q$, then $\neg P$'' is called the \textbf{contrapositive} of ``If $P$, then $Q$.'' Notice that these two statements are equivalent!})
\end{enumerate}

\item 
\begin{enumerate}
\item Prove DeMorgan's second law: $$\neg (P \lor Q) \iff  (\neg P) \land (\neg Q).$$ You can use either the method we used in class and show that if the left side is true, the right side is true and if the left side is false then the right side is false (why is this sufficient?) or use the fact that two statements are equivalent if and only if they imply each other.

\item Using a truth table, verify both of DeMorgan's laws. Recall that the first law claims $$\neg (P \land Q) \iff  (\neg P) \lor (\neg Q).$$
\end{enumerate}

\item List all of the subsets of the following sets:

\begin{enumerate}
\item $\emptyset$
\item $\{1,2,3\}$
\item $\Big\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\Big\}$
\end{enumerate}


\item Let $A,$ $B$, and $C$ be sets. Prove that $(A\cap B) \cup C = A \cap (B \cup C)$ if and only if $C \subseteq A$.

\item Let $\mathcal{C}$ be a collection of sets.
\begin{enumerate}
\item Prove $$A \cup \left( \bigcap_{S \in \mathcal{C}} S\right) = \bigcap_{S \in \mathcal{C}}(A \cup S).$$
\item Give a similar formula for $$A \cap \left( \bigcup_{S \in \mathcal{C}} S\right)$$ and prove that your formula is correct.
\end{enumerate}

\item For each collection of sets $\mathcal{C}$, calculate $\displaystyle\bigcup_{S \in \mathcal{C}} S$ and $\displaystyle\bigcap_{S \in \mathcal{C}} S$.

\begin{enumerate}
\item $A_1 =$ the set of odd integers, \\$A_2 = $ the set of positive real numbers, \\$A_3 = $ the set of integers divisible by 3, and \\$\mathcal{C} = \{A_1, A_2, A_3\}$.
\item For each $i \in \mathbb{N}$, $S_i = \{x \in \mathbb{N} \mid x \geq i\}$, and $\mathcal{C} = \{S_i \mid i \in \mathbb{N}\}$.
\item For every $n \in \mathbb{Z}$, $T_n = \mathbb{Z} - \{n\}$, i.e. the set of integers other than $n$, and $\mathcal{C} = \{T_n \mid n \in \mathbb{Z} \}$.
\item $T_n$ is defined as in part (c), and $\mathcal{C} = \{T_n \mid n \textrm{ is a prime number} \}.$
\end{enumerate}

\item 
Prove DeMorgan's Laws for sets: $(A \cap B)' = A' \cup B'$ and $(A \cup B)' = A' \cap B'$. \\ \textit{(We will define the complement of a set, $A'$, on Thursday, Sept 7.)}

\item Choose one of DeMorgan's Laws from problem 8 and formulate and prove it for arbitrary unions or intersections (i.e. instead of a pair of sets, formulate it in terms of an arbitrary collection of sets $\mathcal{C}$.)



\end{enumerate}
\end{document}