\documentclass{amsart}

% PACKAGES

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb,enumerate}
\usepackage{amsthm,stmaryrd}
\usepackage[all]{xy}
\usepackage{hyperref}
\usepackage{geometry}
\geometry{verbose,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
\usepackage{color}

\theoremstyle{definition}
\newtheorem{exer}{Exercise}

\newcommand{\bbr}{\mathbb{R}}
\newcommand{\bbc}{\mathbb{C}}
\newcommand{\bbz}{\mathbb{Z}}
\newcommand{\bbq}{\mathbb{Q}}
\newcommand{\bbn}{\mathbb{N}}

\begin{document}
\thispagestyle{empty}

\begin{flushright}
Introduction to Abstract Mathematics \\
MATH 310\\
Homework 9\\
Due Monday November 30
\end{flushright}

\noindent
Please show all your work and justify your answers.

\begin{exer}
	Use the method of minimum counterexample to prove that $3\mid (2^{2n} - 1)$ for every positive integer $n$.
\end{exer}

\begin{exer}
	For the relation $R = \{(x,y) \mid x\leq y\}$ defined on $\mathbb{N}$, what is $R^{-1}$?
\end{exer}

\begin{exer}
	A relation $R$ is defined on $\mathbb{Z}$ by $x\, R \, y$ if $x\cdot y\geq 0$. Prove or disprove the following:
	\begin{enumerate}[(a)]
	\item $R$ is reflexive.
	\item $R$ is symmetric.
	\item $R$ is transitive.
	\end{enumerate}
\end{exer}

\begin{exer}
	\begin{enumerate}[(a)]
	\item Let $R$ be the relation defined on $\mathbb{Z}$ by $a\, R\, b$ if $a+b$ is even. Prove that $R$ is an equivalence relation and determine the distinct equivalence classes.
	\item Suppose that ``even'' is replaced by ``odd'' in (a). Which of the properties reflexive, symmetric, and transitive does $R$ possess?
	\end{enumerate}
\end{exer}

\begin{exer}
	Let $H = \{2^m\mid m\in \mathbb{Z}\}$. A relation on $R$ is defined on the set $\mathbb{Q}^+$ of positive rational numbers by $a\, R \, b$ if $\frac{a}{b}\in H$.
	\begin{enumerate}[(a)]
	\item Prove that $R$ is an equivalence relation.
	\item Describe the elements in the equivalence class $[3]$.
	\end{enumerate}
\end{exer}

\begin{exer}
	A relation $R$ on a nonempty set $A$ is defined to be \textbf{circular} if whenever $x\, R\, y$ and $y\, R\, z$, then $z\, R\, x$ for all $x,y,z\in A$. Prove that a relation $R$ on $A$ is an equivalence relation if and only if $R$ is circular and reflexive.
\end{exer}

\begin{exer}
	Let $R$ be a relation on the set $\mathbb{N}$ by $a\, R\, b$ if either $a\mid 2b$ or $b\mid 2a$. Prove or disprove: $R$ is an equivalence relation.
\end{exer}

\begin{exer}
	Prove or disprove: The union of two equivalence relations on a nonempty set is an equivalence relation.
\end{exer}

\begin{exer}
	A relation $R$ is defined on $\mathbb{Z}$ by $a\, R\, b$ if $2a+2b \equiv 0\, (\operatorname{mod}\, 4)$. Prove that $R$ is an equivalence relation and determine the distinct equivalence classes.
\end{exer}

\begin{exer}
	Let $R$ be a relation defined on $\mathbb{Z}$ by $a\, R\, b$ if $a^2\equiv b^2\, (\operatorname{mod}\, 5)$. Prove that $R$ is an equivalence relation and determine the distinct equivalence classes.
\end{exer}


\end{document}















