\documentclass{article}
\input{../notes/preamble.tex}
\usepackage{url}
\title{Assignment 4}
\date{Friday June 8, 2012}
\newcommand{\df}{\textbf}
\begin{document}
\maketitle
\section{Set Theory}
This material is intended to be completed Tuesday June 5th. Here will fully cement our knowledge of basic operations on sets.
\begin{prob}
Prove or disprove the following:
\begin{enumerate}
\item $(A\minus C) \cup (B\minus C) = (A\cup B)\minus C$
\item $(A \minus B) \cap C = A \minus (B\cap C)$
\end{enumerate}
\end{prob}
\begin{prob}
\mbox{}
\begin{enumerate}
\item Prove:
\[
\bigcap_{\alpha\in(A\cup B)} A_\alpha \sbs \big(\bigcap_{\alpha\in A} A_\alpha\big) \cup \big(\bigcap_{\alpha\in B} A_\alpha\big)
\]
\item Show equality need not hold.
\end{enumerate}
\end{prob}
\begin{prob}
Let $A$ and $B$ be sets.
\begin{enumerate}
\item Prove \[\wp(A)\cup\wp(B) \sbs \wp(A\cup B)\]
\item Show that equality need not hold.
\end{enumerate}
\end{prob}
\section{Relations}
\subsection{Basics}
This material is intended to be completed on Wednesday June 6th.
\begin{prob}
For each of the following relations, determine if they are reflexive, symmetric, and transitive; justify your answers
\begin{enumerate}
\item Define $R$ on $\R$ such that $aRb$ if and only if $ab = 0$.
\item Define $S$ on $\R$ such that $aSb$ if and only if $ab \neq 0$.
\item Define $d$ on $\R$ such that $d(a,b)$ if and only if $|a-b|<\frac{1}{2}$.
\item Define $T$ on $\Z$ such that $nTm$ if and only if $n-m$ is even.
\end{enumerate}
\end{prob}
\subsection{Equivalence Relations}
This section is intended to be completed on Wednesday June 6th. Here we will take a look at equivalence relations.
Recall that we proved that a equivalence relation yields a partition of \df{equivalence classes}. That is, if $\sim$ is an equivalence relation on $S$, then for every element $a\in S$ we have a corresponding equivalence class \[[a]_\sim = \set{ b \in S \mid a\sim b }\].
\begin{prob}
In this problem we prove the converse of the above; that is, we prove that given a partition of a set we can ``read off'' an equivalence relation.
Let $S$ be a set, and $P$ a partition of $S$. Recall that $P$ partitions $S$ if and only if
\begin{itemize}
\item $A\in P \implies A\in\wp(S)$ ie. $P$ is a set of subsets of $A$.
\item $A,B\in P \implies A\cap B=\emptyset$, ie. every two members of the partition are disjoint.
\item $x\in S \implies \E A\in P \st x\in P$, ie. every member of $S$ is in some element of the partition.
\end{itemize}
\begin{enumerate}
\item Give a partition of the set $\s{1,2,3,4,5,6,7,8,9,10}$.
\item Fix $S$ and $P$ as above. Define a relation $\sim$ on $S$ by $a\sim b$ if and only if there is a $A\in P$ such that $a,b\in A$. Prove that the relation is an equivalence relation.
\item Consider the partition of $\N$ into the following $3$ sets:
\begin{align*}
\s{ 0,3,6,9,12,15,\ldots } \\
\s{ 1,4,7,10,13,16,\ldots } \\
\s{ 2,5,8,11,14,17,\ldots}
\end{align*}
Take $\sim$ to be the corresponding relation that you get from this partition (from part 2). Give a necessary and sufficient condition for deciding if $a\sim b$ that does not refer to the partition. (ie. $a\sim b$ if and only if $\ldots$)
\end{enumerate}
\end{prob}
\begin{prob}
Prove that each of the following are equivalence relations:
\begin{enumerate}
\item Define $\sim$ on $\Z^+ \times \Z^+$ by $(a,b) \sim (c,d)$ if and only if $ad = bc$.
\item Define $\iso$ on $\R$ by $a\iso b$ if and only if $\frac{a}{b}\in \Q$.
\end{enumerate}
\end{prob}
\subsection{Preview of Modular Arithmetic}
This material is intended to be completed on Thursday June 7th. This is a preview section. Here, we will preview Modular Arithmetic, which we will talk about in great detail on Friday.
\begin{prob}
Prove
\[
\A n,d\in \N \st \E r,q\in\N \stt (n = dq + r) \oand (0\leq r < n)
\]
{\it Hint: Take $d$ arbitrary and do induction on $n$; consider cases: what if $d$ is smaller than $n$? What if it is larger? }
\end{prob}
Tomorrow in class we will prove that $r$ and $d$ are \df{unique}
\begin{prob}
Find the $r$ and $q$ for the given $n$ and $d$.
\begin{enumerate}
\item $n=5$, $d=3$.
\item $n=123$, $d=6$.
\item $n=10^{10}$, $d=2$.
\end{enumerate}
\end{prob}
\begin{dfn}
For a fixed $n$, the $q$ in the theorem above is call the \df{quotient}, the $d$ the \df{divisor}, and $r$ the \df{remainder}. So, this says that any given a number and a divisor $d$, there is a unique quotient and remainder.
\end{dfn}
\begin{prob}
Fix $n\in\N$. Define a relation $\sim$ where $p\sim q$ if and only if $p$ and $q$ have the same remainder when you divide by $n$. Prove this is an equivalence relation. Moreover, determine how many equivalence classes does this relation have (this will depend on $n$ of course) and prove it.
\end{prob}
\begin{prob}
What are the equivalence classes in the above defined relation when $n=2$?
\end{prob}
\end{document}