 %!TEX root = proofs+concepts.tex


\chapter{Sample Topics} \label{TopicsChap}

\begin{quote}
\it If people do not believe that mathematics is simple,
\\ it is only because they do not realize how complicated life is.
\par\raggedleft \small\rm\sf
John von Neumann (1903--1957), Hungarian-American mathematician
\end{quote}

\medskip\noindent
This \lcnamecref{TopicsChap} provides exercises from three % !!! 
different mathematical topics (Number Theory, Abstract Algebra, and Real Analysis) that will test your proof-writing skills. To succeed in advanced math classes, you will need to be able to solve problems like these.


\begin{terminology}
Up to this point, our valid deductions have been called ``theorems\rlap,'' but mathematicians usually reserve this name for the ones that are particularly important, and apply some other name to the others. The terminology allows some flexibility, but here are general guidelines:
\noprelistbreak % why doesn't this work?
\begin{itemize}
\item Any valid deduction can be referred to as a ``result\rlap.''

\item A \define{theorem} is an important result. 
%It may be given a special name, for ease of reference.  Many theorems, such as ``the Pythagorean Theorem'' (which is attributed to Pythagorus), are named after the mathematician who first proved them. Other theorems, such as ``the Fundamental Theorem of Calculus\rlap,'' have been given names that relate to their content or importance.

\item A \define{proposition} is a result that is not sufficiently important to be called a theorem.

\item A \define{corollary} is a result that is proved as an easy consequence of some other result. 
% Generally, mathematicians use this term in cases where the logical sequence is so clear that no proof (or at most, a short proof) is required.  

\item A \define{lemma} is a minor result that is not interesting for its own sake, but will be used as part of the proof of theorem (or other more significant result).
% a stepping stone for proving a theorem (or some other more significant result).  Mathematicians will separate a lemma from the main proof of a theorem either because the proof is long and complicated and needs to be broken down into smaller steps, or because it is a step that needs to be performed repeatedly.  It is much easier and clearer to refer to a lemma multiple times, than to either include the reasoning repeatedly, or refer back to an earlier portion of a single long proof.
\end{itemize}
%The results in this chapter have all been called ``theorems\rlap,'' but this should not be taken as an indication of their importance.  Now that we have introduced this terminology, all of these results should have been called ``propositions\rlap.''  In each case, the result was being proven to demonstrate a proof technique, rather than for any value in the statement of the result itself.
\end{terminology}

%\begin{rem}
%Like ``theorem\rlap,'' the word ``lemma'' was originally Greek, was adopted into Latin, and is now also used in English.  Although the English plural ``lemmas'' is quite acceptable, some mathematicians prefer the classical plural, which is ``lemmata\rlap.''
%\end{rem}



\section{Number Theory: divisibility and  congruence} \label{CongruenceSect}

In this \lcnamecref{CongruenceSect}, we will get some practice with proving properties of integers.

\subsection{Divisibility} \label{DivisibilitySubsect}

Every math student knows that some numbers are even and some numbers are odd; some numbers are divisible by~$3$, and some are not; etc.
Let us introduce a notation that makes it easy to talk about whether or not one number~$b$ is divisible by some other number~$a$:

\begin{defn} \label{DividesDefn}
Suppose $a,b \in \integer$.
We say $a$ is a \define{divisor} of~$b$ (and write ``$a \divides b$'')%
\nindex{$a \divides b$}
iff there exists $k \in \integer$, such that $a k = b$. (Since multiplication is commutative and equality is symmetric, this equation can also be written as $b = ka$.)
\end{defn}

\begin{notation}
$a \notdivides b$%
\nindex{$a \notdivides b$}
is an abbreviation for ``$a$ does \emph{not} divide~$b$\rlap.''
\end{notation}

\begin{rem}
When $a$ is a divisor of~$b$, we may also say:
\noprelistbreak
\begin{tasks}(2) 
\task\fixtask $a$ \define[divides ($a \protect\divides b$)]{divides}~$b$,
or
\task\fixtask $a$ is a \define{factor} of~$b$,
or
\task\fixtask $b$ is a \define{multiple} of~$a$,
or
\task\fixtask $b$ is \define{divisible} by~$a$.
\end{tasks}
\end{rem}

\begin{eg} \label{DivisorEasyEg} \ 
\begin{enumerate}
\item We have $5 \divides 30$, because $5 \cdot 6 = 30$, and $6 \in \integer$.
\item We have $5 \notdivides 27$, because there is no integer~$k$, such that $5k = 27$.
\end{enumerate}
\end{eg}

\begin{exer} \label{EasyCongEx}
Fill each blank with $\divides$ or~$\notdivides$, as appropriate.
\begin{tasks}(3)
\task\fixtask \label{EasyCongEx-3|18}%
$3 \blank 18$
\task\fixtask \label{EasyCongEx-4|18}%
$4 \blank 18$
\task\fixtask \label{EasyCongEx-5|18}%
$5 \blank 18$
\task\fixtask \label{EasyCongEx-6|18}%
$6 \blank 18$
\task\fixtask \label{EasyCongEx-18|6}%
$18 \blank 6$
\task\fixtask \label{EasyCongEx-min6|6}%
$-6 \blank  6$
\end{tasks}
\end{exer}

The following definition is perhaps the best known example of divisibility.

\begin{defn} Let $n \in \integer$. 
We say $n$ is
  \define[even integer]{even} iff $2 \divides n$.
  We say $n$~is \define[odd integer]{odd} iff $2 \notdivides n$.
\end{defn}

Here are some examples of proofs involving divisibility.
We will assume the well-known fact that the sum, difference, and product of integers are integers: for all $k_1, k_2 \in \integer$, we know that $k_1 + k_2 \in \integer$, $k_1 - k_2 \in \integer$, and $k_1 k_2 \in \integer$. Also, the negative of any integer is an integer: for all $k \in \integer$, we have $-k \in \integer$.

Our first result is a generalization of the well-known fact that the sum of two even numbers is even.

\begin{prop} \label{DivideSum}
Suppose $a,b_1,b_2 \in \integer$.
 If $a \divides b_1$ and $a \divides b_2$, then $a \divides (b_1 + b_2)$.
\end{prop}

\vskip-1.5\baselineskip \ % !!!
\begin{scratchwork}
Since $a \divides b_1$ and $a \divides b_2$, we know there is some $k \in \integer$, such that $ak = b_1$, and we know there is some $k \in \integer$, such that $ak = b_2$.  However, these are probably two different values of~$k$, so we need to give them different names if we want to talk about both of them at the same time.  So let's call the first one~$k_1$ and the second one~$k_2$:
	\begin{itemize}
	\item there exists $k_1 \in \integer$, such that $ak_1 = b_1$, 
	and 
	\item there exists $k_2 \in \integer$, such that $ak_2 = b_2$.
	\end{itemize}
To show $a \divides (b_1 + b_2)$, we want to find some $k \in \integer$, such that 
	$$ak \stackrel{?}{=} b_1 + b_2.$$ 
Since $b_1 + b_2 =  ak_1 + a k_2 = a(k_1 + k_2)$, this means we want 
	$$ak \stackrel{?}{=} a(k_1 + k_2) .$$ 
So it is clear that we should let $k = k_1 + k_2$.
\end{scratchwork}

\begin{proof}
Since, by assumption, $a$ is a divisor of both~$b_1$ and~$b_2$, there exist $k_1,k_2 \in \integer$, such that $a k_1 = b_1$ and $a k_2 = b_2$. Let $k = k_1 + k_2$. Then $k \in \integer$ and
	$$ a k = a (k_1 + k_2) = a k_1 + a k_2 = b_1 + b_2 ,$$
so $a$ is a divisor of $b_1 + b_2$, as desired.
\end{proof}

\begin{prop} \label{DivideNegative}
Suppose $a,b \in \integer$.
We have $a \divides b$ iff $a \divides -b$.
\end{prop}

\vskip-1.5\baselineskip \ % !!!
\begin{scratchwork}
($\Rightarrow$) Since $a \divides b$, we know there is some~$k$, such that $ak = b$. To show $a \divides -b$, we want to find some other~$k$ --- let's call it $k'$ --- such that $a k' \stackrel{?}{=} -b$. Since $-b = -(ak) = a(-k)$, this means we want $ak' \stackrel{?}{=} a(-k)$. So we should let $k' = -k$.

($\Leftarrow$) Since $a \divides -b$, we know there is some~$k$, such that $ak = -b$. To show $a \divides b$, we want to find some~$k'$, such that $a k' \stackrel{?}{=} b$. Since $-b = ak$, we have $b = -(ak) = a(-k)$, so we can let $k' = -k$. This is the same work as in the proof of ($\Rightarrow$), and the official proof given below avoids the need for repeating this algebra, by appealing to the result that we have already proved.
\end{scratchwork}

\begin{proof}
($\Rightarrow$) By assumption, there is some $k \in \integer$, such that $a k = b$. Then $-k \in \integer$, and we have $a(-k) = -ak = -b$, Therefore, $a$ divides~$-b$.

($\Leftarrow$) Assume $a \divides -b$. From the preceding paragraph, we conclude that $a \divides -(-b) = b$, as desired.
\end{proof}

\begin{exers} \label{DivisorPfEx}
Assume $a,a',b,b' \in \integer$.
\begin{enumerate}
\item \label{DivisorPfEx-difference}
 Show that if $a \divides b$ and $a \divides b'$, then $a \divides b - b'$.
\item \label{DivisorPfEx-negativea}
Show that $a \divides b$ iff $-a \divides b$.
\item \label{DivisorPfEx-1divb}
 Show $1 \divides b$.
\item \label{DivisorPfEx-adiv0}
Show $a \divides 0$.
\item \label{DivisorPfEx-0divb}
Show that if $0 \divides b$, then $b = 0$.
\item \label{DivisorPfEx-product}
Show that if $a \divides b$, then $a \divides b b'$.
\item \label{DivisorPfEx-doubleproduct}
Show that if $a \divides b$ and $a' \divides b'$, then $aa' \divides b b'$.
\end{enumerate}
\end{exers}

\begin{prop}
Suppose $a,b_1,b_2 \in \integer$.
If $a \divides b_1$ and $a \notdivides b_2$, then $a \nmid (b_1 + b_2)$.
\end{prop}

\begin{proof}
Assume $a \divides b_1$ and $a \nmid b_2$.

Suppose $a \divides (b_1 + b_2)$. (This will lead to a contradiction.) Then $a$ is a divisor of both $b_1 + b_2$ and (by assumption)~$b_1$. So Exercise~\fullref{DivisorPfEx}{difference} tells us 
	$$a \divides \bigl( (b_1 + b_2) - b_1 \bigr) = b_2 .$$
This contradicts the assumption that $a \notdivides b_2$.

Because it leads to a contradiction, our hypothesis that $a \divides (b_1 + b_2)$ must be false. This means $a \notdivides (b_1 + b_2)$.
\end{proof}

It is well known that $1$ and~$-1$ are the only integers whose reciprocal is also an integer. In the language of divisibility, this can be restated as the following useful fact:
%\begin{equation} 
\label{NotDiv1}
%\hbox{
\factoidbox{For any integer~$n$, we have $n \divides 1$ iff $n = \pm 1$.}
%}
%\end{equation}

\begin{exer} \label{DividesPropsEx} Prove:
\begin{enumerate}
\item \label{DividesPropsEx-reflexive}
%(``divisibility is reflexive'')
For all $a \in \integer$, we have $a \divides a$.
\item \label{DividesPropsEx-transitive}
%(``divisibility is transitive'')
For all $a,b,c \in \integer$, if $a\divides b$ and $b \divides c$, then $a \divides c$.
\item \label{DividesPropsEx-notsymmetric}
%(``divisibility is \emph{not} transitive'')
It is \emph{not} true that, 
	for all $a,b \in \integer$, we have $a \divides b$ iff $b \divides a$.
\end{enumerate}
\end{exer} 

\begin{rem}
The three parts of the preceding exercise show that divisibility is ``reflexive'' and ``transitive\rlap,'' but not ``symmetric\rlap.'' These terms will be defined in \cref{RefSymmTransDefn}.
\end{rem}

\begin{exers} \label{DividesExers}
 Assume $a,b,x,y \in \integer$. Prove:
\begin{problist}
\item  \label{DividesExers-2xy} % from Fall 2011 Midterm Exam ???
If \ $a \mid x$ \ and \ $b \mid y$, \ then \ $ab \mid 2xy$.
\item  \label{DividesExers-less}
If $a,b \in \natural^+$, and $a \divides b$, then $a \le b$.
\end{problist}
\end{exers}

\begin{exers} \label{DividesProveDisprove}
Prove or disprove each assertion.
\begin{enumerate}
\item \label{DividesProveDisprove-sum}
For all $a,b_1,b_2 \in \integer$, if $a\notdivides b_1$ and $a \notdivides b_2$, then $a \notdivides (b_1 + b_2)$.
\item \label{DividesProveDisprove-product}
For all $a,b_1,b_2 \in \integer$, if $a\notdivides b_1$ and $a \notdivides b_2$, then $a \notdivides b_1 b_2$.
\item \label{DividesProveDisprove-transitive}
For all $a,b,c \in \integer$, if $a\notdivides b$ and $b \notdivides c$, then $a \notdivides c$.
\item \label{DividesProveDisprove-negative}
For all $a,b \in \integer$, if $a\notdivides b$, then $a \notdivides -b$.
\end{enumerate}
\end{exers}



\subsection{Congruence modulo~\texorpdfstring{$n$}{n}} \label{CongruenceSubsect}

\begin{defn}
Suppose $a,b,n \in \integer$. We say $a$ is \define[congruent]{congruent to~$b$ modulo~$n$} iff $a - b$ is divisible by~$n$. The notation for this is:
	$ a \equiv b \pmod{n} 
	\nindex{$\equiv$}
	$.
\end{defn}




\begin{eg} \label{CongruenceEasyEg} \ 
\begin{enumerate}
\item \label{CongruenceEasyEg-even}
 We have $22 \equiv 0 \pmod{2}$, because $22 - 0 = 22 = 11 \times 2$ is a multiple of~$2$.  (More generally, for $a \in \integer$, one can show that $a \equiv 0 \pmod{2}$ iff $a$~is even.)
\item \label{CongruenceEasyEg-odd}
 We have $15 \equiv 1 \pmod{2}$, because $15 - 1 = 14 =  7 \times 2$ is a multiple of~$2$. (More generally, for $a \in \integer$, one can show that $a \equiv 1 \pmod{2}$ iff $a$~is odd.)
\item We have $28 \equiv 13 \pmod{5}$, because $28 - 13 = 15 = 3 \times 5$ is a multiple of~$5$.
\item For any $a,n \in \integer$, it is not difficult to see that $a \equiv 0 \pmod{n}$ iff $a$~is a multiple of~$n$.
\end{enumerate}
\end{eg}

\begin{exers} \label{CongEasyExer}
Fill each blank with $\equiv$ or $\not\equiv$, as appropriate.
\begin{tasks}(3)
\task\fixtask \label{CongEasyExer-14=5mod2}%
$ 14 \blank 5 \pmod{2}$
\task\fixtask \label{CongEasyExer-14=5mod3}%
$ 14 \blank 5 \pmod{3}$
\task\fixtask \label{CongEasyExer-14=5mod4}%
$ 14 \blank 5 \pmod{4}$
\task\fixtask \label{CongEasyExer-14=32mod2}%
$ 14 \blank 32 \pmod{2}$
\task\fixtask \label{CongEasyExer-14=32mod3}%
$ 14 \blank 32 \pmod{3}$
\task\fixtask \label{CongEasyExer-14=32mod4}%
$ 14 \blank 32 \pmod{4}$
\end{tasks}
\end{exers}

%\begin{exers}
%Assume $a,b,n \in \integer$.
%\begin{enumerate}
%\item Show $a \equiv 0 \pmod{n}$ iff $a$ is a multiple of~$n$.
%%\item Show $a \equiv b \pmod{0}$ iff $a = b$.
%\end{enumerate}
%\end{exers}

\begin{exers} \label{CongEquivRel}
(``Congruence modulo~$n$ is reflexive, symmetric, and transitive\rlap.'')
\\Let $n \in \integer$. Prove:
\begin{enumerate}
\item \label{CongEquivRel-reflexive}
For all $a \in \integer$, we have 
		$a \equiv a \pmod{n}$.
\item \label{CongEquivRel-symmetric}
For all $a,b \in \integer$, we have 
		$a \equiv b \pmod{n}$ iff $b \equiv a \pmod{n}$.
\item \label{CongEquivRel-transitive}
For all $a,b,c \in \integer$, 
		if $a\equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a \equiv c \pmod{n}$.
\end{enumerate}
\end{exers} 

\begin{exers} \label{CongRespectOpsEx}
Assume $a_1 \equiv a_2 \pmod{n}$ and $b_1 \equiv b_2 \pmod{n}$. Show:
\begin{enumerate}
\item \label{CongRespectOpsEx-sum}
$a_1 + b_1 \equiv a_2 + b_2 \pmod{n}$.
\item \label{CongRespectOpsEx-diff}
 $a_1 - b_1 \equiv a_2 - b_2 \pmod{n}$.
\item \label{CongRespectOpsEx-mult}
 $a_1  b_1 \equiv a_2  b_2 \pmod{n}$.
\hint{$a_1 b_1 - a_2 b_2 = a_1(b_1 - b_2) + (a_1 - a_2) b_2$.}
\end{enumerate}
\end{exers}

Children are taught that if a number~$a$ is divided by a number~$n$, then there may be a remainder, but the remainder is always smaller than~$n$.  That idea is said more precisely in the following theorem:

\begin{thm}[(Division Algorithm)] \label{DivAlgThm}
Suppose $a,n \in \integer$, and $n \neq 0$. 
Then there exist unique integers $q$ and~$r$ in~$\integer$, such that:
	\begin{enumerate}
	\item $a = qn + r$,
	and
	\item $0 \le r < |n|$.
	\end{enumerate}
\end{thm}

\begin{defn}
In the situation of \cref{DivAlgThm}, the number~$r$ is called the \define{remainder} when $a$ is divided by~$n$.
\end{defn}

%The following exercise shows that congruence modulo~$n$ is a way to check whether or not two numbers have the same remainder when they are divided by~$n$.
The following exercise reveals the close relationship between congruence and remainders.

\begin{exer} \label{CongVsRemainderEx}
Suppose $a,b,n \in \integer$ (and $n \neq 0$).
\begin{enumerate}
\item \label{CongVsRemainderEx-remainder}
 Let $r$ be the remainder when $a$ is divided by~$n$.
Show $a \equiv r \pmod{n}$.
\item \label{CongVsRemainderEx-Cong}
 Show that $a \equiv b \pmod{n}$ iff $a$~and~$b$ have the same remainder when divided by~$n$.
\end{enumerate}
\end{exer}

\begin{rem} \label{0or1Mod2}
From the second half of parts \pref{CongruenceEasyEg-even}
 and~\pref{CongruenceEasyEg-odd} of \cref{CongruenceEasyEg}, we see that every integer is congruent to either $0$ or~$1$ modulo~$2$ (and not both). 
 \factoidbox{$n$ is even iff $n \equiv 0 \pmod{2}$.
  \\[5pt] $n$ is odd iff $n \equiv 1 \pmod{2}$.}
 \fullcref{CongVsRemainderEx}{remainder} generalizes this to congruence modulo numbers other than~$2$: if $n \in \natural^+$, then every integer is congruent (modulo~$n$) to some number in $\{0,1,2,\ldots,n-1\}$.
\end{rem}

\begin{eg}
Let us show that if $n$ is odd, then $9n+6$ is also odd. To see this, note that:
	\begin{itemize}
	\item $9 \equiv 1 \pmod{2}$, because $9 = 4(2) + 1$, 
	\item $n \equiv 1 \pmod{2}$, because $n$~is odd,
	and
	\item $6 \equiv 0 \pmod{2}$, because $6 = 3(2) + 0 $.
	\end{itemize}
Therefore, using \cref{CongRespectOpsEx}, we have
	$$9n+6 \equiv (1)(1)+0 \equiv 1 \pmod{2} .$$
\end{eg}

The same method can be applied in the following exercises:

\begin{exers} \label{ShowOddEvenEx}
Let $n \in \integer$.
\begin{problist}
\item \label{ShowOddEvenEx-6n+3}
Show $6n + 3$ is odd.
\item \label{ShowOddEvenEx-5n+3odd}
Show that if $n$~is even, then $5n+3$ is odd.
\item \label{ShowOddEvenEx-5n+3even}
Show that if $n$~is odd, then $5n+3$ is even.
%\item Show that if $m$ and~$n$ are odd, then $m^2 - n^2$ is divisible by~$4$.
\end{problist}
\end{exers}

\begin{prop} \label{n2+nEven}
Let $n \in \integer$. Then $n^2 + n$ is even.
\end{prop}

\begin{proof}
From \cref{0or1Mod2}, we know that $n$ is congruent to either $0$ or~$1$ modulo~$2$. We consider these two possibilities as separate cases.

\setcounter{case}{0}

\begin{case}
Assume $n \equiv 0 \pmod 2$.
\end{case}
By the assumption of this case, we have $n = 2q$, for some $q \in \integer$. Therefore
	$$ n^2 + n = (2q)^2 + 2q = 4q^2 + 2q = 2(2q^2 + q)$$
is divisible by~$2$.

\begin{case}
Assume $n \equiv 1 \pmod 2$.
\end{case}
By the assumption of this case, we have $n = 2q+1$, for some $q \in \integer$. Therefore
	$$ n^2 + n 
	= (2q+1)^2 + (2q+1) 
	= (4q^2 + 4q + 1) + (2q+ 1) 
	= 4q^2 + 6q+ 2
	= 2(2q^2 + 3q + 1)$$
is divisible by~$2$.
\end{proof}

\begin{exers} \label{SquareMod4or8Ex}
Let $n \in \integer$.
\begin{problist}
\item \label{SquareMod4or8Ex-even}
Show that if $n$ is even, then $n^2 \equiv 0 \pmod{4}$.
\hint{We have $n = 2q$, for some $q \in \integer$.}
\item \label{SquareMod4or8Ex-odd}
Show that if $n$ is odd, then $n^2 \equiv 1 \pmod{8}$.
\hint{We have $n = 2q+1$, for some $q \in \integer$.}
\item \label{SquareMod4or8Ex-squareeven}
Show that if $n^2$ is even, then $n$~is even.
\end{problist}
\end{exers}

%
%\subsection{Clock arithmetic}

%Telling time (in Canada and the US) is an example of a system where numbers are treated ``{modulo~12}\rlap,'' rather than treated as ordinary integers.

%\begin{eg} \ 
%\begin{enumerate}
%\item Since $5 + 3 = 8$, we know that if we start studying at $5$~o'clock, and spend $3$~hours doing it, then we will finish at $8$~o'clock.
%\item We have $11 + 3 = 14$, but that does \emph{not} mean that if we start our $3$-hour study session at $11$~o'clock, then we will finish at $14$~o'clock. (The time ``$14$~o'clock'' does not exist!) Instead, observing that $14 = 12 + 2$, we see that we will finish $2$~hours after $12$~o'clock, which is at $2$~o'clock.
%\end{enumerate}
%\end{eg}

%\begin{eg} \ 
%\begin{enumerate}
%\item If it is $7$~o'clock now, then what time will it be $60$ hours from now?
%\item If it is $9$~o'clock now, then what time will it be $150$~hours from now?
%\end{enumerate}
%\end{eg}

%
%Show that $\overline{a} = \overline{b}$ iff $a - b$ is a multiple of~$12$.

%When telling time (in Canada and the US), the hour is given as a number from~$1$ to~$12$. For example, the time may be $3$~o'clock or $11$~o'clock, but it cannot be $15$~o'clock, because $15$ is larger than~$12$. This means that calculations involving the time of day do not work exactly as they do in ordinary arithmetic.  

%\begin{eg} \label{ElemModArithEg}
%Here are two problems of elementary arithmetic:
%\begin{enumerate}
%\item \label{ElemModArithEg-prod}
% What is the last digit of the product $32,918 \times 532,19$?
%\item \label{ElemModArithEg-time}
% If it is 2:00~PM now, then what time will it be 100 hours from now?
%\end{enumerate}

%\begin{solution}
%\pref{ElemModArithEg-prod}~We can ignore all but the last digit of each number that was given to us. (The reason for this will be explained later in the chapter.) Since $8 \times 9 = 72$, and the last digit of~$72$ is~$2$, we conclude that the last digit of the original product is~$2$.

%\medskip
%\pref{ElemModArithEg-time} The time 2~PM repeats itself every 24 hours (since there are 24 hours in a day). Therefore, since $96 = 4 \times 24$ is a multiple of~$24$, it will be 2~PM when we check the time $96$~hours from now.  Exactly $4$~hours after that (which is 100~hours from now), it will be $2 + 4 = 6$~PM. Thus, 100 hours from now, the time will be 6:00~PM.
%\end{solution}
%\end{eg}


\subsection{Examples of irrational numbers} \label{IrratSect}
Every rational number is a real number (in other words, $\rational \subset \real$), but it is perhaps not so obvious that some real numbers are not rational (in other words,  $\real \not\subset \rational$). 
%As an example of this, we will show that $\sqrt{2} \notin \rational$.
%Since $\rational$ is countable, but $\real$ is uncountable, there must be many, many real numbers that are not rational. 
Such numbers are said to be \define[irrational number]{irrational}. We now give one of the simplest examples of an irrational number.

\begin{prop} \label{Sqrt2Irrat}
$\sqrt{2}$ is irrational.
\end{prop}

\begin{proof}[Proof by contradiction]
Suppose $\sqrt{2}$ is rational. (This will lead to a contradiction.) By definition, this means $\sqrt{2} = a/b$ for some $a,b \in \integer$, with $b \neq 0$. By reducing to lowest terms, we may assume that $a$ and~$b$ have no common factors. In particular, 
$$ \text{it is not the case that both $a$ and~$b$ are even.}$$
We have 
	$$ \frac{a^2}{b^2} = \left(\frac{a}{b}\right)^2 = \sqrt{2}^2 = 2 ,$$
so $a^2 = 2b^2$ is even. Then \fullcref{SquareMod4or8Ex}{squareeven} tells us that 
	$$ \text{$a$~is even}, $$
so we have $a = 2k$, for some $k \in \integer$. Then
	$$2b^2 = a^2 = (2k)^2 = 4k^2 ,$$
so $b^2 = 2k^2$ is even. Then \fullcref{SquareMod4or8Ex}{squareeven} tells us that 
	$$ \text{$b$~is even}. $$
We have now shown that $a$ and~$b$ are even, but this contradicts the fact, mentioned above, that it is not the case that both $a$ and~$b$ are even.
\end{proof}

\begin{exers} \label{SqrtIrratEx} \ 
\begin{enumerate}
\item \label{SqrtIrratEx-3|n}
For $n \in \integer$, show that if $3 \notdivides n$, then $n^2 \equiv 1 \pmod{3}$.
\item \label{SqrtIrratEx-sqrt3}
Show that $\sqrt{3}$ is irrational.
\item\label{SqrtIrratEx-sqrt4}
Is $\sqrt{4}$ irrational?
\end{enumerate}
\end{exers}

\begin{rem}
The famous numbers $\pi = 3.14159\ldots$ and $e = 2.71828\ldots$ are also irrational, but these examples are much harder to prove than \cref{Sqrt2Irrat}.
\end{rem}





\section{Abstract Algebra: commutative groups} \label{GroupSect}

Every schoolchild learns about addition ($+$), subtraction ($-$), and multiplication ($\times$). Each of these is a ``binary operation'' on the set of real numbers, which means that it takes two numbers, and gives back some other number. %And we learned about some set operations, such as union and intersection: each of these takes two sets, and gives back some other set. 
In this \lcnamecref{GroupSect}, we discuss binary operations on an arbitrary set; that is, we consider various ways of taking two elements of the set and giving back some other element of the set. (The official definition of the term ``binary operation'' is in \cref{BinOpDefn}, but it suffices to have an informal understanding for the present purposes.) 

\begin{defn}[(unofficial)]
Let $A$ be a set. We say that $+$ is a \define{binary operation} on~$A$ if, for every $a,b \in A$, we have a corresponding element $a + b$ of~$A$. 

(The element $a+b$ must exist for \emph{all} $a,b \in A$. Furthermore, the sum $a + b$ must depend only on the values of $a$ and~$b$, not on any other information.)
\end{defn}

\begin{eg} \label{BinOpEgs} \ 
	\begin{enumerate}
	\item Addition ($+$), subtraction ($-$), and multiplication ($\times$) are examples of binary operations on~$\real$. They also provide binary operations on $\rational$ and~$\integer$. However, subtraction ($-$) does \emph{not} provide a binary operation on~$\natural$, because $x - y$ is not in~$\natural$ when $x < y$ (whereas the values of a binary operation on a set must all belong to the given set).
	\item Division ($\div$) is \emph{not} a binary operation on~$\real$. This is because $x \div y$ does not exist when $y = 0$ (whereas a binary operation on a set needs to be defined for \emph{all} pairs of elements of the set). (On the other hand, division is a binary operation on the set $\real \smallsetminus \{0\}$ of all nonzero real numbers.)
	\item Union ($\cup$), intersection ($\cap$), and set difference ($\smallsetminus$) are binary operations on the collection of all sets. 
	
	\item \label{BinOpEgs-hex} 
	If a set does not have too many elements, then a binary operation on it can be specified by providing an ``addition table\rlap.'' For example, the following table defines a binary operation $+$ on $\{\var{a}, \var{b}, \var{c}, \var{d}, \var{e}, \var{f} \}$:
		$$ \begin{array}{c|cccccc}
		+ & \var{a} & \var{b} & \var{c} & \var{d} & \var{e} & \var{f} \\
		\hline
		\var{a} & \var{a} & \var{b} & \var{c} & \var{d} & \var{e} & \var{f} \\
		\var{b} & \var{b} & \var{c} & \var{a} & \var{e} & \var{f} & \var{d} \\
		\var{c} & \var{c} & \var{a} & \var{b} & \var{f} & \var{d} & \var{e} \\
		\var{d} & \var{d} & \var{e} & \var{f} & \var{a} & \var{b} & \var{c} \\
		\var{e} & \var{e} & \var{f} & \var{d} & \var{b} & \var{c} & \var{a} \\
		\var{f} & \var{f} & \var{d} & \var{e} & \var{c} & \var{a} & \var{b}
		\end{array} $$
	To calculate $x + y$, find the row that has~$x$ at its left end, and find the column that has~$y$ at the top. The value $x + y$ is the entry of the table that is in that row and that column. For example, $\var{f}$ is at the left of the bottom row and $\var{e}$ is at the top of the second-to-last column, so $\var{f} + \var{e} = \var{a}$, because $\var{a}$ is the second-to-last entry of the bottom row.
	
%	\item \label{BinOpEgs-suits} 
%	If the set~$A$ has only a few elements, then a binary operation can be specified by providing an ``addition table\rlap.'' For example, the following table defines a binary operation $+$ on $\{\clubsuit, \diamondsuit, \heartsuit, \spadesuit\}$:
%		$$ \begin{array}{c|cccc}
%		+ & \clubsuit & \diamondsuit & \heartsuit & \spadesuit \\
%		\hline
%		\clubsuit & \clubsuit & \diamondsuit & \heartsuit & \spadesuit \\
%		\diamondsuit & \diamondsuit & \clubsuit & \spadesuit & \heartsuit \\
%		\heartsuit & \heartsuit & \spadesuit & \clubsuit & \diamondsuit \\
%		\spadesuit & \spadesuit & \heartsuit & \diamondsuit & \clubsuit
%		\end{array} $$
%	To calculate $x + y$, find the row that has~$x$ at its left end, and find the column that has~$y$ at the top. The value $x + y$ is the entry of the table that is in that row and that column. For example, $\spadesuit$ is in the bottom row and $\heartsuit$ is in the second-to-last column, so $\spadesuit + \heartsuit = \diamondsuit$, because $\diamondsuit$ is the second-to-last entry of the bottom row.

	\end{enumerate}
\end{eg}

\begin{defn} \label{CommGrpDefn}
Let $+$ be a binary operation on a set~$G$. 
	\begin{enumerate}
	\item $+$ is \define{commutative} iff $g + h = h + g$ for all $g,h \in G$.
	\item $+$ is \define{associative} iff $g + (h+k) = (g+h)+k$ for all $g,h,k \in G$.
	\item An element~$0$ of~$G$ is an \define[identity!element]{identity element} iff $g + 0 = g$, for all $g \in G$.
	\item For $g \in G$, a \define{negative} of~$g$ is an element $-g$ of~$G$, such that $g + (-g) = 0$, where $0$~is an identity element of~$G$.
	\item We say $(G,+)$ is a \define[commutative!group]{commutative group} iff all three of the following conditions (or ``axioms'') are satisfied:
		\begin{itemize}
		\item $+$~is commutative and associative, 
		\item there is an identity element, 
		and 
		\item every element of~$G$ has a negative.
		\end{itemize}
	\end{enumerate}
\end{defn}

\begin{otherterm}
For historical reasons, most mathematicians use the term ``\index{abelian group}abelian group\rlap,'' rather than ``commutative group\rlap,'' but they would agree that ``commutative group'' is also acceptable.
\end{otherterm}

\begin{egs} \ 
	\begin{enumerate}
	\item $(\real,+)$ is a commutative group: we all learned in elementary school that addition is commutative and associative, that $g + 0 = g$, and that $g + (-g) = 0$. (The same is true for $(\rational,+)$ and $(\integer,+)$.)
	\item $(\natural,+)$ is \emph{not} a commutative group (even though addition is commutative and associative, and $0$~is an identity element), because no nonzero element has a negative in~$\natural$.
	\item $(\real,-)$ is \emph{not} a commutative group, because subtraction is not commutative: $g - h$ is usually not equal to $h - g$. (Another reason $(\real,-)$ is not a commutative group is that subtraction is not associative: $(g - h) - k$ is usually not equal to $g - (h - k)$.)
	\item $(\real,\times)$ is \emph{not} a commutative group (even though addition is commutative and associative, and $1$~is an identity element for multiplication), because $0$ does not have a ``negative'' or ``multiplicative inverse'': there does not exist $h \in \real$, such that $0 \times h = 1$.
	\end{enumerate}
\end{egs}

\begin{otherterm}
Our condition to be an identity element is what is usually called a ``right identity element\rlap.'' For $0$ to be an identity element, it should be true not only that $g + 0 = g$, but also that $0 + g = g$. However, the only binary operations of interest to us are commutative groups, where the second condition is also satisfied (see \fullcref{FirstGrpExers}{0+g} below), % !!! 
so there is no need for us to make this distinction.
\end{otherterm}

\begin{exer} \label{BinopTableEx}
For the binary operation on $\{\var{a}, \var{b}, \var{c}, \var{d}, \var{e}, \var{f} \}$ in \fullcref{BinOpEgs}{hex}, verify that:%
\noprelistbreak
	\begin{tasks}
	\task\fixtask \label{BinopTableEx-e}
	$\var{a}$ is an identity element,
	and
	\task\fixtask \label{BinopTableEx-neg}
	every element has a negative, namely:
	$-\var{a} = \var{a}$, 
	$-\var{b} = \var{c}$, 
	$-\var{c} = \var{b}$, 
	$-\var{d} = \var{d}$, 
	$-\var{e} = \var{f}$, 
	$-\var{f} = \var{e}$.
	\end{tasks}
\end{exer}

The following result tells us that, instead of \emph{an} identity element of a commutative group, we may speak of \emph{the} identity element. 

\begin{prop} \label{GrpUniqueId}
The identity element of any commutative group is unique.
\end{prop}

\begin{proof}
Suppose $0$ and~$\theta$ are any identity elements of a commutative group $(G,+)$. Then
	\begin{align*}
	0 
	&= 0 + \theta && \text{($\theta$ is an identity element)} \\
	&= \theta + 0 && \text{($+$ is commutative)} \\
	&= \theta && \text{($0$ is an identity element)} 
	. \end{align*}
Since $0$ and~$\theta$ are arbitrary identity elements of $(G,+)$, this implies that all identity elements are equal to each other, so the identity element is unique (there is only one of them).
\end{proof}

\begin{notation}
In this \lcnamecref{GroupSect}, the symbol~$0$%
\nindex{$0$}
will always represent the identity element of whatever commutative group is under consideration. 

\emph{Warning:} This means that $0$ will usually \emph{not} represent the number zero. For example, in \fullcref{BinOpEgs}{hex}, we have $0 = \var{a}$.
\end{notation}

Similarly, instead of \emph{a} negative, we may speak of \emph{the} negative of an element of~$G$:

\begin{prop} \label{GrpUniqueInv}
Let $(G,+)$ be a commutative group. For each $g \in G$, the negative of~$g$ is unique.
\end{prop}

\begin{proof} Suppose $-g$ and~$h$ are any negatives of~$g$. Then
	\begin{align*}
	-g
	&= -g + 0 && \text{($0$ is the identity element)} \\
	&= -g + (g + h) && \text{($h$ is a negative of~$g$)} \\
	&= (-g + g) + h && \text{($+$ is associative)} \\
	&= h + \bigl(g + (-g) \bigr) && \text{($+$ is commutative)} \\
	&= h + 0 && \text{($-g$ is a negative of~$g$)} \\
	&= h && \text{($0$ is the identity element)} 
	. \end{align*}
Therefore, all negatives of~$g$ are equal, so the negative is unique.
\end{proof}

\begin{prop} \label{Neg(0)}
For every commutative group $(G,+)$, we have $-0 = 0$.
\end{prop}

\begin{proof}
Let $g = 0$. Then $g$~is the identity element, so $0 + g = 0$. By definition of the negative, this means that $g = -0$. Since $g = 0$, we conclude that $0 = -0$.
\end{proof}

\begin{notation}
Assume $(G,+)$ is a commutative group. For $g,h \in G$, we use $g - h$%
	\nindex{$g - h$}
as an abbreviation for $g + (-h)$.
\end{notation}

\begin{exers} \label{FirstGrpExers}
Assume $(G,+)$ is a commutative group, and $g,h \in G$.
\\ \emph{Carefully justify each step of your proofs, using only the axioms stated in \cref{CommGrpDefn}. 
\\ Do \underline{not} assume any other properties of addition that you were taught in school.}
	\begin{tasks}(2)
	\task\fixtask \label{FirstGrpExers-0+g}%
	Show $0 + g = g$.
	\task\fixtask  \label{FirstGrpExers-(-g)+g}%
	Show $(-g) + g = 0$.
	\task\fixtask  \label{FirstGrpExers-gming}%
	Show $g - g = 0$.
	\task\fixtask \label{FirstGrpExers-min(-g)}%
	%Since $-g$ is an element of~$G$, it has a negative. Specifically, show that the negative of~$-g$ is~$g$. In symbols: 
	Show $-(-g) = g$.
	\task\fixtask \label{FirstGrpExers-(-g)+h}%
	Show $(-g) + h = h - g$.
	\task\fixtask \label{FirstGrpExers-(g-h)+h}%
	Show $(g-h) + h = g$.
%	\task\fixtask \label{FirstGrpExers-solve}%
%	Show $\exists x \in G$, such that $g + x = h$.
	\end{tasks}
\end{exers}

The associative law tells us that $(g + h) + k = g + (h + k)$. Therefore, we learn in elementary school to simply write $g + h + k$, because it does not matter where the parentheses go. Officially, the associative law In fact (as we also learn in elementary school), there is no need to include parentheses in any sum (even if it has more than three terms). Also, the commutative law tells us that $g + h = h + g$. We learn in elementary school that this allows us to rearrange the terms in a sum of any length, and the same is true for commutative groups. For example:
	$$g_1 + g_2 + g_3 + g_4 + g_5 = g_4 + g_3 + g_1 + g_5 + g_2 .$$
Here is an official statement of these observations:

\begin{prop} 
If $(G,+)$ is a commutative group, $n \in \natural^+$, and $g_1,g_2,\ldots,g_n \in G$, then: 
	\begin{enumerate}
	\item \textup($+$ is \define{associative}\textup) The expression 
	$ g_1 + g_2 + \cdots + g_n $
	represents a well-defined element of~$G$, which does not depend on how the expression is parenthesized.
	\item \textup($+$ is \define{commutative}\textup) If $h_1,h_2,\ldots,h_n$ is a list of the same elements of~$G$, but perhaps in a different order, then
		$$ h_1 + h_2 + \cdots + h_n = g_1 + g_2 + \cdots + g_n .$$
	\end{enumerate}
\end{prop}

\begin{eg} \label{Neg(g+h)}
Assume $(G,+)$ is a commutative group, and $g,h \in G$.
Show 
	$$-(g + h) =  (-g) + (-h) .$$
\end{eg}

\begin{proof}
We have
	\begin{align*}
	(g + h) + \bigl( (-g) + (-h) \bigr)
	&= g + h + (-g) + (-h)
		&& \text{($+$ is associative)}
	\\&= g + (-g) + h + (-h)
		&& \text{($+$ is commutative)}
	\\&= \bigl( g + (-g) \bigr) + \bigl( h  + (-h) \bigr)
		&& \text{($+$ is associative)}
	\\&=  0  + 0 
		&& \text{(definition of $-g$ and $-h$)}
	\\&=  0
		&& \text{($0$ is the identity element)}
	. \end{align*}
So $(-g) + (-h)$ is the negative of $g + h$. In other words, $(-g) + (-h) = -(g + h)$.
\end{proof}

\begin{exers} \label{HaveLawsGrpExers}
Assume $(G,+)$ is a commutative group, and $g,h,a \in G$.
	\begin{tasks}(2)
	\task\fixtask \label{HaveLawsGrpExers-min(g-h)}%
	Show $-(g - h) = h - g$.
	\task\fixtask \label{HaveLawsGrpExers-cancel}% %(\define{cancellation})
	Show that if $g + a = h + a$, then $g = h$.
	\end{tasks}
\end{exers}

\begin{defn} \label{SubgrpDefn}
Let $(G,+)$ be a commutative group. A subset~$H$ of~$G$ is a \define{subgroup} of $(G,+)$ iff 
	\begin{enumerate}
	\item \label{SubgrpDefn-nonempty}
	$H \neq \emptyset$,
	\item \label{SubgrpDefn-neg}
	(\define[closed under!negatives]{closed under negatives}) $-h \in H$, for all $h \in H$,
	and
	\item \label{SubgrpDefn-add}
	(\define[closed under!addition]{closed under addition}) $h_1 + h_2 \in H$, for all $h_1,h_2 \in H$.
	\end{enumerate}
\end{defn}

\begin{eg}
$\integer$ and $\rational$ are subgroups of $(\real,+)$, but $\natural$~is \textbf{not} a subgroup (because it is not closed under negatives).
\end{eg}

\begin{prop} \label{0inH}
If $H$ is a subgroup of a commutative group $(G,+)$, then $0 \in H$ \textup(where, as usual, $0$~is the identity element of~$(G,+)$\textup).
\end{prop}

\begin{proof}
We know that $H \neq \emptyset$ (from the definition of subgroup), so there is some $h \in H$. Since $H$ is closed under negatives (because it is a subgroup) this implies $-h \in H$. Then, since $H$ is closed under addition (because it is a subgroup), we have $h + (-h) \in H$. Since $h + (-h) = 0$ (by the definition of~$-h$), this means $0 \in H$.
\end{proof}

\begin{exers} \label{SubgrpEx}
Assume $H$ is a subgroup of a commutative group $(G,+)$, and $h,k \in H$.
	\begin{enumerate}
	\item \label{SubgrpEx-diff}
	Show $h - k \in H$.
	\item \label{SubgrpEx-notin}
	For all $a \in G$, show that if $a \notin H$, then $a + h \notin H$.
	\end{enumerate}
\end{exers}

\begin{exers} \label{CosetEx}
Assume $H$ is a subgroup of a commutative group~$(G,+)$, and $a,b \in G$. Let 
	$a + H = \{\, a+h \mid h \in H\,\}$ and $b + H = \{\, b+h \mid h \in H\,\}$. 
	\begin{enumerate}
	\item \label{CosetEx-subgrp}
	Show that if $a + H$ is a subgroup of~$G$, then $a \in H$.
	\hint{Every subgroup contains~$0$.}
	\item \label{CosetEx-inH}
	Show that if $a \in H$, then $a + H = H$.
	\item \label{CosetEx-=}
	Show that $a + H = b + H$ iff $a - b \in H$.
	\item \label{CosetEx-intersect}
	Show that if $(a + H) \cap (b + H) \neq \emptyset$, then $a + H = b + H$.
	\end{enumerate}
\end{exers} 

\begin{prop} \label{2Torsion}
Assume $(G,+)$ is a commutative group, and let $T = \{ t \in G \mid t + t = 0 \}$. % deleted \, to avoid overfull !!!
Then $T$ is a subgroup of~$G$.
\end{prop}

\begin{proof}
It suffices to show that $T$ is: nonempty, closed under negatives, and closed under addition.

(nonempty) We have $0 \in T$ (because it is immediate that $0 + 0 = 0$), so $T \neq \emptyset$.

(closed under negatives) Given $t \in T$, we have
	\begin{align*}
	 (-t) + (-t) 
	 &= -(t + t) && \text{(\cref{Neg(g+h)})}
	 \\& = - 0 && \text{($t \in T$)}
	 \\&= 0 && \text{(\cref{Neg(0)})}
	 . \end{align*}
This means $-t \in T$, so $T$~is closed under negatives.

(closed under addition) Given $s,t \in T$, we have $s + s = 0$ and $t + t = 0$. Therefore
	\begin{align*}
	(s + t) + (s + t)
	&= (s + t) + (t + s) && \text{($+$ is commutative)} \\
	&= s + \bigl( t + (t + s) \bigr) && \text{($+$ is associative)} \\
	&= s + \bigl( (t + t) + s \bigr) && \text{($+$ is associative)} \\
	&= s + ( 0 + s ) && \text{($t \in T$)} \\
	&= s + s && \text{($0$ is the identity element)} \\
	&= 0 && \text{($s \in T$)}
	, \end{align*}
so $s + t \in T$. Therefore $T$ is closed under addition.
\end{proof}

\begin{exers} \label{HKEx}
Assume $H$ and $K$ are subgroups of a commutative group~$(G,+)$.
	\begin{enumerate}
	\item \label{HKEx-HcapK}
	Show that $H \cap K$ is a subgroup of $(G,+)$.
	\item \label{HKEx-H+K}
	Let $H + K = \{\, h + k \mid h \in H, k \in K \,\}$. Show that $H + K$ is a subgroup of $(G,+)$.
	\end{enumerate}
\end{exers}





\goodbreak

\section{Real Analysis: convergent sequences} \label{SequenceSect}

\begin{notation}
For $x \in \real$, $|x|$%
\nindex{$|x|$}
 denotes the \define{absolute value} of~$x$:
	$$|x| = \begin{cases}
	\hfill x & \text{if $x \ge 0$} , \\
	\hfill -x & \text{if $x < 0$} 
	. \end{cases}$$
\end{notation}

You may assume the following basic properties of absolute value (without proof):

\begin{lem} \label{AbsValProps}
For $x,y,z \in \real$, we have:
	\begin{tasks}(2)
	\task\fixtask  \label{AbsValProps->0}%
	$|x| \ge 0$ \ \textup(and $|x| = 0 \eiff x = 0$\textup).
	\task\fixtask \label{AbsValProps-minusx}%
	$|x| = |{-x}|$.
	\task\fixtask $|x + y| \le |x| + |y|$.  {\normalfont(``\define{triangle inequality}'')} % normalfont !!!
	\task\fixtask \label{AbsValProps-product}%
	 $|xy| = |x| \cdot |y|$.
	\task\fixtask \label{AbsValProps-between}%
	$-|x| \le x \le |x|$.
	\task\fixtask \label{AbsValProps-N}%
	$\exists N \in \natural$, $N > |x|$.
	\task\fixtask If $|x| < |y|$ and $z \neq 0$, then $|xz| < |yz|$.
	\task\fixtask  \label{AbsValProps-1/x}%
	If $|x| > |y| \neq 0$, then $1/|x| < 1/|y|$.
	\end{tasks}
\end{lem}

\begin{defn}
Assume $a_1,a_2,a_3,\ldots$ is an infinite sequence of real numbers, and $L \in \real$. We say that the sequence \define{converges} to~$L$ (and write $a_n \to L$%
\nindex{$a_n \to L$})
 iff
	$$ \forall \epsilon > 0, \ \exists N \in \natural, \ \forall n > N, \ |a_n - L| < \epsilon . $$
\end{defn}

\begin{otherterm}
When $a_n \to L$, we can also say that the \define{limit} of the sequence is~$L$.
\end{otherterm}

\begin{eg} \label{constconv}
Let $t \in \real$. If $a_n = t$ for all~$n$, then $a_n \to t$.
\end{eg}

\begin{proof}
Given $\epsilon > 0$, let $N = 0$. Given $n > N$, we have
	$ |a_n - t| = |t - t| = |0| = 0 < \epsilon $.
\end{proof}

\begin{eg}
If $a_n = 1/n$ for all~$n$, then $a_n \to 0$.
\end{eg}

\begin{scratchwork}
To prove $a_n \to 0$, we want:
	\begin{align*}
	|a_n - 0| &\stackrel{?}{<} \epsilon &
	1/n &\stackrel{?}{<} \epsilon &
	1/\epsilon &\stackrel{?}{<} n 
	\end{align*}
Since $n > N$, it suffices to choose $N > 1/\epsilon$.
\end{scratchwork}

\begin{proof}
Given $\epsilon > 0$, \fullcref{AbsValProps}{N} tells us there exists $N \in \natural$, such that $N > 1/\epsilon$. Given $n > N$, we have
	\begin{align*}
	|a_n - 0| 
	&= 1/n && \text{($a_n = 1/n > 0$)}
	\\&< 1/N && \text{($n > N$ and \fullcref{AbsValProps}{1/x})}
	\\&< \epsilon && \text{($N > 1/\epsilon$ and \fullcref{AbsValProps}{1/x})}
	. \end{align*}
\end{proof}

\begin{exer} \label{Converge1Ex}
Show that if $a_n = n/(n+1)$ for all~$n$, then $a_n \to 1$.
\end{exer}

\begin{prop} \label{ConvSum}
If $a_n \to L$ and $b_n \to M$, then $a_n + b_n \to L + M$.
\end{prop}

\begin{scratchwork}
To prove $a_n + b_n \to L + M$, 
	$$ \text{we want to make $|(a_n + b_n) - (L + M)|$ small (less than~$\epsilon$).} $$
What we know is that we can make $|a_n - L|$ and $|b_n - M|$ as small as we like. By the triangle inequality, we have
	$$ \bigl| (a_n - L) + (b_n - M) \bigr| < |a_n - L| + |b_n - M| .$$
By simple algebra, the left-hand side is equal to $|(a_n + b_n) - (L + M)|$, so we just need to make the right-hand side less than~$\epsilon$. This will be true if $|a_n - L|$ and $|b_n - M|$ are both less than $\epsilon/2$.

Since $a_n \to L$, there is some large $N_a$, such that $|a_n - L| < \epsilon/2$ for all $n > N_a$. Similarly, since $b_n \to M$, there is some large $N_b$, such that $|b_n - M| < \epsilon/2$ for all $n > N_b$. Now, we just need know that $n$ will be larger than both $N_a$ \underline{and}~$N_b$ whenever $n > N$. So we should choose $N$ to be whichever of~$N_a$ and~$N_b$ is larger. That is, we let $N$ be the \define{maximum} of~$N_a$ and~$N_b$, which is denoted $ \max(N_a,N_b)$. % notation index? !!!
\end{scratchwork}

\begin{proof}
Given $\epsilon > 0$, we know that $\epsilon/ 2 > 0$. Hence:
	\begin{itemize}
	\item Since $a_n \to L$, we know $\exists N_a \in \natural, \ \forall n > N_a, \ |a_n - L| < \epsilon/2$.
	\item Since $b_n \to M$, we know $\exists N_b \in \natural, \ \forall n > N_b, \ |b_n - M| < \epsilon/2$.
	\end{itemize}
Let $N = \max(N_a,N_b) \in \natural$, so $N \ge N_a$ and $N \ge N_b$.

Given $n > N$:
	\begin{enumerate} \renewcommand{\labelenumi}{(\theenumi)} % !!!
		\renewcommand{\theenumi}{$*$} 
	\item \label{SumOfLimits-an}
	We have $n > N \ge N_a$, so $|a_n - L| < \epsilon/2$.
		\renewcommand{\theenumi}{$**$}
	\item \label{SumOfLimits-bn}
	We have $n > N \ge N_b$, so $|b_n - M| < \epsilon/2$.
	\end{enumerate}
Therefore
	\begin{align*}
	\bigl| (a_n + b_n) - (L + M) \bigr|
	&= \bigl| (a_n - L) + (b_n - M) \bigr| && \text{(high-school algebra)}
	\\&\le |a_n - L| + |b_n - M| && \text{(triangle inequality)}
	\\&< {\epsilon}/{2} \ + \ {\epsilon}/{2} && \text{(\pref{SumOfLimits-an} and \pref{SumOfLimits-bn})}
	\\&= \epsilon
	. \end{align*}
\end{proof}

\begin{exers} \label{ConvEx}
Assume $a_n \to L$, and $c \in \real$.
\\ \emph{Do these proofs directly from the definition of convergence.}
\begin{tasks}(2)
\task\fixtask \label{ConvEx-min(an)}
Show $- a_n \to -L$.
\task\fixtask \label{ConvEx-an+c}
Show $a_n + c \to L + c$.
\task\fixtask \label{ConvEx-2an}
Show $2 a_n \to 2L$.
\task\fixtask \label{ConvEx-can}
Show $c a_n \to cL$ if $c \neq 0$.
\task*\fixtask \label{ConvEx-an>0}
Show that if $L > 0$, then $\exists N \in \natural$, such that $a_n > 0$ for all $n > N$.
\task*\fixtask (\emph{harder}) \label{ConvEx-L=1}
Show that if $L = 1$, then $1/a_n \to 1$.
\end{tasks}
\end{exers}

\begin{exers} \label{ConvabEx}
Assume $a_n \to L$ and $b_n \to M$.
\begin{enumerate}
\item \label{ConvabEx-0}
Show that if $M = 0$, and $|a_n| \le 2$ for all~$n$, then $a_n b_n \to 0$.
\item (\emph{harder}) \label{ConvabEx-LM}
Show $a_n b_n \to LM$.
\end{enumerate}
\end{exers}

%The same sequence cannot converge to two different numbers:
%
%\begin{prop}
%If $a_n \to L$ and $a_n \to M$, then $L = M$.
%\end{prop}
%
%\begin{proof}[Proof by contradiction]
%Suppose $L \neq M$ (so $L - M \neq 0$). Then, letting $\epsilon = |L - M|/2$, we have $\epsilon > 0$. 
%	\begin{itemize}
%	\item Since $a_n \to L$, we know $\exists N_L \in \natural, \ \forall n > N_L, \ |a_n - L| < \epsilon$.
%	\item Since $a_n \to M$, we know $\exists N_M \in \natural, \ \forall n > N_M, \ |a_n - M| < \epsilon$.
%	\end{itemize}
%Choose some $n > \max(N_L,N_M)$, so $n > N_L$ and $n > N_M$. Then
%	\begin{align*}
%	|L - M|
%	&= \bigl| -(a_n - L) + (a_n - M)| && \text{(high-school algebra)}
%	\\&\le \bigl| -(a_n - L) \bigr|+ \bigl| a_n - M \bigr| && \text{(triangle inequality)}
%	\\&= | a_n - L |+ | a_n - M | && \text{(\fullcref{AbsValProps}{minusx})}
%	\\&< \epsilon + \epsilon && \text{($n > N_L$ and $n > n_M$)}
%	\\&= |L - M| && \text{(definition of~$\epsilon$)}
%	. \end{align*}
%This is a contradiction.
%\end{proof}




\begin{summary}
\item A valid deduction (or ``result'') is usually called a theorem, proposition, corollary, or lemma.
% Each term is used differently; these differences were discussed.

\medskip % !!!

\item \textbf{Divisibility and congruence}
    \begin{itemize}
    \item Important definitions:
        \begin{itemize}
        \item divisor, multiple
        \item congruent modulo $n$: $a \equiv b \pmod{n}$
        \item remainder
        \item irrational number
        \end{itemize}
%    \item Proofs using divisibility.
    \item Congruence (mod~$n$) is reflexive, symmetric, and transitive
    %\item Divisibility (mod~$n$) is reflexive and transitive, but not symmetric.
    \item $a \equiv b \pmod{n}$ \ iff \ $a$ and $b$ have the same remainder when divided by~$n$
    \item $\sqrt{2}$ is irrational
    \item Notation:
        \begin{itemize}
        \item $a \divides b$, $a \notdivides b$
        \item $a \equiv b \pmod{n}$
        \end{itemize}
    \end{itemize}

\item \textbf{Commutative groups}
    \begin{itemize}
    \item Important definitions:
        \begin{itemize}
%        \item binary operation
%        \item commutative, associative, identity element, negative
        \item commutative group (commutative, associative, identity element, negatives)
        \item subgroup (closed under negatives and addition)
%        \item closed under: negatives, addition
        \end{itemize}
    \item The identity element of a group is unique.
    \item The negative of each element of a group is unique.
    \item Notation:
        \begin{itemize}
        \item $\phantom{-}0$ \quad (identity element)
        \item $-g$ \quad (negative)
        \end{itemize}
    \end{itemize}

\item \textbf{Convergent sequences}
    \begin{itemize}
    \item Important definitions:
        \begin{itemize}
        \item absolute value
        \item converges
%        \item closed under: negatives, addition
        \end{itemize}
    \item triangle inequality
    \item Notation:
        \begin{itemize}
        \item $|x|$
        \item $a_n \to L$
        \end{itemize}
    \end{itemize}


\end{summary}
