\documentclass[11pt,oneside,reqno]{amsart}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
\usepackage{amsfonts, amscd, amssymb, amsthm, amsmath, multicol, enumerate}
\usepackage{pdfsync}%leaves makers for tex searching

%%%%% Margins %%%%% 
\setlength{\topmargin}{1in} %top/bot margins
\setlength{\oddsidemargin}{\topmargin} %sidemargins

\setlength{\textheight}{11in} \setlength{\textwidth}{8.5in}
\setlength{\hoffset}{-1in} \setlength{\voffset}{-1in} \setlength{\evensidemargin}{\oddsidemargin} \addtolength{\textheight}{-2 \topmargin}\addtolength{\textwidth}{-2\oddsidemargin}\setlength{\headheight}{0pt} \setlength{\headsep}{20pt} \setlength{\footskip}{20pt}\addtolength{\textheight}{-\footskip} \addtolength{\textheight}{-\headheight} \addtolength{\textheight}{-\headsep}


%%% Environments %%%--------------------------------------------------------- 
\newenvironment{ans}{\medskip \paragraph*{\emph{Answer}.}}{\hfill \break \rule{1.5cm}{0.4pt} \medskip }
\newenvironment{sketch}{\medskip \paragraph*{\emph{Proof sketch}.}}{ \medskip }
\newenvironment{summary}{\medskip \paragraph*{\emph{Summary}.}}{  \hfill \break  \rule{1.5cm}{0.4pt} \medskip }
\newcommand\Ans[1]{\hfill \emph{Answer:} {#1}}

%%%%% Theorems %%%%% 
\theoremstyle{plain}
	\newtheorem{thm}{Theorem}
	\newtheorem{lem}[thm]{Lemma}
	\newtheorem{prop}[thm]{Proposition}
	\newtheorem{cor}[thm]{Corollary}


%%% Pictures %%%--------------------------------------------------------- 
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage[pdftex,bookmarks]{hyperref}
\usetikzlibrary{scopes}
\usepgflibrary{shapes.geometric}
\tikzstyle{V}=[draw, fill =black, circle, inner sep=0pt, minimum size=2pt]
\tikzstyle{bV}=[draw, fill =black, circle, inner sep=0pt, minimum size=4pt]
\tikzstyle{over}=[draw=white,double=black,line width=3pt]

\newcommand\TikZ[1]{\begin{matrix}\begin{tikzpicture}#1\end{tikzpicture}\end{matrix}}



%%% Color  %%%--------------------------------------------------------------
\usepackage{color}
\definecolor{dred}{rgb}{.65, 0, 0.15}
\newcommand{\NOTE}[1]{{\color{blue}#1}}

%%% Alphabets %%%--------------------------------------------------------
\def\cA{\mathcal{A}}\def\cB{\mathcal{B}}\def\cC{\mathcal{C}}\def\cD{\mathcal{D}}\def\cE{\mathcal{E}}\def\cF{\mathcal{F}}\def\cG{\mathcal{G}}\def\cH{\mathcal{H}}\def\cI{\mathcal{I}}\def\cJ{\mathcal{J}}\def\cK{\mathcal{K}}\def\cL{\mathcal{L}}\def\cM{\mathcal{M}}\def\cN{\mathcal{N}}\def\cO{\mathcal{O}}\def\cP{\mathcal{P}}\def\cQ{\mathcal{Q}}\def\cR{\mathcal{R}}\def\cS{\mathcal{S}}\def\cT{\mathcal{T}}\def\cU{\mathcal{U}}\def\cV{\mathcal{V}}\def\cW{\mathcal{W}}\def\cX{\mathcal{X}}\def\cY{\mathcal{Y}}\def\cZ{\mathcal{Z}}

\def\AA{\mathbb{A}} \def\BB{\mathbb{B}} \def\CC{\mathbb{C}} \def\DD{\mathbb{D}} \def\EE{\mathbb{E}} \def\FF{\mathbb{F}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \def\II{\mathbb{I}} \def\JJ{\mathbb{J}} \def\KK{\mathbb{K}} \def\LL{\mathbb{L}} \def\MM{\mathbb{M}} \def\NN{\mathbb{N}} \def\OO{\mathbb{O}} \def\PP{\mathbb{P}} \def\QQ{\mathbb{Q}} \def\RR{\mathbb{R}} \def\SS{\mathbb{S}} \def\TT{\mathbb{T}} \def\UU{\mathbb{U}} \def\VV{\mathbb{V}} \def\WW{\mathbb{W}} \def\XX{\mathbb{X}} \def\YY{\mathbb{Y}} \def\ZZ{\mathbb{Z}}  

\def\ii{\mathbf{i}}\def\jj{\mathbf{j}}\def\kk{\mathbf{k}}\def\uu{\mathbf{u}}\def\vv{\mathbf{v}}\def\ww{\mathbf{w}}

\def\<{\langle} \def\>{\rangle}
\def\half{\hbox{$\frac12$}}
\def\id{\mathrm{id}}
\def\img{\mathrm{img}}
\def\vep{\varepsilon}
\def\lcm{\mathrm{lcm}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\HW{11}
\def\DUE{12/11/2018}
\def\NAME{YOUR NAME HERE}
\title[Homework \HW]{Homework \HW\\
Math 308\\
\small Due: \DUE}
\author{}
%\date{}                                           % Activate to display a given date or no date

\begin{document}
%\maketitle %Comment out this line, and uncomment the following for your assignment
\begin{flushright}
\NAME\\
Math 308\\
Homework \HW\\
\DUE
\end{flushright}


\noindent \textbf{For this assignment only}, if you prefer, you may turn in partially or fully hand-written solutions. 

\medskip

\noindent 
For problems 1--3, you may use our old working knowledge of number systems like $\ZZ$ and $\RR$. For problems 4--6, use the new set-theoretic definitions we developed, and only use assumptions about their properties as listed in the prompt. 

\medskip

\begin{enumerate}[1.]
\item For the following relations on $X$ determine whether they are reflexive, symmetric, and/or transitive. State whether they are equivalence relations or not and if they are describe their equivalence classes.
\begin{enumerate}
\item Let $X=\ZZ$ and define $\sim$ by $x\sim y$ if $x- y$ is odd.
\item Let $X=\RR$ and define $\sim$ by $x\sim y$ if $xy \neq 0$.
\item Let $X=\RR\times \RR$ and define $\sim$ by $(a,b)\sim (c,d)$ if $(a-c)(b-d) = 0$.
\end{enumerate}


\vfill 


\item Let $\sim$ be an equivalence relation on a set $A$, and for each $a \in A$, let 
	$$[a] = \{ b \in A ~|~ a \sim b \}$$
denote the \emph{equivalence class} of $x$.
\begin{enumerate}
\item Prove that if $x \in [y]$, then $y \in [x]$.\\
{[See notes.]} 
\item Prove that for all $x, y \in A$ that either $[x] \cap [y] = \emptyset$ or $[x] = [y]$. \\
{[Use part (a)).]} 
\item Prove that the equivalence classes partition $A$ (see notes).  \\
{[Use part (b)).]} 
\end{enumerate}

\vfill 

\item Let $\sim$ be the equivalence relation on $\ZZ$ given by $a \sim b$ if $a \equiv b \pmod{n}$. Define $\ZZ_n = \{ [a] ~|~ a \in \ZZ\}$, where $[a]$ is the equivalence class of $a$ modulo $n$.
\begin{enumerate}
\item Briefly explain why it makes sense to define $+ : \ZZ_n \times \ZZ_n \to \ZZ_n$ and $\cdot : \ZZ_n \times \ZZ_n \to \ZZ_n$ by 
$$[a] + [b] = [a + b] \quad \text{ and } \quad [a]\cdot [b] = [a + b].$$
{[If $[a] = [a']$ and $[b] = [b']$, do we know that $[a] + [b] = [a'] + [b']$?]}

\item Briefly check that $\ZZ_n$ is a commutative ring.\\
(By ``briefly'', I mean you can say things like ``since addition and multiplication satisfy \underline{\quad} in $\ZZ$, we have the same properties in $\ZZ_n$.'' )

\item Find an $n$ so that $\ZZ_n$ is not a field (justify your answer).
\end{enumerate}

\vfill 

\pagebreak

\item \textbf{Natural numbers.} For the following, use the set theoretic definition of $\ZZ_{\ge 0}$ developed in class. Let $a, b, c \in \ZZ_{\ge 0}$.

\medskip

Recall, we defined $\leq$ by 
\\ \smallskip
\centerline{$a \le b$\quad  if \quad  $b = S(S( \cdots S(a) \cdots ))$.} \smallskip
and addition by 
\\ \smallskip
\centerline{$a + 0 = a$; and $a + S(b) = S(a + b)$,} \smallskip
where $S: \ZZ_{\ge 0} \to \ZZ_{\ge 0}$ is the successor function. 

\smallskip

Using these definitions of $+$ and $\le$, prove that if $a \le b$ then $a + c \le b+c$. \\
{[You may want to use induction on $c$. You may assume that addition is associative.]}



\vfill

\item \textbf{Rational numbers.} For the following, use the set theoretic definition of $\QQ$ developed in class.  You may assume all properties we listed about addition, multiplication, and comparisons in $\ZZ$, like associativity, commutativity, additive inverses, etc.
\begin{enumerate}
\item Show that $\displaystyle \frac{0}{a} = \frac{0}{b}$ for all $a, b \in \ZZ_{\neq 0}$. 

\item We defined addition by 
$$\frac{a}{b} + \frac{c}{d} = \frac{a\cdot d + b \cdot c}{b \cdot d} \qquad \text{and} \qquad
	\frac{a}{b} \cdot \frac{c}{d} = \frac{a\cdot c}{b\cdot d},$$
	where the addition and multiplication on the right-hand-side of each equation is in $\ZZ$. We also said that for any $a \in \ZZ$, that in $\QQ$, $a$ is defined as $\frac{a}{1}$. 

\smallskip

Using these definitions, prove the following.
\begin{enumerate}
\item We have $\displaystyle \frac{a}{b} + 0 = \frac{a}{b}$ for all $\displaystyle \frac{a}{b} \in \QQ$. 
\item We have $\displaystyle \frac{a}{b} + \left(\frac{-a}{b}\right) = 0$ for all $\displaystyle \frac{a}{b} \in \QQ$. 
\item We have $\displaystyle \frac{a}{b} \cdot \frac{b}{a} = 1$ for all $\displaystyle \frac{a}{b} \in \QQ$ with $b \neq 0$. \\
{[You'll need to show that $\frac{c}{c} = 1$ for all $c \in \ZZ_{\neq 0}$.]}


\end{enumerate}
\end{enumerate}

\vfill

\item \textbf{Real numbers.}  Recall that the set $\cR$ of Dedekind cuts is the subsets of $\QQ$ satisfying properties \textbf{(i)}--\textbf{(iii)} on page 30 of ``Elementary analysis'' (see below), with operations defined set-theoretically. As in class, define $0^* = \{ y \in \QQ ~|~ y <0 \}$.  You may assume all properties we listed about addition, multiplication, and comparisons in $\QQ$, like associativity, commutativity, additive inverses, etc.

\medskip

 \noindent For $\alpha, \beta \in \cR$, we defined $\alpha + \beta = \{a + b ~|~ a \in \alpha, b \in \beta\}$. 
 \begin{enumerate}
 \item Briefly verify that $0^* \in \cR$. 
 \item Prove that for $\alpha, \beta \in \cR$, we have $\alpha + \beta \in \cR$. \\
 {[You get to assume that $\alpha$ satisfies \textbf{(i)} $\alpha \neq \QQ, \emptyset$; \textbf{(ii)} if $r \in \alpha$ and $s \in \QQ$ satisfy $s < r$, then $s \in \alpha$; and \textbf{(iii)} $\alpha$ doesn't have a maximum (and similarly for $\beta$). Your goal is to show that $\alpha + \beta$ also satisfies those three properties.]}
 \item Briefly check that $\{ a \in \QQ ~|~ a^3 < 2\}$ is a Dedekind cut, but $\{ a \in \QQ ~|~ a^2 < 2\}$ is not. \\
 {[You many use arithmetic properties of $\QQ$ without proof.]}
 \item Show that $\alpha + 0^* = \alpha$ for all $\alpha \in \cR$. 
 \end{enumerate}
 

\end{enumerate}

\vfill



\end{document}