\documentclass[letterpaper,12pt]{article}

\usepackage{amsfonts,amssymb,amsmath,amsthm,txfonts,pxfonts,mathrsfs,fullpage,enumitem}
\usepackage{xcolor}

\pagestyle{empty}
\begin{document} 

\begin{center}\textbf{Problem Set 3 \hspace{.7in} Foundations \hspace{.7in} Due 9/23/19} \end{center}

\noindent Five of these problems will be graded (our choice, not yours!), with each problem worth 4 points.  Clear and complete justification is required for full credit.  You are welcome to discuss these problems with anyone and everyone, but must write up your own final submission without reference to any sources other than the textbook and instructor. 

\begin{enumerate}
\item $\sqrt{3}$ is irrational.
\item The product of a non-zero rational and an irrational number is irrational.
\item Critique the following proof:\\
Proposition: If $2 \mid p^2$ then $2 \mid p$.\\
Proof: Assume $2\nmid p$, i.e. $p \neq 2n,  \exists n \in \mathbb{Z}$.  So $p$ must be odd.  $\forall m \in \mathbb{Z}$, $p=2m+1$.  Now $p^2=(2m+1)^2=4m^2+4m+1$ is odd because of the +1 and not even, so $2 \nmid p^2$.
\item Consider the formula $1+2+3+...+ n = \frac{n^2+n+1}{2}$.
\begin{enumerate}
	\item Write the formula in sigma notation.
	\item Show that if this formula works for $n = k$, then it also must work for $n = k + 1$.
	\item Explain why mathematical induction does not prove that this formula is true for all $n \in \mathbb N$.
\end{enumerate}
\end{enumerate}
\vspace{.25in}
The Fibonacci numbers are defined by the two-term recurrence relationship
\[F_1=1, \enspace F_2=1, \enspace F_{n+2}=F_{n+1}+F_n \enspace \mathrm{for} \enspace n \in \mathbb{Z}^+\]
\begin{enumerate} \setcounter{enumi}{4}
\item Find $F_3$ through $F_{10}$.
\item $F_1+F_2+...+F_n=F_{n+2}-1$ for every $n \in \mathbb{Z}^+$.

\vspace{.25in}

\item Find $\mathcal{P}(\{a,b,c\})$.
\item If $A$ has $n$ elements, then $\mathcal{P}(A)$ has {$2^n$} elements. [Hint: Induction!]
\item Score at least 7 out of 8 on the Set Theory Gateway on WeBWorK.
\item For any sets $A$ and $B$, $(A \bigcup B)' = A' \bigcap B'$. 
\item For any sets $A, B$, and $C$, $A \bigcup (B \bigcap C) = (A \bigcup B) \bigcap (A \bigcup C)$. 
\item Show that $(A - C) \cap B) \subseteq A \cap B$.

\end{enumerate}

\end{document}