\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{16: The Unit Distance Graph}{Due Friday, Week 10}


Do \textbf{one} of the four problems listed here!  Have fun, prove all of your claims, and let me know if you have any questions!  

\begin{enumerate}
\item Finish our proof that $\chi(\mathbb{Q}^2)$ is rational by proving the following claims:
\begin{enumerate}

\item Take any two rational numbers $\frac{a}{b}, \frac{c}{d}$ written so that $GCD(a,b) = 1 = GCD(c,d)$.  Suppose that $a^2d^2 + b^2c^2 = b^2 d^2$.  

Prove that both $b$ and $d$ must be odd.
\item Using (a), take any two points $\vec{q}, \vec{r} \in \mathbb{Q}^2$.  Show that if $d(\vec{q}, \vec{r}) = 1$, then $\vec{q} \sim \vec{r}$ under the equivalence relation defined in class on Monday.
\item Take the collection of all rational points equivalent to $(0,0)$, under the equivalence relation defined in class.  Color points in this class red when they are of the form $\left( \frac{odd}{odd}, \frac{odd}{odd} \right)$ or $\left(\frac{even}{odd}, \frac{even}{odd} \right)$, and color them blue otherwise; i.e.\ color points blue when they are of the form $\left( \frac{odd}{odd}, \frac{even}{odd} \right)$ or $\left(\frac{even}{odd}, \frac{odd}{odd} \right)$. 

Prove the claim we made in class:\ any two points that are distance 1 apart in this class are colored different colors.
\end{enumerate}

\item  Zorn's lemma, in mathematics, says the following:
\begin{lemma}[Zorn's lemma]
Suppose that $(P, \leq)$ is a nonemptu partially ordered set\footnote{A partially ordered set $(P, \leq)$ is a set $P$ and a binary relation $\leq$ such that $\leq$ satisfies the folowing three axioms:
\begin{itemize}
\item $a \leq a$ (reflexivity)
\item $a \leq b$ and $b \leq a$ implies $a=b$ (antisymmetry)
\item $a \leq b$ and $b \leq c$ implies $a \leq c$ (transitivity).
\end{itemize}} with the following property: in any totally ordered subset\footnote{A subset $T$ of $P$ is called totally ordered if every two elements are comparable in $T$: i.e. for any $a,b \in T$, $a \leq b$ or $b \leq a$.} $T$ of $P$, there is an upper bound $u$: i.e. an element $u$ such that for any other $a \in T$, $a \leq t$.


Then $P$ has a maximal element: i.e. there is some $m \in P$ such that we never have $m < a$ for any $a \in P$.
\end{lemma}

Prove this, using the axiom of choice.

\item Let $\mathbb{Q}^3$ denote the graph on $\mathbb{Q}^3$ formed by connecting $\vec{v}, \vec{w}$ with an edge if and only if $d(\vec{v}, \vec{w}) = 1$.  Show that $\chi(\mathbb{Q}^3) = 2$.

\end{enumerate}



\end{document}

