\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,enumerate}
\usepackage{fullpage}
\usepackage{color}
\newcommand{\st}{{\text{\huge {.}}}\;}
\newcounter{theproblem} \setcounter{theproblem}{1}
\newenvironment{problem}[1][]
{\noindent{{\color{blue}\large\bf
\arabic{theproblem}. #1} \stepcounter{theproblem}\vspace{0.3cm}}\\}
{\vspace{0.5cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}\newpage}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\noindent{\color{blue}{\Large\bf Homework 5 \hfill 21-127 Concepts of Math \hfill due 10.11.2012}\\
\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Assignment begins here! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\color{blue}\large\bf Name:} % WRITE YOUR NAME HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Andrew ID:} % WRITE YOUR ANDREW ID HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Section:} % WRITE YOUR RECITATION SECTION HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Collaborators:} % LIST ANYONE YOU WORKED WITH HERE
\vspace{0.3cm}\\
{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
\begin{problem}[Reflexive $\neq$ Irrelevant (10 pts)]
What is wrong with following ``proof'' that the symmetric and transitive properties imply the reflexive property, rendering the reflexive property useless?
\begin{quote}
Let $A$ be a non-empty set. Let $R$ be a relation on $A$.

Suppose $R$ is symmetric and transitive. We will show $R$ is reflexive.

Let $x\in A$ be arbitrary and fixed. Define the set $T$ to be
\[ \{y\in A\mid (x,y)\in R\} \]
Let $y\in T$ be given. Thus, $(x,y)\in R$.

Since $R$ is symmetric, we can deduce $(y,x)\in R$.

Since $R$ is transitive, and $(x,y)\in R$ and $(y,x)\in R$, we deduce that $(x,x)\in R$.

Since $x$ was arbitrary, we have shown that the reflexive property holds.
\end{quote}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Recursive Threequence (15 pts)]
Define the recursive sequence $a_n$ by setting
\begin{align*}
a_1 &=1\\
a_2 &= 8\\
a_n &= a_{n-1}+2a_{n-2}\qquad\text{ for }n\geq 3
\end{align*}
Prove, by induction, that
\[ \forall n\in\mathbb{N}\st\;a_n=3\cdot 2^{n-1}+2\cdot(-1)^n\]
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Evens Are Oddly Periodic (20 pts)]
Consider the Fibonacci numbers, defined by
\begin{align*}
f_0 &= 0\\
f_1 &= 1\\
f_n &= f_{n-1}+f_{n-2}\qquad\text{ for }n\geq 2
\end{align*}
Prove, by induction, that
\[ \forall n\in\mathbb{N}\st\; f_n\text{ is even }\;\iff\; 3\mid n\]
\vspace{0.2cm}

\noindent (If you want to define a slightly different statement and prove that by induction, that is fine; just be sure to explain why what you prove implies the claim given above.)
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Relations (20 pts)]
Consider the set $A=\{1,2,3\}$. For each of the following relations, defined on $A$ or $\mathcal{P}(A)$ as specified, decide whether it is (i) reflexive, (ii) symmetric, (iii) transitive, (iv) anti-symmetric.\vspace{0.2cm}\\
Not much justification is required, just a {\sf Yes} or {\sf No} and a sentence or two.
\begin{enumerate}[{\color{blue}\bf(a)}]
\item $R_a$ on $A$ defined by $R_a=\{\;(1,1),(1,2),(2,1),(2,2),(3,3)\;\}$ 
\item $R_b$ on $A$ defined by $R_b=\{\;(1,1),(1,2),(2,2),(2,3),(3,3)\;\}$
\item $R_c$ on $\mathcal{P}(A)$ defined by $\forall S,T\in\mathcal{P}(A)\st (S,T)\in R_c\;\iff\; S\cap T=\varnothing$
\item $R_d$ on $\mathcal{P}(A)$ defined by $\forall S,T\in\mathcal{P}(A)\st (S,T)\in R_d\;\iff\; S\cap T\neq\varnothing$
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Equivalent Equivalences (15 pts)]
Define the relation $\sim$ on $\mathbb{Z}$ by saying
\[ \forall x,y\in\mathbb{Z}\st\; x\sim y\;\iff\; 3\mid x+2y\]
(Remember that ``$\mid$'' means ``divides'' in this context. Be sure to use the formal definition; ask me if you need a reminder of what that is.)
\begin{enumerate}[{\color{blue}\bf(a)}]
\item Prove that $\sim$ is reflexive.
\item Prove that $\sim$ is symmetric.
\item Prove that $\sim$ is transitive.
\item{\bf\color{blue}[Bonus]} Describe the sets $[0]_\sim$, $[1]_\sim$, $[2]_\sim$ using set-builder notation.\vspace{0.2cm}\\
Why is $[0]_\sim=[3]_\sim$? \quad (Hint: There is a very short answer.)
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Do Your Part(ition) (20 pts)]
In this problem, you will prove the converse of the theorem we saw in class about equivalence classes and partitions. Specifically, you will prove the following:\vspace{0.2cm}\\
{\bf Theorem:} Let $S$ be a set and let $R$ be an equivalence relation on $S$. The set of equivalence classes $S/R$ forms a {\bf partition} of $S$.\vspace{0.3cm}\\
Remember that we use the notation $[x]_R$ to mean the {\bf equivalence class corresponding to $x$}, and it is the set of all elements of $S$ that are related to $x$; that is,
\[ [x]_R=\{y\in S\mid (x,y)\in R\} \]
Throughout the parts of this problem, we are assuming that $S$ is a set and $R$ is an equivalence relation on $S$, so that $R$ is reflexive, symmetric, and transitive.
\begin{enumerate}[{\color{blue}\bf(a)}]
\item Let $x\in S$. Show that $x\in[x]_R$.
\item Let $x,y\in S$. Suppose $x\neq y$, and suppose that $(x,y)\in R$. Show that $[x]_R=[y]_R$.\vspace{0.2cm}\\
({\bf Hint:} Use transitivity. You'll need it {\it twice}.)
\item Let $x,y\in S$. Suppose $x\neq y$, and suppose that $(x,y)\notin R$. Show that $[x]_R\cap [y]_R=\varnothing$.\vspace{0.2cm}\\
({\bf Hint:} Use a contradiction argument.)
\item{\bf\color{blue}[Bonus]} Show why this has proven the stated {\bf Theorem}.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Challenge Problem: Investigating Equivalence Relations (0 pts)]
\begin{enumerate}[{\color{blue}\bf(a)}]
\item Suppose $R$ and $S$ are equivalence relations on the set $A$. Suppose that $A/R=A/S$ (i.e. the set of equivalence classes under each equivalence relation are the same). Prove that, in fact, $R=S$.
\item Suppose $R$ and $S$ are equivalence relations on the set $A$. Must $R\cap S$ be an equivalence relation?
\item Suppose $R$ and $S$ are equivalence relations on the set $A$. Must $R\cup S$ be an equivalence relation?
\item Suppose $R$ and $S$ are equivalence relations on the set $A$. Define the {\it composition} of the relations to be
\[ S\circ R = \{ (x,z)\in A\times A\mid \exists y\in A\st (x,y)\in R\wedge (y,z)\in S\}\]
Must $S\circ R$ be an equivalence relation?
\item Suppose $R$ and $S$ are equivalence relations on the set $A$. Recall that $A/R$ and $A/S$ are {\it partitions} of $A$.\vspace{0.2cm}\\
We say that a partition $\mathcal{F}$ {\bf refines} a partition $\mathcal{G}$ if and only if
\[ \forall X\in\mathcal{F}\st\exists Y\in\mathcal{G}\st X\subseteq Y\]
Prove that
\[ R\subseteq S \;\iff\; A/R\text{ refines }A/S\]
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\end{document}