\documentclass[12pt]{amsart}
\thispagestyle{empty}
\usepackage{tikz}


\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\lcm}{\mathrm{lcm}}


\begin{document}
\begin{center}
\begin{Large}
{\bf Math 2001 - Assignment 11}
\end{Large}

\bigskip
Due April 10, 2020
\end{center}

\thispagestyle{empty}

\bigskip

\begin{enumerate}
\item Prove or disprove that the following relations are reflexive, symmetric, antisymmetric,
 transitive. Which are equivalences, which partial orders?
\begin{enumerate}
\item $\neq$ on $\Z$
\item $\subseteq$ on the power set $P(A)$ of a set $A$
\end{enumerate}
  
\item
 Prove or disprove that the following relations are reflexive, symmetric, antisymmetric,
 transitive. Which are equivalences, which partial orders?
\begin{enumerate}
\item $|$ (divides) on $\N$
\item $R = \{ (x,y)\in\mathbb{R} \colon |x-y| \leq 1 \}$
\end{enumerate}

\item
 List the equivalence classes for these equivalence relations:
\begin{enumerate}
\item The relation $\sim$ on subsets $A,B$ of $\{1,2,3\}$ where $A \sim B$ if $|A|=|B|$.
\item $R = \{ (x,y)\in \Z \colon |x| = |y| \}$ on $\Z$
\end{enumerate}


\item
\begin{enumerate}  
\item
 Given finite sets $A$ and $B$. How many different relations are there from $A$ to $B$?
\item
 How many different equivalence relations are there on $A = \{1,2,3\}$?
 Describe them all by listing the partitions of $A$. 
\end{enumerate}

\item
 Let $\sim$ be an equivalence relation on a set $A$, let $a,b\in A$.
 Let $[a]$ denote the equivalence class of $a$ modulo $\sim$.
 Show that
 \[ a\not\sim b \text{ iff } [a]\cap[b] = \emptyset. \]

\item
\begin{enumerate}  
\item
 Give the tables for addition and multiplication for $\Z_6$.

\item
 Dividing by $[a]$ in $\Z_n$ means solving an equation $[a]\cdot[x] = [1]$ for $[x]$. 

 Solve $[8]\cdot [x] = [1]$ in $\Z_{37}$.

 Hint: Use the Euclidean algorithm to solve $8x \equiv 1 \mod 37$.
\end{enumerate}
\end{enumerate}
\end{document}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
