\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}
