\documentclass[12pt,reqno]{amsart}

\usepackage{enumerate}
\usepackage[margin =.75in]{geometry}
\usepackage{graphicx}
\usepackage{mathtools,amssymb,amsfonts,amsthm}
\usepackage{color}
\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}
\usepackage{comment}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{tabularx}
\usepackage{tikz}
\usetikzlibrary{petri}
\usetikzlibrary{trees}
\usepackage{url}
\usepackage[linktoc=all,colorlinks=true,linkcolor=blue,urlcolor=Purple,citecolor=cyan]{hyperref}
\usepackage[all]{hypcap}
\usepackage{newverbs}
\usepackage{euscript,mathrsfs}
\usepackage{pdfpages}
\usepackage{bbm}
%\usepackage[all]{xy}
%\usepackage{wrapfig}
%\usepackage{caption}
\raggedbottom
\allowdisplaybreaks

\specialcomment{lecturenotes}{}{}\excludecomment{lecturenotes}
\specialcomment{answers}{\sss \textsc{Answer: }}{\sss}
%\excludecomment{answers} % comment to compile with answers.
\specialcomment{remarks}{

\sss
\begingroup\color{blue}}
{\endgroup

\sss}
\specialcomment{inremarks}{\begingroup\color{blue}[}{]\endgroup}
\specialcomment{undefined}{\begingroup\color{orange}}{\endgroup}
\specialcomment{unjustified}{\begingroup\color{red}}{\endgroup}
\specialcomment{grammar}{\begingroup\color{Green}}{\endgroup}
\specialcomment{tex}{\begingroup\color{purple}}{\endgroup}

\newverbcommand{\cverb}{\small\color{purple}}{}
\newverbcommand{\everb}{\small\color{blue}}{}

\newcolumntype{L}[1]{>{\hsize=#1\hsize\raggedright\arraybackslash}X}
\newcolumntype{R}[1]{>{\hsize=#1\hsize\raggedleft\arraybackslash}X}
\newcolumntype{C}[1]{>{\hsize=#1\hsize\centering\arraybackslash}X}

\newcommand{\sss}{\vspace{2 mm}\noindent}
\newcommand{\lss}{\vspace{5 mm}\noindent}
\newcommand{\lls}{\vspace{7 mm}\noindent}
\newcommand\Tstrut{\rule{0pt}{2.6ex}}         % = `top' strut
\newcommand\Bstrut{\rule[-1ex]{0pt}{0pt}}   % = `bottom' strut
\newcommand{\ds}{\displaystyle}
\newcommand{\HR}{\vspace{5pt}\hrule height 1pt \vspace{5pt}}
\newcommand{\atext}[1]{\text{\quad #1 \quad }}

\newcommand{\ca}{\mathcal}
\newcommand{\fr}{\mathfrak}
\newcommand{\eucal}{\EuScript}
\newcommand{\scr}{\mathscr}
\newcommand{\bbf}{\mathbb{F}}
\newcommand{\bbn}{\mathbb{N}}
\newcommand{\bbr}{\mathbb{R}}
\newcommand{\bbq}{\mathbb{Q}}
\newcommand{\bbc}{\mathbb{C}}
\newcommand{\bbz}{\mathbb{Z}}
\newcommand{\bbp}{\mathbb{P}}
\newcommand{\bfa}{\mathbf{a}}
\newcommand{\bfb}{\mathbf{b}}
\newcommand{\bfc}{\mathbf{c}}
\newcommand{\bfu}{\mathbf{u}}
\newcommand{\bfv}{\mathbf{v}}
\newcommand{\bfx}{\mathbf{x}}

\newcommand{\inv}{^{-1}}
\newcommand{\into}{\hookrightarrow}
\newcommand{\onto}{\twoheadrightarrow}
\newcommand{\isom}{\overset{\sim}{\to}}
\renewcommand{\iff}{\Leftrightarrow}
\renewcommand{\implies}{\Rightarrow}
\renewcommand{\impliedby}{\Leftarrow}
\newcommand{\contradiction}{\Rightarrow\Leftarrow}

\newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\vmat}[1]{\begin{vmatrix}#1\end{vmatrix}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\Floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\vect}[1]{\langle #1 \rangle}

\newcommand{\Ad}{\operatorname{Ad}}
\newcommand{\ad}{\operatorname{ad}}
\newcommand{\disc}{\operatorname{disc}}
\newcommand{\domain}{\operatorname{domain}}
\newcommand{\Id}{\operatorname{Id}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\ind}{\operatorname{ind}}
\newcommand{\nul}{\operatorname{Nul}}
\newcommand{\nullity}{\operatorname{nullity}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\proj}{\operatorname{proj}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\red}{\operatorname{red}}
\newcommand{\bbref}{\operatorname{rref}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\trunc}{\operatorname{Trunc}}
\newcommand{\vspan}{\operatorname{span}}

%\theoremstyle{definition}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem*{prop*}{Proposition}
\newtheorem*{cor*}{Corollary}
\newtheorem*{lem*}{Lemma}
\newtheorem*{thm*}{Theorem}

\theoremstyle{definition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{defn}[thm]{Definition}
\newtheorem*{defn*}{Definition}
\newtheorem{claim}[thm]{Claim}
\newtheorem{example}[thm]{Example}
\newtheorem*{conj*}{Conjecture}
\newtheorem*{rd}{Read from the text}
\newenvironment{answer}{\noindent\textsc{Answer:}}{\hfill $\square$}

\newcounter{homework}
\newtheorem{hw}[homework]{Homework}
\newtheorem*{hw*}{Homework}

\newcounter{exercise}[homework]
\newtheorem{exer}[exercise]{$\star$ Exercise}
\newtheorem*{exer*}{$\star$ Exercise}
\renewcommand{\theexercise}{\arabic{homework}.\arabic{exercise}}

\newcommand{\truefalse}{\qquad\textbf{T}\qquad \textbf{F}\quad :\quad}

\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{remark*}{Remark}
\newtheorem{notation}[thm]{Notation}

\renewcommand{\thethm}{\arabic{thm}}
\renewcommand{\theexercise}{\arabic{exercise}}

\title{Math 2001 \\ Relations}

\begin{document}
\maketitle

\begin{defn}
Let $A$ be a set. The set $R$ is a \emph{relation} on $A$ if $R \subseteq A \times A$.
\end{defn}

\begin{defn}
Let $A$ be a set and let $R$ be a relation on $A$. Then
\begin{itemize}
\item $R$ is \emph{reflexive} if $(a,a) \in R$ for each $a \in A$;
\item $R$ is \emph{symmetric} if $(a,b) \in R$ implies that $(b,a) \in R$;
\item $R$ is \emph{transitive} if $(a,b) \in R$ and $(b,c) \in R$ implies that $(a,c) \in R$.
\end{itemize}
\end{defn}

\begin{example}
Let $A= \{a,b,c,d,e,f\}$ and consider the relation $R$ given by the following diagram.

\begin{center}
\begin{tikzpicture}[>=latex]
\foreach \x/\y/\z in {1/1/a,2/1/b,3/1/c,1/-1/d,2/-1/e,3/-1/f} {
	\draw (\x,.5*\y) node (\z) {$\bullet$} +(90*\y:.5) node {$\z$};
	}
\draw[->] (a) edge (e) (c) edge (f) (b) edge[bend right] (e) (e) edge[bend right] (b) (f) edge[loop right] (f) (d) edge (a) (c) edge[loop right] (c) (b) edge[loop right] (b);
\end{tikzpicture}
\end{center}

\begin{enumerate}[a.)]
\item What is $R$? (Write out the elements of $R$ in set notation.)
\vspace{1in}

\item What additional elements would have to be included for $R$ to be reflexive? (Feel free to draw them in as well.)

\begin{tikzpicture}[>=latex,scale=1.2]
\foreach \x/\y/\z in {1/1/a,2/1/b,3/1/c,1/-1/d,2/-1/e,3/-1/f} {
	\draw (\x,.5*\y) node (\z) {$\bullet$} +(90*\y:.5) node {$\z$};
	}
\draw[->] (a) edge (e) (c) edge (f) (b) edge[bend right] (e) (e) edge[bend right] (b) (f) edge[loop right] (f) (d) edge (a) (c) edge[loop right] (c) (b) edge[loop right] (b);
\end{tikzpicture}

\item What additional elements would have to be included for $R$ to be symmetric? 

\begin{tikzpicture}[>=latex,scale=1.2]
\foreach \x/\y/\z in {1/1/a,2/1/b,3/1/c,1/-1/d,2/-1/e,3/-1/f} {
	\draw (\x,.5*\y) node (\z) {$\bullet$} +(90*\y:.5) node {$\z$};
	}
\draw[->] (a) edge (e) (c) edge (f) (b) edge[bend right] (e) (e) edge[bend right] (b) (f) edge[loop right] (f) (d) edge (a) (c) edge[loop right] (c) (b) edge[loop right] (b);
\end{tikzpicture}

\item What additional elements would have to be included for $R$ to be transitive?

\begin{tikzpicture}[>=latex,scale=1.2]
\foreach \x/\y/\z in {1/1/a,2/1/b,3/1/c,1/-1/d,2/-1/e,3/-1/f} {
	\draw (\x,.5*\y) node (\z) {$\bullet$} +(90*\y:.5) node {$\z$};
	}
\draw[->] (a) edge (e) (c) edge (f) (b) edge[bend right] (e) (e) edge[bend right] (b) (f) edge[loop right] (f) (d) edge (a) (c) edge[loop right] (c) (b) edge[loop right] (b);
\end{tikzpicture}
\end{enumerate}
\end{example}

\begin{example} \label{ex:z rel}
Each of the following is a relation on $\bbz$: $=, \neq, \le, \mid, \nmid$. For each relation, determine whether it is reflexive, symmetric, and/or transitive. If a relation does not have a particular property, give an example illustrating why not.
\vspace{2in}
\end{example}

\begin{defn}
A relation $R$ is an \emph{equivalence relation} if it is reflexive, symmetric, and transitive.
\end{defn}

\begin{example}
Which of the relations in Example \ref{ex:z rel} are equivalence relations?
\vspace{10mm}
\end{example}

\begin{defn}
Let $A$ be a set, and let $R$ be an equivalence relation on $A$. For any $a \in A$, the \emph{equivalence class containing $a$} (denoted by $[a]$) is the set of all elements in $A$ that are related to $a$. That is,
\begin{align*}
[a] = \{b \in A : (a,b) \in R\}.
\end{align*}
\end{defn}

\begin{example}
Let $A = \bbz$, and let $R$ be the relation on $A$ defined by
\begin{align*}
R = \{(a,b) \in \bbz \times \bbz : a-b = 2c \text{ for some } c \in \bbz\}.
\end{align*}
Prove that $R$ is an equivalence relation on $\bbz$, then describe the equivalence classes.
\vspace{2in}
\end{example}

\begin{example}
Let $A = \bbz^2 - \{(0,0)\}$, and let $R$ be the relation on $A$ defined by 
\begin{align*}
R = \{((a,b), (c,d)) : ad-bc = 0\}.
\end{align*}
Prove that $R$ is an equivalence relation on $\bbz$, then describe the equivalence classes.
\end{example}

\end{document}