\documentclass{article}
\usepackage{amsmath,amsthm,amssymb}

\title{Math101 \\ Selected Solutions for Problem Set 4}
\author{Thomas Allen and Stefan Karpinski}

\newcommand{\union}{\cup}
\newcommand{\inter}{\cap}
\newcommand{\set}[1]{\left{#1\right}}
\newcommand{\Question}[1]{\subsection*{Question #1}}
\newcommand{\Problem}[1]{\subsection*{Problem #1}}
\newcommand{\Part}[1]{\paragraph*{Part #1}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\F}{\ensuremath{\mathbb{F}}}
\newcommand{\K}{\ensuremath{\mathcal{K}}}
\newcommand{\Cf}{\textit{C.f.} }
\newcommand{\cf}{\textit{c.f.} }
\newcommand{\te}{\exists\:}
\newcommand{\etc}{\textit{etc.} }
\newcommand{\Eg}{\textit{E.g.} }
\newcommand{\eg}{\textit{e.g.} }
\newcommand{\Ie}{\textit{I.e.} }
\newcommand{\ie}{\textit{i.e.} }
\newcommand{\fa}{\forall}
\newcommand{\st}{\text{ \textit{s.t.} }}

\begin{document}

\maketitle



\Problem{N 3.3.1}


Let $A \subset B \subset \R^{n}$.  Take $x \in \K A$.  For every $\epsilon > 0$, there
exists an $a \in A \subset B$ such that $d(x,a) < \epsilon$.  So, $x \in \K B$, by definition.
Therefore,$ \K A \subset \K B$.

Now, note that $A \inter B \subset A \Rightarrow \K (A \inter B) \subset \K A$.  Similarly, for $\K B$.
So, \K $(A \inter B) \subset \K A \inter \K B$.


\Problem{W 6.2.2}



\Part{(a)}


No, not symmetric


\Part{(b)}


Yes


\Part{(c)}


Yes


\Part{(d)}


No, not transitive.


\Part{(e)}


Yes


\Part{(f)}


No, $A \subset \R$ may not have a smallest member.  So, not reflexive.


\Problem{W 6.2.4}


Some common answers and mistakes


\Part{(a)}


$|a - b| < 1$


\Part{(b)}


$a \leq b$


\Part{(c)}


A common mistake included a proof that symmetric and transitive implies reflexive.
While it is true that symmestric and transitive implies reflexive for the elements contained
in $R$, it does not give you reflexivity for all $x \in A$.  Consider:
\begin{align*}
	R = \{(x,y) \in \N^{2} | x \leq y\} - \{(x,y) | x = 1~\text{or}~y = 1\}.
\end{align*}
This does not contain $(1,1)$.


\Part{(d)}


$0 \leq a - b \leq 1$


\Part{(e)}


$a \not= b$


\Part{(f)}


$a < b$


\Part{(g)}


$a = 2 b$


\Problem{W 6.2.8}


The relation is clearly reflexive and symmetric.  The main issue comes down
showing that the relation is transitive.  First, suppose $(a,b) ~ (c,d)$ and
$(c,d) ~ (e,f) \Rightarrow a d = b c$ and $c f = d e \Rightarrow a d f = b c f \Rightarrow a d f = b d e
\Rightarrow d(a f - b e) = 0$.  But, $d \not= 0$ by construction, so $a f - b e = 0$.  Thus we
have $a f = b e$ or $(a,b) ~ (e,f)$, as desired. Many people tried to use division
($i.e$. multiplication by inverses).  However, since we're working entirely
inside \Z, which doesn't have multiplicative inverses, this is no good.


\Problem{W 6.3.20 and 6.3.21}


For $a$ ``critique'' of a proof you must first determine whether the proof is
correct or not.  If the proof is correct you need only state that it is
correct and briefly explain why the proof is in fact legitimate at each
possible point of concern.  If the proof is incorrect (or incomplete) you
need to pinpoint precisely where it goes wrong and explain why it is wrong.
Commentary on style and philosophical concerns is not required.

The proof in $20$ is in fact correct.  The biggest possible concern is over
the disjointness of $R$ and $S$:  because of this the relation $R \cup S$ has the
property that for any $x \in A$ and $y \in B$ neither $(x,y)$ nor $(y,x)$ is in
$R \cup S$.  However this is not a difficulty for the proof given in problem $20$
since we are only trying to prove that $R \cup S$ is a partial ordering.
However for problem $21$ it is a big problem.  The proof asserts ``since $R$ is
total on $A$ and $S$ is total on $B, R \cup S$ is total on $A \cup B'$' but there is no
reason for this at all---in fact by the above observation, unless $A = B =
\emptyset$ the ordering $R \cup S$ cannot be total on $A \cup B$.


\Problem{W 8.2.12 (not assigned but I did it by accident)}


The technique here is an important and common one.  We take a minimal element
of some sort (in this case the least common multiple of two integers). Then we
assume that the proposition is not true and use this to show that our
minimal element cannot in fact be minimal, yielding a contradiction.

Let $l$ be the least common multiple of $n$ and $m.  I.e$. let $l$ be the least
positive integer such that both $n$ and $m$ divide $l$.  Now suppose that there
exists some $k$ which is a common multiple of $n$ and $m$ but such that $l$ does not
divide $k$ (without loss of generality, we can let $k$ be positive since we can
always replace $k$ by $-k$).  Since we picked $l$ to be minimal, we know that $l <
k$.  Thus we may use the Euclidean algorithm, more commonly known as division
with remainder.  $I.e$. we may find positive integers $q$ and $r$ (why do we know
that they're both non-zero?) such that $r < l$ and
\begin{align*}
	k = q l + r.
\end{align*}
Thus we may also write $r$ as $k - q l$.  But since both $n$ and $m$ divide $k$ and $l$,
they must also divide $r$ but $r < l$, contradicting the minimality of $l$ as a
common multiple of $n$ and $m$.


\Problem{W 8.3.13}


Two integers $m$ and $n$ are said to be \textit{relatively prime} if there exist integers
$k$ and $l$ such that $m k + n l = 1$.  This is equivalent to $m$ and $n$ having no
common factors other than $1$.  (More generally, the least common factor of $m$
and $n$ is the smallest positive integer of the form $m k + n l$.)  But
\begin{align*}
	\te l \st m k + n l = 1 \quad \Longleftrightarrow \quad m k \equiv 1 \pmod n
\end{align*}
Thus the existence of an inverse for $m$ in $\Z_{n}$ is equivalent to the relative
primality of $m$ and $n$.  Now, since primes are relatively prime to everything
but multiples of themselves ($i.e$. numbers that are $\equiv 0 \pmod p$), in
particular, a prime $p$ is relatively prime to every $m$ such that $0 < m < p$, so
each such $m$ is invertible in $\Z_{p}$.


\Problem{W 8.3.15}



\Part{(a)}


An important idea to use here is that the order of an element divides the
order of the group it is contained in.  Therefore, if $a^{d} = 1$, then $d|3$ ($3 = |
\F_{4}$ - \{$0$\} $|$ ).  So, $d = 1$ or $3$.  But, $a \not= 1$, so $d = 3$ and $a^{3} = 1$.  So,
$a^{(-1)} = a^{2}$.  This fact allows for the completion of both tables.


\Problem{W 9.5.4}



\Part{(a)}


Suppose $c n < d n$ and $n > 0$.  Then $n(c-d) < 0$.  But, $n > 0 \Rightarrow c-d < 0$.
So, $c < d$.     Therefore, if we have $a < b$ and $b < c$, then ab $<$ bc (assuming $b
> 0$, which you can do wlog).  The lemma $\Rightarrow a < c$, as desired.


\Part{(b)}


Division is not defined for $\Z$ since there are no multiplicative inverses
(for $z \not= \pm 1$).

\end{document}
