\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{9: Equivalence Relations}{Due Friday, Week 5}

Hey!  These problems are slightly harder than normal.  Do \textbf{two} of the \textbf{five} problems below!

\begin{enumerate}
\item Consider the collection of all polynomials with real-valued coefficients, which we denote as $\mathbb{R}[x]$.  Take any polynomial $h(x) \in \mathbb{R}[x]$.  

Consider the following relation:
\begin{align*}
\equiv_h := \{ (f(x), g(x)) ~|~ \exists q(x) \in \mathbb{R}[x], f(x) - g(x) = q(x)h(x) \}.
\end{align*}
For example, if $h(x) = x-2$, we would say that $f(x) = x^2 - 4$ is equivalent to $g(x) = x^2 - 3x  +2$, because 
\begin{align*}
f(x) - g(x) = x^2 - 4  - (x^2 - 3x +2) = 3x - 6 = 3(x-2) = 3h(x).
\end{align*}
Prove that $\equiv_h$ is an equivalence relation on the collection of all polynomials.
\item Let's continue to work with the equivalence relation $\equiv_h$ defined in the problem above.  Denote any equivalence class containing a polynomial $f(x)$ as $[f(x)]_h$: this represents the collection of all of the polynomials equivalent to $f(x)$ under $\equiv_h$.

We can define $+, \cdot $ on these equivalence classes as follows: $[f(x)]_h + [g(x)]_h = [f(x)+g(x)]_h$, and $[f(x)]_h \cdot [g(x)]_h = [f(x)\cdot g(x)]_h$.

Set $h(x) = x^2  + 1$ for this problem, and let $\left( \mathbb{R}[x] / h(x)\right)$ denote the collection of equivalence classes for $\mathbb{R}[x]$ under $h$.
\begin{enumerate}
\item Show that $[x]_h \cdot [x]_h + [1]_h = [0]_h.$
\item Consider the map $\varphi: \mathbb{C} \to \left( \mathbb{R}[x] / h(x)\right)$ defined by $h(a+ib) = [a+bx]_h$.  Is $\varphi$ a bijection?  Does $\varphi$ preserve addition and multiplication: in other words, for any $a,b,c,d \in \mathbb{R}$, do we have
\begin{itemize}
\item $\varphi((a+ib) + (c+id)) = [a+bx]_h + [c+dx]_h$, and
\item  $\varphi((a+ib) \cdot (c+id)) = [a+bx]_h \cdot [c+dx]_h$?
\end{itemize} 
\end{enumerate}

\item There are two possible equivalence relations on the two-element set $\{1,2\}$:
\begin{itemize}
\item The relation $\sim_A$ that says that $1 \sim_A 1$ and $2 \sim_A 2$ are true, and that $1 \sim_A 2$ and $2 \sim_A 1$ are false.
\item The relation $\sim_A$ that says that $1 \sim_A 1$, $2 \sim_A 1$, $1 \sim_A 2$, and $2 \sim_A 2$ are all true.
\end{itemize}
For any $n$, let $E_n$ denote all of the possible equivalence classes on the set $\{1,2,\ldots n\}$.  Find a recurrence relation for $E_n$.  (For example: we defined the Fibonacci numbers recursively via the equation $f_{n+1} = f_n + f_{n-1}$.  In this problem, you are being asked to create an recursive expression for $E_n$; i.e. a way to express $E_n$ in terms of earlier terms.)
\item Let $X$ be some set, and $S \subseteq X \times X$ be a relation on the set $X$.
\begin{enumerate}
\item Prove that there is some equivalence relation $R \subset X \times X$ such that $S \subseteq R$.  (If you're not comfortable with the subset notation: this is a relation $R$ with the property that if $xSy$, then $xRy$ must also hold.)
\item Take the collection of all equivalence relations $T$ such that $T \supseteq S$.  Let $R_S = \bigcap_{T} T$ denote the intersection of all of these equivalence relations: in other words, $R_S$ is a relation where $xR_Sy$ holds only if $xTy$ holds for each $T$.  

Show that $R$ is an equivalence relation.  (We think of $R$ as the equivalence relation \textbf{generated} by $S$.)
\item Consider the set $X = \{1,2,3,4,5\}$ and relation $S = \{(1,2), (3,4)\}$: i.e. $S$ thinks that $1S2, 3S4$ are both true, and that all other relations are false.  

Find the equivalence relation $R_S$ generated by $S$.
\end{enumerate}
\item\begin{enumerate}
\item Give an equivalence relation $\sim$ on $\mathbb{R}$ such that the equivalence class of any element is size 4.
\item Give an equivalence relation $\sim$ on $\mathbb{R}$ such that there are infinitely many equivalence classes of $\mathbb{R}$ under $\sim$, and each equivalence class has the same cardinality as $\mathbb{R}$.
\end{enumerate}
\end{enumerate}
\end{document}