Real-Analysis.tex

\documentclass[]{article}
\input{../mathdoc}
\input{../mathsym}
\input{../theorem}

\author{Presenter: Maya Chhetri, Notes by Michael Reed, Book: Walter Rudin 3rd}
\title{Real Analysis}
\date{Fall 2017, \today}

\begin{document}
\maketitle

%\begin{abstract}
%\end{abstract}

\section{The Real and Complex Number System}

\ul{Notation}: 

$\mb{N} = \{0,1,2,3,\dots\}$ - set of natural numbers.

$\mb Z = \{0,\pm 1, \pm 2,\dots\}$ - set of integers.

$\mb Q = \{\frac{m}{n}:m,n\in\mb Z,\, n\neq 0\}$ - set of rationals $\ra$ we know $\mb Q$.

$\mb R$ - set of all real numbers.

$\mb C = \{a+ib: a,b\in\mb R \text{ and } i^2 = -1\}$.

\ul{Sets} - collection of objects. Empty set - $\emptyset$ - a set which contains no objects.
$A\subset B$ if $a\in A \implies a\in B$ for all $a\in A$.
\begin{example}
	$A\varsubsetneq B$ - a proper subset if $A\subset B$ and $\exists x_0 \in B$ such that $x_0 \notin A$.
\end{example}
\begin{note}
	$A = B$ iff $A\subset B$ and $B\subset A$.
\end{note}

\ul{Order on a set}: Let $S$ be a set. An order, denoted by '$<$' is a \ul{relation} on $S$ satisfying:
\begin{enumerate}
	\item[(i)] If $x,y\in S$ then one of the following must hold:
	$x<y$, $x = y$, $y<x$.
	\item[(ii)] If $x,y,z\in S$ with $x<y$ and $y<z$ then $x<z$ (transitive property).
\end{enumerate}
\begin{example}
	$S = \mb N$ with \say{$<$} ($x<y$ if $y-x>0$) is an ordered set.
\end{example}
\begin{definition}
	[Upper bound] Let $(S,<)$ be an ordered set, $E\subset S$. We say that $\beta$ is an \ul{upper bound of $E$} if $s\leq\beta$ for all $s\in E$.
\end{definition}
\begin{definition}
	[Lower bound] $\alpha$ is a \ul{lower bound of $E$} if $\alpha \leq s$ for all $s\in E$.
\end{definition}

\begin{example}
	$(S = \mb Q,<)$ and
	\begin{enumerate}
		\item $E = \{x \in \mb Q: 0\leq x < 1\}$. $\beta = 1$ is an upper bound of $E$ and $1\notin E$. $\beta \geq 1$ are upper bounds of $E$. $\alpha = 0$ is a lower bound of $E$ and $0\in E$. $\alpha \leq 0$ are lower bounds of $E$.
	\end{enumerate}
\end{example}
\begin{definition}
	[Least upper bound] Let $E\subset (S,<)$. We say that $\alpha \in S$ is the least upper bound or supremum of $E$ if:
	\begin{itemize}
		\item[(i)] $\alpha$ is an upper bound of $E$, and
		\item[(ii)] if $\gamma$ is an upper bound of $E$, then $\alpha \leq \gamma$ (or $\gamma $ is not an upper bound for any $\gamma < \alpha$).
	\end{itemize}
\end{definition}
\ul{We write}: $\alpha = \text{lub} E$ or $\alpha = \sup E$.
\begin{example}
	[continued] $\sup E = 1 \notin E$, $\inf = 0 \in E$. $\max E$ is a the $\sup E$ and it belongs to $E$.
\end{example}

Rational numbers $\mb Q$ has holes.
\begin{lemma}
	$\sqrt{2} \notin \mb Q$. That is $x^2 = 2$ has no solution in $\mb Q$.
\end{lemma}
\begin{proof}
	We will prove by contradiction (BWOC). Suppose $\sqrt{2} \in \mb Q$. Then $\sqrt{2} = \frac{m}{n}$, with $m,n\in \mb Z$, $n\neq 0$ and $\frac{m}{n}$ in least terms or $\gcd (m,n) = 1$. Then $2 = \frac{m^2}{n^2} \implies m^2 = 2n^2$. Then $m^2$ is even. \ul{So $m$ is even}.
	\begin{proof}
		Suppose $m$ is odd. Then $m = 2k + 1$ for some $k \in \mb Z$. $\implies m^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 \implies m^2$ is odd, a contradiction. So $m$ must be even.
	\end{proof}
	Then $m = 2l$ for some $l\in \mb Z$. Then $(2l)^2 = 2n^2 \implies 4l^2 = 2n^2 \implies 2l^2 = n^2$. So $n^2$ is even and hence $n$ is even. This is a contradiction to $\frac{m}{n}$ being in least terms. So $\sqrt{2} \notin \mb Q$.
\end{proof}

\begin{example}
	Prove that $\sup E = 1$ if $E = \{x \in \mb Q : 0 \leq x < 1\}$.
	\begin{enumerate}
		\item[(i)] Clearly $x<1$ for all $x\in E$. So $1$ is an upper bound of $E$.
		\item[(ii)] If $\gamma < 1$ then $\gamma$ is not an upper bound of $E$. If $\gamma \leq 0$, then clearly $\gamma$ is not an upper bound of $E$. If $0<\gamma < 1$, then $x = \frac{\gamma + 1}{2}$. But $\gamma < x\in E$ by construction, so $\gamma$ is not an upper bound. Therefore \ul{$ \sup E = 1$}.
	\end{enumerate}
\end{example}

\begin{theorem}
	[Uniqueness of supremum] Let $(S,<)$ be an ordered set. If $E\subset S$ has supremum (or infimum) in $S$, then it is unique.
	\begin{proof}
		Let $\alpha_1 = \sup E$ and $\alpha_2 = \sup E$. Then by definition $\alpha_1$ and $\alpha_2$ are upper bounds of $E$. But $\alpha_1 = \sup E$ and $\alpha_2$ is an upper bound of $E$, so $\alpha_1 \leq \alpha_2$. Switching roles of $\alpha_1$ and $\alpha_2$, we get $\alpha_2 \leq \alpha_1$. Combining these two, $\alpha_1 = \alpha_2$. So $\sup E$ is unique.
	\end{proof}
\end{theorem}
\begin{example}
	$A := \{ x\in\mb Q : x>0 \text{ and } x^2 \leq 2\}$. $B:=\{ x\in\mb Q: x>0 \text{ and } x^2\geq 2\}$. $A\cap B = \{ x \in\mb Q : x>0 \text{ and } x^2 = 2\} = \emptyset$ - showed.
	\begin{enumerate}
		\item $A$ is bounded above in $\mb Q$ ($B$ is bouned below in $\mb Q$).
		If $a\in A$ and $b\in B$ then $a\leq b$.
		\item There is no upper bound of $A$ in $A$.
		Let $p>0\in \mb Q$ be fixed and arbitrary. Set $q:= p - \frac{p^2-2}{p+2} = \frac{2(p+2)}{p+2}$. $q^2-2 = \frac{4p^2 + 8p +4}{(p+2)} - 2 = \frac{4p^2 + 8p + 4 - 2p^2 - 8p - 8}{(p+2)^2} = \frac{2(p^2-2)}{(p+2)^2}$. So, $q^2 < 2$ if and only if $p^2 < 2$. Therefore $q\in A$ if and only if $p\in A$.
		
		Suppose $p\in A$ is an upper bound of $A$. Then $q = \frac{2p+2}{p+2} > p$ and $q\in A$. Therefore $p$ cannot be an upper bound of $A$.
		\item $A$ has no least upper bound or supremum in $\mb Q$.
		$B$ is the set of upper bounds of $A$. Repeating the argument of 2. for $B$, there is no lower bound of $B$ in $B$.
		That means $A$ has no least upper bound in~$\mb Q$.
	\end{enumerate}
\end{example}

\begin{definition}
	[Least upper bound property] Let $(S,<)$ be an ordered set. Then $S$ is said to have the least upper bound property if every nonempty subset of $S$ that is bounded above has supremum in $S$ i.e., $\forall E\subset S$ with $E\neq \emptyset$ and bounded above, $\sup E \in S$.
\end{definition}
\begin{example}
	$(Q,<)$ (usual ordering) does not have least upper bound property.
	
	\begin{proof}
		[Reason] $A = \{x\in\mb Q: x>0 \text{ and } x^2\leq 2\}\subset \mb Q$. 
		\begin{itemize}
			\item $A\neq\emptyset$ since $1\in \mb Q$.
			\item $A$ is bounded above (by $B$).
		\end{itemize}
		But $\sup A$ does not exist in $\mb Q$
	\end{proof}
\end{example}

\begin{theorem}
	Let $(S,<)$ with the least upper bound property. Let $B\subset S$ with $B\neq \emptyset$ and $B$ is bounded below.
	Set $L = $ set of all lower bounds of $B$. Then $\alpha = \sup L$ exists in $S$, and $\alpha = \inf B$.
\end{theorem}
	\begin{proof}
		First, we want to show:
		\begin{enumerate}
			\item[(i)] $L$ is nonempty, and
			\item[(ii)] $L$ is bounded above.
		\end{enumerate}
		$L$ is nonempty since $B$ is bounded below and hence $\exists l\in S$ such that $l\leq b$ for all $b\in B$. By definition of $L$, $l \leq b$ for all $l\in L$ and $\forall b\in B$ and $B\neq\emptyset$. So $L$ is bounded above.
		By the least upper bound property of $S$, $\sup L\in S$. Define $\alpha = \sup L$. \ul{We claim}:
		\begin{enumerate}
			\item[(a)] $\alpha$ is a lower bound of $B$, and
			\begin{proof}
				$\alpha = \sup L$ and if $b\in B$ then $\alpha \geq l$ for all $l\in L$. But $l\leq b$ for $b\in B$, so $b$ is an upper bound of $L$. Therefore, $\alpha \leq b$ since $\alpha = \sup L$.
			\end{proof}
			\item[(b)] $\gamma>\alpha$ is not a lower bound of $B$.
			\begin{proof}
				If $\gamma > \alpha$ then $\gamma \notin L$ and so $\alpha = \inf B$.
			\end{proof}
		\end{enumerate}
		(a), (b) $\implies \alpha = \inf B$.
	\end{proof}

\begin{definition}
	[Field] A field $F$ is a set with two operations
	\begin{itemize}
		\item addition '+'
		\item multiplication '$\cdot$'
	\end{itemize}
	Satisfying the following axioms:
	\begin{enumerate}
		\item[(A1)] $x+y \in F$, $\dots$ (A5).
		\item[(M1)] $x\cdot y \in F$, $\dots$ (M5).
		\item[(D)] $x\cdot(y+z) = x\cdot y + x\cdot z$ for all $x,y,z\in F$.
	\end{enumerate}
\end{definition}

\begin{proposition}
	\label{prop1.14}
	Let $(F,+\cdot)$ be a field. Then for $x,y,z\in F$,
	\begin{enumerate}
		\item[(a)] If $x+y = x+z$, then $y = z$. (Cancellation law)
		\item[(b)] If $x+y = x$, then $y = 0$.
		\item[(c)] If $x+y = 0$, then $y = -x$.
		\item[(d)] $-(-x)=x$.
	\end{enumerate}
\end{proposition}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] $y \os{A4}{=} 0+y \os{A5}{=} (-x+x) + y \os{A3}{=} -x+(x+y) \os{A3}{=} -x+(x+z)\equiv (-x+x)+z \os{A5}{=} 0+z \os{A4}{=} z$
		\item[(b)] Taking $z=0$ in (a), we get $x+y = x+0 \implies y=0$.
		\item[(d)] Let $x\in F$. Then $-x\in F$ such that $x+(-x)=0$. Since $-x\in F$, $\exists -(-x)\in F$ such that $-(-x)+(-x)=0$. So $x$ and $-(-x)$ are additive inverse of $-x$, by (c) $x=-(-x)$.
	\end{enumerate}
Done.
\end{proof}

\begin{proposition}
	Let $(F,+,\cdot)$ a field with $x,y,z\in F$. Then
	\begin{enumerate}
		\item[(a)] If $x\neq 0$ and $xy=xz$ then $y=z$.
		\begin{proof}
			Let $x\neq 0$ and $xy = xz$. $y \os{M4}{=} 1\cdot y \os{M5}{=} (\frac{1}{x}\cdot x)\cdot y \os{M3}{=} \frac{1}{x}(xy) \equiv \frac{1}{x}(xz) \os{M3}{=} (\frac{1}{x}\cdot x)\cdot z \os{M5}{=} 1\cdot z \os{M4}{=} z$
		\end{proof}
		\item[(b)] If $x\neq 0$ and $xy=x$ then $y=1$.
		\item[(c)] If $x\neq 0$ and $xy = 1$ then $y=\frac{1}{x}$.
		\item[(d)] If $x\neq 0$, then $\frac{1}{1/x} = x$.
	\end{enumerate}
\end{proposition}

\begin{proposition}
	\label{prop1.16}
	Let $x,y,z\in (F,+,\cdot)$ field. Then
	\begin{enumerate}
		\item[(a)] $0\cdot x = 0$
		\item[(b)] If $x\neq 0$ and $y\neq 0$ then $xy\neq 0$.
		\item[(c)] $(-x)y = -(xy) = x(-y)$.
		\item[(d)] $(-x)(-y) = xy$.
	\end{enumerate}
\end{proposition}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] $0\cdot x = (0+0)\cdot x \os{D}{=} 0\cdot x + 0\cdot x$. Then $0\cdot x = 0$ (Proposition \ref{prop1.14}(b)).
		\item[(b)] We'll prove by contradiction. Let $x\neq 0$, $y\neq 0$ but $xy=0$. Then $1 \os{M4}{=} 1\cdot 1 = (x\cdot \frac{1}{x})(y\cdot \frac{1}{y})$ because $\exists \frac{1}{x},\frac{1}{y}\in F$ such that $x\cdot \frac{1}{x} = 1$ and $y\cdot \frac{1}{y} = 1$. Then $(x\cdot \frac{1}{x})(y\cdot \frac{1}{y}) \os{M2-M3}{=} (xy)(\frac{1}{x}\cdot\frac{1}{y}) \equiv 0(\frac{1}{x}\cdot\frac{1}{y}) \os{(a)}{=} 0 \implies 1 =0$, a contradiction to the assumption that $1\neq 0$ (M4). So $xy\neq 0$.
		\item[(c)] Need to show $(-x)y$ is an additive inverse of $xy$. $(-x)y + xy \os{D}{=} (-x+x)y \os{A5}{=} 0\cdot y \os{(a)}{=} 0 \implies (-x)y = -(xy)$ by Proposition \ref{prop1.14}(c). Similarly, $-(xy) = x(-y)$.
		\item[(d)] $(-x)(-y) \os{(c)}{=} -(x(-y)) \os{(c)}{=} -[-(xy)] \os{\text{Prop \ref{prop1.14}(d)}}{=} xy$
	\end{enumerate}
	Done.
\end{proof}

Field, Ordered set $\}\implies$ Ordered field.

\begin{definition}
	An ordered field $(F,+,\cdot,<)$ is a field which is also an ordered set and satisfies:
	\begin{enumerate}
		\item[(i)] If $y<z$ then $x+y<x+z$ for all $x\in F$.
		\item[(ii)] If $x>0$ and $y>0$ then $xy>0$.
	\end{enumerate}
\end{definition}

\begin{example}
	$(\mb Q,+,\cdot,<)$ is an ordered field with:
	\begin{enumerate}
		\item[+:] $\frac{a}{b} + \frac{c}{d} = \frac{ad+bc}{bd}$ for $\frac{a}{b},\frac{c}{d}\in\mb Q$.
		\item[$\cdot$:] $\frac{a}{b}\cdot\frac{c}{d} = \frac{ac}{bd}$ for $\frac{a}{b},\frac{c}{d}\in\mb Q$.
		\item[$<$:] $\frac{a}{b}<\frac{c}{d}$ if $ad<bc$.
	\end{enumerate}
\end{example}

\begin{proposition}
	Let $(F,+,\cdot,<)$ an ordered field. Then
	\begin{enumerate}
		\item[(a)] If $x>0$ then $-x<0$. (If $x<0$ then $-x>0$).
		\item[(b)] If $x>0$ and $y<z$ then $xy<xz$.
		\item[(c)] If $x<0$ and $y<z$ then $xy>xz$.
		\item[(d)] If $x\neq 0$ then $x^2 = x\cdot x >0$. In particular $1>0$.
		\item[(e)] If $x> 0$ then $\frac{1}{x}>0$.
		\item[(f)] If $0<x<y$ then $\frac{1}{x}>\frac{1}{y}$.
	\end{enumerate}
\end{proposition}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] Let $x>0$. Then $0 \os{A5}{=} -x + x \os{\text{(i)OF}}{>} -x+0 \os{A4}= -x \implies 0>-x$. Similarly, $\dots$
		\item[(b)] Let $x>0$ and $y<z$. Since $y<z\implies z-y >y-y = 0$. Then $x(z-y) \os{(a)}{>} 0$. Then $xz = xz + 0 = xz - xy + xy = x(z-y) + xy \os{(i)}{>} 0 + xy = xy \implies xy <xz$.
		\item[(c)] Try it.
		\item[(d)] Let $x\neq 0$. Then $x>0$ or $x<0$ (ordered set). If $x>0$ then $x^2 = x\cdot x \os{\text{OF}(ii)}{>}0$. Let $x<0$. Then $-x>0 \implies 0<(-x)(-x) \os{\text{Prop \ref{prop1.16}(d)}}{=} x\cdot x = x^2$. In particular, $1\neq 0$, so $1^2 = 1 >0$.
		\item[(e)] Let $x>0$. Suppose that $\frac{1}{x}\geq 0$. Then $-\frac{1}{x}\geq 0$. Then $0 = 0\cdot x \leq (-\frac{1}{x})\cdot x = -1 \implies 0\leq -1$ ($1\leq 0$), a contradiction to $0<1$.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	[Real field] There exists an ordered field, say $(\mb R,+,\cdot,<)$, which has the least upper bound property. Moreover, $\mb R$ contains $\mb Q$ as a subfield.
\end{theorem}
\begin{note}
	$\mb R$ is called real field and elements of $\mb R$ are called real numbers.
\end{note}

\begin{theorem}
	Cases:
	\begin{enumerate}
		\item[(a)] Let $x,y\in\mb R$ with $x>0$. Then there exists $n\in\mb N\backslash\{0\}$ such that $nx>y$. (Archimedean property of $\mb R$).
		\item[(b)] Let $x,y\in\mb R$ with $x<y$. Then $\exists q\in\mb Q$ such that $x<q<y$. (Denseness of $\mb Q$ in $\mb R$).
	\end{enumerate}
	\ul{Special case}: For each $y\in\mb R$, $\exists n\in\mb N\backslash \{0\}$ such that $n>y$. (Taking $x=1>0$).
\end{theorem}
\begin{proof}
	\begin{enumerate}
		\item[(a)] Let $x,y\in\mb R$ with $x>0$. Suppose by contradiction that $n\cdot x \geq y$ for all $n\in\mb N\backslash\{0\}$. Set $A:=\{nx:n\in\mb N\backslash\{0\}\}$. $A$ is nonempty since $x = 1\cdot x\in A$. $A$ is bounded above by $y$ since $nx\leq y$ for all $n\in\mb N$. Since $\mb R$ has the least upper bound property, $\sup A\in\mb R$. $\alpha:= \sup A\in\mb R$. Now, $x>0$, so $-x<0$. $\alpha-x < x+0 = \alpha = \sup A \implies \alpha - x$ is not an upper bound of $A$ $\implies \exists m\in\mb N$ such that $m\cdot x\in A$ and $\alpha-x<mx<\alpha$. $\implies \alpha= \alpha - x + x < mx + x = (m+1)x\in A$, a contradiction that $\alpha = \sup A$. Therefore $\exists n\in\mb N\backslash \{0\}$ such that $nx>y$.
		\item[(b)] Want to construct $q = \frac{m}{n}$, $m,n\in\mb Z$ and $n\neq 0$ such that $x<\frac{m}{n}<y$. Since $x<y$, $y-x>0$. By part (a), $\exists n\in\mb N\backslash \{0\}$ such that $n(y-x)>1$. Next, we find $m$. Since $1>0$ by (a), $\exists k_1,k_2\in\mb N\backslash \{0\}$ such that $k_1>ny$ and $k_2>-nx$ ($\implies -k_2<nx$). Combining $-k_2<nx<ny<k_1$. We're done if $\exists m\in\mb Z$ such that $nx<m<ny$. Define $S:=\{j\in\mb Z:-k_2\leq j\leq k_1 \text{ and } j>nx\}$. Then $S$ is finite, $S\neq \emptyset$ since $k_1\in S$, $S$ is bounded below by $-k_2$. So $\inf S = \min S$ exists, say $m = \min S$. $\implies m>nx$ by construction. Since $m=\min S$, $m-1 \leq nx$. Then $m = (m-1)+1 \leq nx+1 < nx+n(y-x) = ny$. So $nx<m<ny$ and hence $x<\frac{m}{n}<y$, where $q = \frac{m}{n}\in\mb Q$.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	Cases:
	\label{thm1.21}
	\begin{enumerate}
		\item For every positive real number $x$ and every $n\in\mb N\backslash \{0\}$, there exists a unique $y\in\mb R$, $y>0$ so that $y^n = x$ ($y$ is called $n^\text{th}$ root of $x$). $y = ^n\sqrt{x}$ or $y = x^{1/n}$.
		\item For every $n\in\mb N\backslash \{0\}$, there exists a unique $y\in\mb R$, namely \ul{$y=0$}, such that $0^n = 0$ (or $0^{1/n} = 0$).
		\item If $0<a<b$ then $0<a^{1/n} < b^{1/n}$ (monotonicity of $n^\text{th}$ root).
	\end{enumerate}
\end{theorem}
\begin{proof}
	Uniqueness of $n^\text{th}$ root.	
	\ul{Case}: When $x=0$. Suppose $y^n = 0$ given fixed $n$ but $y\neq 0$. Then $y^2 \neq 0$, and by induction $y^k \neq 0$ for all $k\in \mb N\backslash\{0\}$, a contradiction to the fact that $y^n = 0$ for some fixed $n\in\mb N$. So $y=0$ is the only $n^\text{th}$ root for $x=0$.
	
	\ul{Case}: When $x>0$. Suppose $\exists y_1,y_2\in\mb R$ with $y_1,y_2>0$ and $y_1\neq y_2$ such that $y_1^n = x = y_2^n$. WLOG assume $y_1<y_2$. If $0<a<b$ then $0<a^k<b^k$ for any $k\in\mb N\backslash \{0\}$ and $a,b\in\mb R$. By induction: Base case: $a<b$. Suppose $a^{k-1} < b^{k-1}$. Then $a^k = a\cdot a^{k-1} < a\cdot b^{k-1} \underset{a<b}{<} b\cdot b^{k-1} = b^k$. By induction $0<a^k<b^k$ for all $k\in\mb N\backslash \{0\}$. Then $y_1^n<y)2^n$, a contradiction to $y_1^n = y_2^n$.
	
	\ul{Existence of $n^\text{th}$ root}: If $x=0$ then $0^n = 0$ and therefore it follows from the uniqueness that $y=0$. Let $x>0$. If $n=1$, then $y^n = y^1 = x$. Assume $n\geq 2$. Define $S = \{t\in\mb R: t^n < x\}$. $S\neq \emptyset$ because $0\in S$. $S$ is bounded above: find an upper bound of $S$. Let $\alpha := 1+x$. Want to show that $\alpha$ is an upper bound of $S$, i.e. $\alpha \geq t$ for all $t\in S$. Equivalently, we show that $\alpha < t$ then $t\notin S \implies t^n > (1+x)^n = (1+x)(1+x)^{n-1} > (1+x)\cdot 1 \underset{1>0}{>} x \implies t\notin S \implies \alpha$ is an upper bound of $S$ or $S$ is bounded above $\implies \sup S\in \mb R$.
\end{proof}

%\newpage

\begin{recall}
	Cases:
	\begin{enumerate}
		\item[(i)] If $x\in \mb R$, $x>0$, then $\exists! y\in\mb R$, $y>0$ such that $y^n = x$.
		\item[(ii)] If $x=0$, then $y=0$ is the only real number such that $0^n = 0$.
		\item[(iii)] $0<a<b\implies 0<a^{1/n}<b^{1/n}$.
	\end{enumerate}
\end{recall}
\begin{proof}
	In last class, $S := \{t\in \mb R: t^n < x\}$ and $y = \sup S\in\mb R$. We need to show $y^n = x$. We will show $y^n \nless x$ and $y^n \ngtr x$. \ul{So $y^n = x$}.
	Useful inequality: Let $0<a<b$. Then $$b^n - a^n = (b-a)(b^{n-1}+b^{n-2}a + b^{n-3}a^2 + \dots + ba^{n-2} + a^{n-1}) < (b-a)\cdot nb^{n-1}.$$
	
	\ul{Case I}: Suppose $y^n < x$. (Find $y_1>y$, $y_1\in S$ such that $y_1^n > x$). Let $0<h<1$, $h\in\mb R$ such that $h< \frac{x-y^n}{n(y+1)^{n-1}}$. Taking $a = y$ and $b= y+h$ in the inequality, we get $$(y+h)^n - y^n < h\cdot n\cdot (y+h)^{n-1} < h\cdot n(y+1)^{n-1} < x-y^n$$ implies $(y+h)^n < x$ implies $y+h\in S$. But $y+h>y$ and $y=\sup S$, a contradiction.
	
	\ul{Case II}: Assume $y^n > n$. (Find $y_2 < y$ so that $y_2$ is an upper bound of $S$). Define $k = \frac{y^n - x^{>0}}{ny^{n-1}} < \frac{y^n}{n\cdot y^{n-1}} = \frac{y}{n} \underset{n\geq 2}{<} y$. 
	\ul{Claim}: $y - k > 0$ is an upper bound of $S$. 
	Then $y^n - (y-k)^n < k\cdot n y^{n-1} \underset{\text{choice of }k}{=} y^n - x$ implies $-(y-k)^n < -x \implies (y-k)^n > x \implies y-k\notin S \implies y-k$ is an upper bound of $S$. But $y-k<y = \sup S$, a contradiction. Therefore, $y^n = x$.
	
	(iii) Suppose $0<a<b$ but $a^{1/n}\geq b^{1/n}$. Then $b = (b^{1/n})^n \us{\text{power are monotone}}{\leq} (a^{1/n})^n = a$, a contraction to $a<b$. This completes the proof of Theorem \ref{thm1.21}.
\end{proof}
\begin{corollary}
	Let $a,b\in\mb R$ and $a\geq 0,b\geq 0$. Then $(ab)^{1/n} = a^{1/n}\cdot b^{1/n}$.
\end{corollary}
\begin{proof}
	By the uniqueness of the $n^\text{th}$ root, it is enough to show $(a^{1/n}\cdot b^{1/n})^n = ab$. Now, $ab = (a^{1/n})^n (b^{1/n})^n = a^{1/n}\cdots a^{1/n}\cdot b^{1/n}\cdots b^{1/n} = (a^{1/n}b^{1/n})$ respectively $n$ times and using commutativity and associativity.
\end{proof}

\subsection*{Decimal expansion of real numbers}

Let $x\in\mb R$ and $x>0$. By the decimal expansion of $x$, we mean a number of the form $n_0. n_2 n_2 n_3\cdots$ where $n_i$ are defined inductively as follows:
Let $n_0$ be the largest integer such that $n_0\leq x$, i.e., $n_0 = \max\{k\in\mb N: k\geq x\}$. Let $n_1$ be the largest integer such that $n_0 + \frac{n_1}{10} \leq x$, i.e., $n_1 = \max\{k\in\mb N : n_0 + \frac{k}{10} \leq x\}$. Once $n_0,\dots,n_{k-1}$ are chosen, $n_k$ is chosen as follows: $n_k = \max\{j\in\mb N: n_0 + \frac{n_1}{10} + \frac{n_2}{10^2} + \cdots + \frac{n_{k-1}}{10^{k-1}} + \frac{j}{10^k} \leq x\}$.
\begin{note}
	By construction, $n_k\in\{0,1,2\dots,8,9\}$.
\end{note}
\begin{remark}
	Let $x\in\mb R$ and $x>0$. Let $n_0.n_1n_2\dots n_k\dots$ be a decimal expansion of some real number. Define $E:=\{n_0 + \frac{n_1}{10} + \frac{n_2}{10^2} + \dots + \frac{n_k}{10^k} : k\in\mb N\}$. Then $x\sup E$ if and only if $x = n_0.n_1n_2n_3\dots$.
\end{remark}

\subsection*{Extended real number system}

$\mb R^\# := \mb R\cup\{-\infty,\infty\}$. Order on the set $\mb R^\#$: $-\infty < x<\infty$ for all $x\in\mb R$. $\mb R^\#$ is not a field (Not closed under \say{usual} addition, i.e. $-\infty + \infty \os{?}{\in}\mb R^\#$. Use these conventions: $x+\infty = \infty$, $x-\infty = -\infty$, $\frac{1}{\infty} = 0$, $\frac{1}{-\infty} = 0$. For $x\in\mb R^\#$, $x>0$: $x\cdot(+\infty) = \infty$, $x\cdot (-\infty) = -\infty$. For $x\in\mb R^\#$, $x<0$: $x\cdot(+\infty) = -\infty$, $x\cdot(-\infty) = \infty$.

For any $A\subset \mb R^\#$, $\sup A\in\mb R^\#$, $\inf A\in\mb R^\#$. In particular, if $A$ is not bounded above, then $\sup A = \infty$. If $A$ is not bounded below, then $\inf A = -\infty$. Also, $\sup \emptyset = -\infty$ and $\inf \emptyset = \infty$ because every element real number is an upper bound for empty set and every real number is a lower bound for empty set.

\subsection*{Complex Field}

Dictionary order: $(a,b) < (c,d)$ if $\begin{cases} a<c , \\ a=c, & b<d\end{cases}$.

\begin{definition}
	Set of all complex numbers $\mb C :=\{(a,b):a,b\in\mb R\}$, where $(a,b)$ is an ordered pair, i.e. $(a,b)\neq (b,a)$ if $a\neq b$.
	If $z = (a,b)\in\mb C$, $a = \Re(z)$, $b=\Im(z)$.
\end{definition}

Addition \say{$+_\mb C$}: $z_1= (a,b)\in\mb C$ and $z_2 = (c,d)\in\mb C$. Then $z_1+z_2 = (a +_\mb R c, b+_\mb R d)$.

Multiplication \say{$\cdot_\mb C$}: $z_1\cdot z_2 = (ac-bd, bc+ad)$.

Additive identity: $0_\mb C = (0,0)$.

Multiplicative identity: $1_\mb C = (1,0)$.

Then $(\mb C,+_\mb C,\cdot_\mb C)$ is a field.

\begin{recall}
	$(\mb C,+_\mb C,\cdot_\mb C)$ is a field.
\end{recall}
\begin{note}
	$\mb R$ is a subfield of $\mb C$, let $f:\mb R\ra \mb C$ by defining $f(a) = (a,0)$. It allows us to identify $a\in\mb R$ as $a\in\mb C$.
\end{note}
\begin{definition}
	[$i$] We define the imaginary unit $i$ as $(0,1)\in\mb C$.
\end{definition}
\begin{theorem}
	$i^2 = -1$.
\end{theorem}
\begin{proof}
	$i^2 = i\cdot i = (0,1)\cdot_\mb C(0,1) = (0-1,0) = (-1,0)\in\mb C = -1\in\mb R$.
\end{proof}
Given $z=(a,b)\in\mb C$, we can write $z = a+bi$. Indeed, $a+bi = (a,0) +_\mb C (b,0)(0,1) = (a,0)+_\mb C(0,b) = (a,b)$.
\begin{definition}
	[Conjugate] For $z = a+bi = (a,b)\in\mb C$, the conjugate of $z$ is $\conj z\in\mb C$, where $\conj z = a-bi = (a,-b)$.
\end{definition}
\begin{theorem}
	[Conjugate] Let $z,w\in\mb C$, $z = a+ib$, $w = c+id$; where $a,b,c,d\in\mb R$. Then
	\begin{enumerate}
		\item[(a)] $\conj{z+w} = \conj z+\conj w$
		\item[(b)] $\conj{z\cdot w} = \conj z\cdot \conj w$
		\item[(c)] $z+\conj z = 2\Re(z)$ and $z-\conj z = 2i\Im(z)$
		\item[(d)] $z\cdot \conj z\in\mb R$, $z\cdot \conj z \geq 0$ and $z\cdot\conj z = 0 \Lr z = 0$
		\item[(e)] $\conj z = z$
		\item[(f)] $z\in\mb R \implies \conj z = z$.
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] $\conj{z+w} = \conj{(a+ib)+(c+id)} = \conj{(a+c)+i(b+d)} = (a+c)-i(b+d) = a+c-ib-id = (a-ib)+(c-id) = \conj{a+ib} + \conj{c+id} = \conj z + \conj w$.
		\item[(b)] skip!
		\item[(c)] skip!
		\item[(d)] $z\cdot \conj z = (a+ib)(a-ib) = a^2+b^2\in\mb R$. If $a\in\mb R$ and $b\in\mb R$ then $a^2\geq 0$ and $b^2\geq 0 \implies z\cdot \conj z \geq 0$. Now suppose $z = 0$. Then $z\cdot \conj z = 0\cdot \conj z = 0$. Suppose $z\cdot \conj z = 0$. Then $a^2+b^2 = 0$, which implies $a=0$ and $b=0$. So $z = 0+0i = 0$.
		\item[(e)] skip!
		\item[(f)] skip!
	\end{enumerate}
	Done.
\end{proof}
\begin{remark}
	$f:\mb C\ra \mb C$ by $f(z) = \conj z$. By Theorem, $f(z+w) = f(z)+f(w)$ for all $z,w\in\mb C$ and $f(z\cdot w) = f(z)\cdot f(w)$ for all $z,w\in\mb C$ and $f(0) = 0$ and $f(1) = 1$. This implies conjugate preserves field properties of $\mb C$. However, $f$ is not an identity mapping since $f(i) = -i$.
\end{remark}
\begin{definition}
	[Absoulute value, modulus] Given $z\in\mb C$, modulus or absolute value of $z$ is: $|z|:=(z\cdot \conj z)^\frac{1}{2}$ - well defined by $n^\text{th}$ root theorem since $0\leq z\cdot \conj z\in \mb R$.
\end{definition}
\begin{note}
	If $x\in\mb R$, then $|x| = x\cdot x^{1/2} = (x^2)^\frac{1}{2} \us{x\in\mb R}{=} ((-x)^2)^\frac{1}{2} \implies |x| = \begin{cases} x & \text{if } x\geq 0\\ -x & \text{if } x<0\end{cases}$.
\end{note}
\begin{observe}
	$|x|^2 = x^2 = (-x)^2$ for all $x\in\mb R$. But the identity is not true in $\mb C$. Take $z = i$, so $|z|^2 = |i|^2 = i\cdot\conj i = i(-i) = 1$. But $z^2 = i\cdot i = i^2 = -1$.
\end{observe}
\begin{theorem}
	Let $z,w\in\mb C$. Then
	\begin{enumerate}
		\item[(a)] $|z|\geq 0$ and $|z|= 0 \Lr z= 0$.
		\item[(b)] $|\conj z| = |z|$
		\item[(c)] $|z\cdot w| = |z|\cdot|w|$
		\item[(d)] $|\Re (z)| \leq |z|$ and $|\Re(z)|=|z|\Lr z\in\mb R$.
		\item[(e)] $|z+w|\leq |z|+|w|$ and equality holds $\Lr z = \alpha w$ or $w = \alpha z$ for some $\alpha\in\mb R$.
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] Since $z\cdot \conj z \geq 0$ and $|z| = (z\cdot\conj z)^{1/2}$, $|z|\geq 0$ follows by $n^\text{th}$ root theorem. By previous theorem, $z\cdot \conj z = 0\Lr z = 0$. So $|z|=0\Lr z = 0$.
		\item[(b)] $|\conj z| = (\conj z\cdot \conj{\conj z})^\frac{1}{2} = (\conj z\cdot z)^\frac{1}{2} = |z|$.
		\item[(c)] $|z\cdot w|^2 = (z\cdot w)\conj{(z\cdot w)} = (z\cdot w)(\conj z\cdot \conj w) = (z\cdot \conj z)\cdot(w\cdot\conj w) = |z|^2\cdot |w|^2 = (|z|\cdot|w|)^2$. By uniqueness of the square root, $|z\cdot w| = |z|\cdot |w|$. 
		\item[(d)] $|\Re(z)|^2 = \Re(z)\cdot \conj{(\Re(z))} = (\Re(z))^2 \leq (\Re(z))^2 + (\Im(z))^2 = |z|^2$. By monotonicity of square root, $|\Re(z)|\leq |z|$.
		\item[(e)] $|z+w|^2 = (z+w)\conj{(z+w)} = (z+w)(\conj z+\conj w) = z\cdot \conj z + w\cdot \conj z + z\cdot \conj w + w\cdot\conj w = |z|^2 + w\cdot\conj z + \conj{\conj z \cdot w} + |w|^2 = |z|^2 + 2\Re(w\cdot \conj z) + |w|^2 \leq |z|^2 + 2|\Re(w\cdot \conj z)| + |w|^2$ since $x\leq |x| \os{(d)}{\leq} |z|^2 + 2|z\cdot\conj w| + |w|^2 \os{(b)+(c)}{=} |z|^2 + 2|z|\cdot|w| + |w|^2 = (|z|+|w|)^2$ for all $x\in\mb R$. By monotonicity of roots, $|z+w| \leq |z| + |w|$.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	[Schwartz inequality] Let $z_1,z_2,\dots,z_n,w_1,\dots,w_n\in\mb C$. Then $$ \left| \sum_{i=1}^n z_i\cdot \conj{w_i} \right|^2 \leq \left(\sum_{i=1}^n |z_i|^2 \right) \left( \sum_{i=1}^n |w_i|^2\right).$$
\end{theorem}
\begin{proof}
	Let $Z:= \sum_{i=1}^n |z_i|^2 \in\mb R$ and $W: = \sum_{i=1}^n |w_i|^2\in\mb R$ and $P:=\sum_{i=1}^n z_i\cdot \conj{w_i}\in\mb C$. \ul{Claim}: $zw \geq |p|^2$. Note that $W \geq 0$. Then $W = 0 \Lr |w_i| = 0 \Lr w_i = 0$. Then $P = \sum_{i=1}^n z_i\cdot 0 = 0$, we're done.
	
	\ul{Take $W>0$}: Then 
	\begin{align*}
		0\leq \sum_{i=1}^n |Wz_i - Pw_i|^2 &\os{?}{\geq} W(WZ-|P|^2) \\
		&= \sum_{i=1}^n(Wz_i-Pw_i)\conj{(Wz_i-Pw_i)} = \sum_{i=1}^n(Wz_i-Pw_i)(W\conj{z_i}-\conj P\conj{w_i}) \\
		& = \sum_{i=1}^n \left[ W^2 z_i\cdot \conj{z_i} - W\conj P z_i \conj{w_i} - PW w_i \conj{z_i} + P\conj P w_i \cdot \conj{w_i} \right] \\
		&= \sum_{i=1}^n \left[ W^2|z_i|^2 - W\conj P z_i \conj{w_i} - PW w_i \conj{z_i} + |P|^2 \cdot |w_i|^2 \right] \\
		&= W^2 \sum_{i=1}^n |z_i|^2 - W\conj P\sum_{i=1}^n z_i \cdot \conj{w_i} - PW \sum_{i=1}^n w_i \conj{z_i} + |P|^2 \sum_{i=1}^n |w_i|^2 \\
		&= W^2 Z  - W\conj P P - P W \conj P + |P|^2 W = W^2Z - W|P|^2 \\
		&= W(WZ-|P|^2) \geq 0 \os{W>0}{\implies} WZ-|P|^2 \geq 0
	\end{align*}
\end{proof}

\ul{Test 1, Sep 19, 2017}: Problems to ignore \#7, \# 11, \#16, \#20, Expect:
\begin{itemize}
	\item Definitions (always give example)
	\item Statement of named theorems
	\item HW like problems, exercises,
	\item Proofs of theorems/propositions
\end{itemize}

\subsection{Euclidean spaces}
\begin{definition}
	[Vector space over a field] Let $(F,+_F,\cdot_F)$ be a field. A vector space $V$ over a field $F$ is a nonempty set $V$ with two operations -- vector addition + and scalar multiplication $\cdot$ with following:
	\begin{enumerate}
		\item $V$ satisfies (A1)-(A5) of field axioms with `+'.
		\item \begin{itemize}
			\item $a\vv\in V\ \forall a\in F,\ \forall \vv\in V$.
			\item $a(\vu + \vv) = a\vu + a\vv\ \forall a\in F,\ \forall \vu,\vv\in V$.
			\item $(a+_Fb)\vu = a\vu + b\vu\ \forall a,b\in F,\ \forall \vu \in V$.
			\item $(a\cdot_Fb)\vu = a(b\vu)\ \forall a,b\in F,\ \forall \vu\in V$.
			\item $1_F\vu = \vu\ \forall \vu\in V$.
		\end{itemize}
	\end{enumerate}
\end{definition}

Define $\mb R^k = \us{k\text{ times}}{\mb R\times \mb R\times \dots \times \mb R}$ for $k\geq 1$.

For $\vx = (x_1,\dots,x_k), \vy = (y_1,\dots,y_k)\in\mb R$, define addition + and scalar multiplication $\cdot$ as follows:
$$ \vx + \vy = (x_1+y_1,x_2+y_2,\dots,x_k+y_k)$$
$$ a\vx = (ax_1,ax_2,\dots,ax_k) \quad \text{for }a\in\mb R.$$
$$ \vzero = (0,0,\dots,0).$$

\begin{theorem}
	$(\mb R^k,+,\cdot)$ is a vector space over the field of $\mb R$.
\end{theorem}
\begin{proof}
	Skip.
\end{proof}
\begin{definition}
	For $\vx,\vy\in\mb R^k$, inner product or scalar product is defined as:
	$$ \vx\cdot\vy = x_1y_1+x_2y_2+\dots+x_ky_k = \sum_{i=1}^k x_iy_i\ul{\ul{\in\mb R}}$$
\end{definition}
\begin{definition}
	[Norm or modulus or absolute value]
	$$ |\vx| = \left( \sum_{i=1}^k x_i^2 \right)^\frac{1}{2}$$
	Other notation $||\vx|| = \left( \sum_{i=1}^k x_i^2 \right)^{1/2}$.
\end{definition}
\begin{theorem}
	Let $\vx,\vy,\vz\in\mb R^k$ and $a\in\mb R$. Then
	\begin{enumerate}
		\item[(a)] $|\vx|\geq 0$ and $|\vx| = 0 \Lr \vx = \vzero$.
		\item[(b)] $|a\vx| = |a|\cdot|\vx|$
		\item[*(c)] $|\vx\cdot\vy| \leq |\vx|\cdot |\vy|$
		\item[(d)] $|\vx+\vy| \leq |\vx|+|\vy|$
		\item[(e)] $|\vx - \vz| \leq |\vx - \vy| + |\vy-\vz|$
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] $|\vx|^2 = \sum_{i=1}^k x_i^2 \geq 0$, since $x_i^2 \geq 0$ for $x_i\in\mb R$. $\implies |\vx| \geq 0$ using the monotonicity of root. Suppose that $|\vx| = 0$ and suppose by contradiction that $x_i\neq 0$ for some $i\in\{1,\dots,k\}$. $\implies x_i^2 >0$ and $\sum_{j=1}^k x_j^2 > 0$, a contradiction. If $\vx = \vzero$, then $x_i = 0$ for all $i = 1,\dots,k$. So $|\vx| = \left( \sum_{i=1}^k 0^2 \right)^{1/2} = 0$.
		\item[(b)] $|a\vx|^2 = \sum_{i=1}^k (a x_i)^2 = a^2 \sum_{i=1}^k x_i^2 = a^2(|\vx|)^2 \implies |a\vx| = \sqrt{a^2}\sqrt{|\vx|^2} = |a||\vx|$.
		\item[*(c)] WTS: $|\vx|^2|\vy|^2$. Recall, Schwartz inequality $$\left| \sum_{i=1}^n z_i \cdot \conj{w_i} \right|^2 \leq \sum_{i=1}^n |z_i|^2 \sum_{i=1}^n |w_i|^2.$$
			\begin{align*}
				|\vx\cdot \vy|^2 &= \left| \sum_{i=1}^k x_iy_i \right|^2
				\os{\text{Schwartz}}{\leq} \left(\sum_{i=1}^n |x_i|^2 \right) \left( \sum_{i=1}^n |y_i|^2 \right) \os{x_i,y_i\in\mb R}{=} \left(\sum_{i=1}^k x_i^2 \right) \left( \sum_{i=1}^k y_i^2 \right) = |\vx|^2 |\vy|^2.
			\end{align*}
			By monotonicity of root $|\vx\cdot \vy| \leq |\vx||\vy|$.
		\item[(d)] Want to show: $|\vx + \vy|^2 \leq (|\vx| + |\vy|)^2 = |\vx|^2 + 2|\vx|\cdot|\vy| + |\vy|^2$.
			\begin{align*}
				|\vx + \vy|^2 &= \sum_{i=1}^k (x_i+y_i)^2 = \sum_{i=1}^k (x_i^2 + 2x_i y_i + y_i)^2
				= \sum_{i=1}^k x_i^2 + 2 \sum_{i=1}^k x_i y_i + \sum_{i=1}^k y_i^2 \\
				&\leq |\vx|^2 + 2|\vx \cdot \vy| + |\vy|^2 \os{(c)}{\leq} |\vx|^2 + 2|\vx|\cdot |\vy| + |\vy|^2 = (|\vx| + |\vy|)^2
			\end{align*}
			since $\vx\cdot\vy\in\mb R$ and $a\leq |a|$ for all $a\in\mb R$. This implies $|\vx + \vy| \leq |\vx| + |\vy|$ by monotonicity of root.
		\item[(e)] $|\vx - \vz| = |\vx + \vzero - \vz| = |\vx - \vy + \vy - \vz| \os{(d)}{\leq} |\vx-\vy| + |\vy-\vz|$.
	\end{enumerate}
	Done.
\end{proof}
\begin{observe}
	Observe that $|\vx\cdot \vy| = |\vx|\cdot |\vy|$ if $x,y\in\mb R$ \ul{\ul{or}} if $x,y\in\mb C$. \ul{Not true in $\mb R^2$}:
	
	Compare the result of (c) in $\mb C$ versus in $\mb R^2$.
	Take $z = a + ib,w = c+id\in\mb C$. Then
	\begin{align*}
		|z\cdot w|^2 &= |(a+ib)\cdot(c+id)|^2 = |(ac-bd) + i(ad+bc)|^2 = (ac-bd)^2 + (ad+bc)^2 \\
		&= (ac)^2 + (bd)^2 + (ad)^2 + (bc)^2 = (a^2 + b^2)(c^2+d^2) = |z|^2 \cdot |w|^2 \implies |z\cdot w| = |z|\cdot |w|.
	\end{align*}
	Take $\vx = (a,b)$, $\vy = (c,d)$ in $\mb R^2$.
	\begin{align*}
		|\vx\cdot \vy|^2 &= (ac+bd)^2 = (ac)^2 + 2abcd + (bd)^2 \\
		&\cdots\ ?\ \cdots\\
		&\leq |(a^2+b^2) \cdot (c^2+d^2) = |\vx|\cdot |\vy|
	\end{align*}
\end{observe}

If $(a,b),(c,d)\in\mb C$, then $|(a,b)\cdot(c,d)| = |(a,b)|\cdot|(c,d)|$.

If $(a,b),(c,d)\in\mb R^2$, then $|(a,b)\cdot(c,d)| \leq |(a,b)||(c,d)|$.
\begin{proof}
	$0\leq p^2+q^2 - 2pq = (p-q)^2 \implies 2pq \leq p^2 + q^2$.
	\begin{align*}
		|(a,b)\cdot(c,d)|^2 &= |ac+bd|^2 = (ac+bd)^2\\
				    &= (ac)^2 + 2abcd + (bd)^2 \\
		&\leq a^2c^2 + b^2c^2 + a^2d^2 + b^2d^2 \\
		&= (a^2+b^2)(c^2+d^2) = |(a,b)|^2 |(c,d)|^2 \implies |(a,b)\cdot (c,d)| \leq |(a,b)||(c,d)|
	\end{align*}
	monotonicity of roots.
\end{proof}

\section{Topology}

\begin{definition}
	[Function] $A,B$ are sets. $f:A\ra B$ is a function or a mapping if for each $x\in A$, $\exists!f(x)\in B$.
	\begin{itemize}
		\item $A = $ domain of $f$.
		\item $B = $ target set of $f$.
		\item $f(A) = $ Image of $A$ under $f = \{y\in B: \exists x\in A \text{ such that } f(x)=y \}$.
	\end{itemize}
\end{definition}
\begin{definition}
	[one-to-one and onto] $f:A\ra B$ is 1-1 iff $f(a_1) = f(a_2) \implies a_1=a_2$ (or iff $\forall a_1,a_2\in A$, $a_1\neq a_2 \implies f(a_1)\neq f(a_2)$.
	$f:A\ra B$ is onto iff $\forall b\in B$, $\exists a\in A$ such that $f(a)=b$ \ul{\ul{OR}} $f(A)=B$.
\end{definition}
\begin{definition}
	[Preimage or inverse image] Suppose $E_1\subset B$. Then the preimage of $E_1$: $$f\inv(E_1) = \{a\in A: f(a)\in E_1\}.$$
	If $b\in B$, then $f\inv(b) = \{a\in A : f(a)=b\} \subset A$.
\end{definition}
\begin{remark}
	One-to-one correspondence means both one-to-one and onto.
\end{remark}

\begin{definition}
	[Cardinality] We say that a set $A$ has \ul{no more} elements than a set $B$ if $\exists$ a 1-1 map $f:A\ra B$.
	In this case, we write $|A|\leq |B|$, where $|\cdot|$ denotes the cardinality of $A$ (\say{number of elements}).
\end{definition}

\begin{theorem}
	[Cantor-Shroder-Bernstein]
	If $\exists$ two 1-1 functions $f:A\ra B$ and $g:B\ra A$, then $\exists$ a \ul{1-1 and onto} function $h:A\ra B$.
	i.e., $|A|\leq |B|$ and $|B|\leq |A| \implies |A|=|B|$.
\end{theorem}
\begin{proof}
	Skip.
\end{proof}
\begin{definition}
	[Equivalence relation via cardinality]
	$A$ and $B$ have same cardinality if $\exists$ a 1-1 and onto function $f:A\ra B$. We write $|A| = |B|$. This is an equivalence relation.
	\begin{enumerate}
		\item[(i)] $|A| = |A|$ since $id:A\ra A$ is 1-1 and onto.
		\item[(ii)] $|A|=|B|$ then $|B|=|A|$. If $f:A\ra B$ is 1-1 and onto, then $f\inv:B\ra A$ is 1-1 and onto.
		\item[(iii)] If $|A|=|B|$ and $|B|=|C|$, then $|A|=|C|$. There exist $f:A\ra B$ and $g:B\ra C$ both 1-1 and onto. Then $g\circ f: A\ra C$ is 1-1 and onto.
	\end{enumerate}
\end{definition}

\ul{Notation} $J:= \mb N\backslash \{0\}$ and $J_n := \{1,2,\dots,n\}$.
\begin{definition}
	Let $A$ be any set. We say
	\begin{enumerate}
		\item[(a)] $A$ is finite if $A\sim J_n$ or $|A|=|J_n|$ for some $n\in\mb N$.
		\item[(b)] $A$ is infinite if $A$ is not finite.
		\item[(c)] $A$ is countable if $|A| = |J|$ i.e., there exists a 1-1 and onto mapping $f:A\ra J$.
		\item[(d)] $A$ is uncountable if $A$ is neither finite nor countable.
		\item[(e)] $A$ is at most countable if $A$ is finite or countable.
	\end{enumerate}
\end{definition}
\begin{example}
$|\mb Z| = |\mb N|$. Let $f:\mb Z\ra\mb N$ by $f(z) = \begin{cases} 2z-1 & \text{if } z\in\mb Z_+ \\ -2z & \text{if } z\in\mb Z_- \end{cases}$:
	$\begin{array}{ccccccccc}
			\mb {Z} & 0 & 1 & -1 & 2 & -2 & 3 & -3 & \cdots \\
			\, & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow  & \, \\
			\mb{N} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \cdots
	\end{array}$
Let $f:J \os{1-1}{\us{\text{onto}}{\lra}} \mb Z$ by $f(n) = \begin{cases} \frac{n}{2} & \text{if } n \text{ even}\\ -\frac{n-1}{2} & \text{if } n \text{ odd} \end{cases}$.
\end{example}

\begin{note} some notes:
	\begin{itemize}
		\item A finite set has \ul{more} elements than its proper subsets.
		\item Empty set is a finite set.
		\item A set and its proper subsets can have same cardinality.
	\end{itemize}
\end{note}
\begin{example}
	$|\mb N|\os{f?}{=} |2n:n\in\mb N| = |2n-1:n\in\mb N|$
\end{example}
\begin{example}
	$|(-\frac{\pi}{2},\frac{\pi}{2}| = |\mb R|$. Let $f:(-\frac{\pi}{2},\frac{\pi}{2}) \ra \mb R$ by $f(x) = \tan x$ is 1-1 and onto.
\end{example}


\begin{proposition}
	$S$ is infinite $\Llr \exists f:\mb N \ra S$ that is 1-1.
\end{proposition}
\begin{proof}
	\say{$\implies$} Suppose $S$ is infinite. We need to construct $f:\mb N\ra S$ that is 1-1. Since $S$ is not finite, $\exists s_0\in S$.
	Define $f_0:\{0\}\ra S$ by $f_0(0) = s_0$. By construction $f_0$ is 1-1.
	$S$ is infinite, so $\exists s_1\in S (s_1\neq s_0)$.
	Define $f_1:\{0,1\} \ra S$ by $f_1(0) = s_0$ and $f_1(1) = s_1$.
	Then $f_1$ is 1-1. Since $S$ is infinite, $\exists s_2\in S$, $s_2\neq s_0$, $s_2\neq s_1$. Deefine $f:\{0,1,2\} \ra S$ by $f_2(0) = s_0$, $f_2(1) = s_1$, $f_2(2) = s_3$.
	Inductively, $\exists s_n\in S$ such that $s_n\neq s_j$ for $j=0,\dots,n-1$ and $f_n : \{0,1,\dots,n\}\ra S$ by
	\begin{align*}
		f_n(0) &= s_0 \\
		f_n(1) &= s_1 \\
		       &\vdots \\
		f_n(n) &= s_n.
	\end{align*}
	Then $f:\mb N\ra S$ defined by $f(n) = f_n(n) = s_n$ is 1-1 (by construction).
\end{proof}

\begin{example}
	[HW2.1] Let $A$ and $B$ be nonempty bounded subsets of $\mb R$ such that $A\subset B$. Prove: $$\inf B \leq \inf A \leq \sup A \leq \sup B.$$
	\begin{proof}
		Given that $A\neq \emptyset,B\neq\emptyset$, $A$ bounded, $B$ bounded, and $A,B\subset \mb R$, by LUB property of $\mb R$, $\sup A,\inf A, \sup B, \inf B$ exist in $\mb R$.
		Let $a:= \inf A$, $\alpha := \sup A$, $b:=\inf B$, $\beta:=\sup B$.
		By definition of $\sup A,\inf A$, we have:
		\begin{align*}
			\forall x\in A,\, a\leq x \\
			\forall x\in A,\, x\leq \alpha \\
			\text{then for some } x_0\in A \\
			a\leq x_0 \leq \alpha \\
			\text{So } a\leq \alpha \text{ by transitivity}.
		\end{align*}
		To show $\sup A\leq \sup B$, where $A\subset B$, suppose by contradiction that $\beta \leq \alpha$. Since $A\subset B$, for all $x\in A$, $x\in B$ and any $y\in B$, then, $b\leq y \leq B$.
		Then $\beta < \alpha \implies \exists x_1\in A$ such that $\beta<x_1\leq \alpha \implies x_1\notin B$. Contradiction. $A\subset B$.
	\end{proof}
	\begin{proof}
		We show $\inf B\leq \inf A$: By definition of $\inf$, $\gamma \leq \inf B$ for all $\gamma$ lower bounds of $B$.
		Since $x\in A \implies x\in B$, $\gamma$ is a lower bound of $A$. Choose $\gamma = \inf B$, $\inf B$ is a lower bound of $A$. Therefore $\inf B\leq \inf A$.
	\end{proof}
	We know by definition of infimum, $b\leq \inf B$ for all $b\in B$. But $A\subset B$, so $a\leq\inf B$ for all $a\in A$. 
	This implies $\inf B$ is a lower bound of $A$. By definition of $\inf A$, $\inf B\leq \inf A$.
\end{example}
\begin{example}
	[HW2.2] $S:=\{a+b:a\in A,b\in B\}$. $\sup S = \sup A + \sup B$.
	\begin{proof}
		Since $A\neq\emptyset,B\neq\emptyset$ and $A,B\subset \mb R$ are bounded and $\mb R$ has the least upper bound property, $\sup A,\sup B\in\mb R$.
		First, $S\neq\emptyset$ since $A\neq\emptyset$ and $B\neq\emptyset$. Now, $a\leq \sup A$ for all $a\in A$ and $b\leq \sup B$ for all $b\in B$.
		Then $a+b\leq\sup A+b$ and $a+b\leq \sup A + \sup B$ for $b\in B$ fixed and $\forall a\in A$. 
		This implies $\sup A+\sup B$ is an upper bound of $S \implies \sup S\in\mb R$.
		Want to show:
		\begin{enumerate}
			\item[(i)] $\sup A+\sup B$ is an upper bound of $S$. check.
			\item[(ii)] If $\gamma$ is an upper bound of $S$ then $\gamma\geq\sup A + \sup B$.
		\end{enumerate}
		Let $\gamma$ be an upper bound of $S$. Then $\gamma\geq s$ for all $s\in S$. Then $s = a+b$ for some $a\in A$ and $b\in B$.
		So $\gamma \geq a+b \implies b\leq \gamma-a \implies \gamma-a$ is an upper bound for $B$.
		Then $\gamma-a\geq \sup B$ (by definition of $\sup$) implies $\gamma-\sup B \geq a \implies \gamma-\sup B$ is an upper bound for $A$. This implies $\gamma-\sup B \geq \sup A$ (by definition of $\sup$) $\implies \gamma\geq \sup A + \sup B$.
		Therefore $\sup S = \sup A+\sup B$.
	\end{proof}
\end{example}
\begin{example}
	[HW2.3]
	$A\subset \mb R$ nonempty and bounded below. $-A:=\{-a\in \mb R:a\in A\}$.
	Prove that $-\inf A = \sup (-A)$.
	\begin{proof}
		$A\subset\mb R$ nonempty + bounded below $\implies \inf A\in\mb R$.
		By definition of infimum, $a\geq \inf A$ for all $a\in A$.
		$\implies -a\leq -\inf A$ for all $-a\in -A$ - $(*)$.
		This implies $-A$ is bounded above. So $\sup (-A)\in\mb R$ since $-A\neq\emptyset$.
		Want to show: $\sup(-A) = -\inf A$.
		\begin{enumerate}
			\item[(i)] $-\inf A$ is an upper bound of $-A$ by $(*)$.
			\item[(ii)] If $\gamma$ is an upper bound of $-A$, then $\gamma\geq -\inf A$.
		\end{enumerate}
		Let $\gamma$ be an upper bound of $-A$. Then $\gamma\geq -a$ for all $-a\in -A \implies -\gamma\leq a$ for all $a\in A \implies -\gamma$ is a lower bound of $A$. But $\inf A$ is the greatest lower bound of $A$, so $\inf A\geq -\gamma \implies -\inf A\leq \gamma$. Therefore $-\inf A = \sup (-A)$.
	\end{proof}
\end{example}
\begin{example}
	[HW3.4] $\left| |z|-|w|\right| \leq |z-w|$ for all $z,w\in\mb C$.
	\begin{proof}
		$|x|\leq c \Lr -c\leq x \leq c$.
		\ul{Want to show}: (1) $|z|-|w| \leq |z-w|$ and (2) $-|z-w|\leq |z|-|w|$.

		(1): 
		\begin{align*}
			|z| &\os{\mb C\text{ field}}{=} |z-w+w| \\
				&\os{\Delta}{\leq} |z-w| + |w|		
		\end{align*}
		This implies $|z|-|w|\leq |z-w|$.

		(2):
		\begin{align*}
			|w| &= |w-z+z| \\
				&\os{\Delta}{=} |w-z|+|z|
		\end{align*}
		This implies $|w|-|z|\leq |z-w| \implies -(|w|-|z|) \geq -|z-w| \implies |z|-|w| \leq -|z-w|$.
		
		Combining (1)+(2) $\left||z|-|w|\right| \leq |z-w|$.
	\end{proof}
\end{example}

%\ul{From last class}:
\begin{recall}
	\ul{From last class}: $S$ is infinite $\Lr \exists f:\mb N \ra S$ that is 1-1.
\end{recall}
\begin{proof}
	\say{$\implies$} Last class.
	\say{$\Lla$} Suppose there exists $f:\mb N \ra S$ 1-1.
	Assume to the contrary that $S$ is finite i.e., $|S| = |J_n|$ for some $n\in\mb N$ so $\exists j:S\os{1-1}{\us{\text{onto}}{\lra}} J_n$.
	Now, $J_{n+1} \os{i}{\us{1-1}{\lra}} \mb N \os{f}{\us{1-1}{\lra}} S \os{1-1}{\us{\text{onto}}{\lra}} J_n$.
	$A\subset B$ then the includsion map $i:A\ra B$ defined by $i(x) = x$ is a 1-1 map.
	Then $\exists h = j(f(i)): J_{n+1} \ra J_n$ is 1-1, a contradiction since $|J_{n+1}| = n+1$, $|J_n| = n$.
\end{proof}
\begin{proposition}
	A set $S$ is infinite $\Lr \exists S'\subsetneq S$ such that $|S'| = |S|$.
\end{proposition}
\begin{proof}
	Skip.
\end{proof}

\begin{theorem}
	Ever infinite subset of a countable set is countable.
\end{theorem}
\begin{proof}
	Let $A$ be a countable set and $E\subset A$ is \ul{infinite}.
	\ul{Want to show}: $E$ is countable i.e., $\exists j:\mb N\ra E$ that is 1-1 and onto.
	A countable $\implies \exists s:\mb N\ra A$ such that $s$ is 1-1 and onto.
	
	Let $n_1:=\min\{n\in \mb N: s(n) = s_n\in \}$ - set is well defined since $E$ is infinite.
	
	$n_2:=\min\{n\in\mb N: n>n_1 \text{ and } s(n) = s_n\}$. clearly $n_1>n_1$.

	Suppose $n_1<n_2 <\dots < n_{k-1}$, then $n_k:= \min\{n\in\mb N: n>n_{k-1} \text{ and } s(n) = s_n\in E\}$.

	$n_1<n_2<\dots<n_{k-1}<n_k$ and $\{s_{n_1}, s_{n_2}, s_{n_3},\dots,s_{n_{k-1}},s_{n_k} \} \neq E$.
	Now define $f:\mb N \ra E$ by $f(k) = s_{n_k}$. Then $f$ is 1-1. So, $|\mb N| \os{f\text{ 1-1}}{\leq} |E| \os{E\subset A}{\leq} |A| \os{\text{countable}}{=} |\mb N|$. Therefore, $|\mb N| = |E|$, so $E$ is countable.
\end{proof}

Unions and intersections. Let $A,B$ be any subsets of $\Omega$.
$$A\cup B = \{ x\in \Omega : x\in A \text{ \ul{or} } x\in B\}.$$
$$A\cap B = \{x\in \Omega : x\in A \text{ \ul{and} } x\in B\}.$$
Let $A$ be any set - index set.
Let $\{E_\alpha\}_{\alpha\in A}$ be any collection of subsets of $\Omega$.
Then $$\bigcup_{\alpha\in A} E_\alpha = \{ x\in \Omega: x\in E_{\alpha_0} \text{ \ul{for some} } \alpha_0\in A\}.$$
$$ \bigcap_{\alpha\in A} E_\alpha = \{x\in \Omega: x\in E_\alpha \text{ \ul{for all} } \alpha\in A\}.$$
\begin{remark}
	$A,B$ subsets of $\Omega$.
	\begin{itemize}
		\item $A\cup B = B\cup A$, $A\cap B = B\cap A$.
		\item $(A\cup B)\cup C = A\cup(B\cup C)$.
		\item $(*)$ $A\cap (B\cup C) = (A\cap B)\cup (A\cap C)$.
		\item $A,B\subset A\cup B$, $A\cap B\subset A,B$.
		\item $A\subset B \implies A\cup B = B$ and $A\cap B = A$.
		\item $\emptyset$ acts as neutral element, that is $A\cup \emptyset = A$ and $A\cap \emptyset = \emptyset$.
		\item $*$ $\emptyset$ is a subset of every set.
	\end{itemize}
\end{remark}
\begin{example}
	$\bigcup_{x\in\mb R} (-\infty,x] = \mb R$.
	\begin{proof}
		\say{$\subset$} Let $a\in\bigcup_{x\in\mb R}(-\infty,x]$.
		Then $a\in(-\infty,x_0]\subset\mb R$ for some $x_0\in\mb R$.
		This implies $a\in\mb R\implies \bigcup_{x\in\mb R}(-\infty,x]\subset \mb R$.

		\say{$\supset$} Let $a\in\mb R$. Then $a\in(-\infty,a]$. So $a\in\bigcup_{x\in\mb R}(-\infty,a]$. Therefore $\mb R\subset_{x\in\mb R} (-\infty,x]$. Hence $\bigcup_{x\in\mb R} (-\infty,x] =~\mb R$.
	\end{proof}
\end{example}
\begin{example}
	$\bigcap_{x\in(0,1)}(0,x) = \emptyset$. $\nexists a\in\mb R$ such that $\bigcap_{x\in(0,1)}(0,x) = a$.
	If $a\leq 0$, then $a\notin(0,x)$ for any $x\in(0,1)$, so $a\notin\bigcap_{x\in(0,1)}(0,x)$.
	Let $a>0$. Then $a\notin (0,x)$ for any $x\in(0,1)$. So $a\notin \bigcap_{x\in(0,1)}(0,x)$.
	Let $0<a<1$. Then $a\notin(0,\frac{a}{2})$. So $a\notin \bigcap_{x\in(0,1)}(0,x)$. Therefore $\bigcap_{x\in(0,1)}(0,x) = \emptyset$.
\end{example}
\begin{example}
	[*] $A:=\{x\in\mb R: 0<x\leq 1\} = (0,1]$. For $x\in A$, define $E_x\{y\in\mb R: 0<y<x\}$.
	Then $E_x\subset E_z \Lr 0<x\leq z \leq 1$.
\end{example}

\begin{theorem}
	Let $\{E_n\}_{n\in\mb N}$ be a sequence of countable sets.
	Then $S:=\bigcup_{n\in\mb N} E_n$ is countable. (Countable union of countable sets is countable).
\end{theorem}
\begin{example}
	$\mb N^2 = \mb N\times \mb N = \bigcup_{n\in\mb N} \mb N\times \{n\}$.
\end{example}
\begin{proof}
	We need to show: $\exists f:\bigcup_{n\in\mb N} E_n \ra \mb N$ that is 1-1.
	For each $n\in\mb N$, $E_n$ is countable, so $\exists g_n: \mb N\ra E_n$ that is 1-1 and onto.
	This allows us to write: $$g_1: x_{1,1}, x_{1,2}, x_{1,3},\dots,x_{1,k},\dots = E_1.$$
	$$g_2: x_{2,1}, x_{2,2}, x_{2,3},\dots,x_{2,k},\dots = E_2.$$
	$$g_3: x_{3,1}, x_{3,2}, x_{3,3},\dots,x_{3,k},\dots = E_3.$$
	$$ \vdots$$
	$$g_m: x_{m,1}, x_{m,2}, x_{m,3},\dots,x_{m,k},\dots = E_m.$$
	This array contains all elements of $S$.
	We can rewrite $S = \bigcup_{n\in\mb N} E_n$ as follows: $S = \bigcup_{n\in\mb N} \bigcup_{m\in\mb N} g_n(m)$.
	Define $f:\bigcup_{n\in\mb N} E_n \ra \mb N$ by
	$ f(g_n(m)) = 10^{m+n} + m \implies f$ is 1-1 $\implies \bigcup E_n$ is countable.
\end{proof}

\begin{theorem}
	Let $A$ be a countable set. Let $B_n:= \{(x_1,\dots,x_n):x_i\in A\}$.
	Then $B_n$ is countable.
\end{theorem}
\begin{proof}
	By induction. Since $A$ is countable, $B_1:= \{ x: x\in A\} = A$.
	Suppose that $B_{k-1}$ is countable for $k \geq 2$. Then $B_k = B_{k-1}\times A = \{(x_1,\dots,x_{k-1},a): a\in A \text{ and } (x_1,\dots,x_{k-1})\in B_{k-1}\} = \bigcup_{a\in A} B_{k-1}\times \{a\}$ implies $B_k$ is countable as countable union of countable sets.
	Therefore, $B_n$ is countable for any $n\in\mb N$.
\end{proof}
\begin{corollary}
	$\mb Q$ is countable.
\end{corollary}
\begin{proof}
	We will show: $\mb Q$ is a countable union of countable sets.
	For fixed $n\in\mb N$, write $S_n:=\{\frac{m}{n}:m\in\mb Z\}$. Then $S_n$ is countable since $\mb Z$ is countable.
	\ul{Claim}: $\mb Q = \bigcup_{n\in\mb N} S_n$.
	
	\ul{Proof of claim}: \say{$\subset$} Let $x\in\mb Q$. Then $x = \frac{m}{n}$ with $m,n\in\mb Z$ and $n\neq 0$.
	If $n\in\mb N$, then $x = \frac{m}{n}\in S_n$, we're done.
	If $-n\in\mb N$, then $x = \frac{m}{n} = \frac{-m}{-n} \implies x\in S_{-n\in\mb N} \implies x\in\bigcup_{n\in\mb N} S_n \implies \mb Q\subset\bigcup_{n\in\mb N} S_n$.

	\say{$\supset$} Let $x\in\bigcup_{n\in\mb N} S_n$. Then $\exists n_0\in\mb N$ such that $x\in S_{n_0}$ i.e., $x=\frac{m}{n_0}$ for some $m\in\mb Z$. $\implies x\in\mb Q \implies \bigcup_{n\in\mb N}S_n\subset \mb Q$.	
	So $\mb Q = \bigcup_{n\in\mb N} S_n$ - a \ul{countable union} of countable sets.
	So $\mb Q$ is countable.
\end{proof}

\begin{theorem}
	Let $A:=\{0,1\}^\mb N = \{f:\mb N\ra\{0,1\}\}$ set of all sequences of 0's and 1's.
	Then $A$ is \ul{uncountable}.
\end{theorem}
\begin{proof}
	We will use: If every countable subset of $A$ is a proper subset of $A$, then $A$ is uncountable.
	(Otherwise, $A\subsetneq A$ - a contradiciton).
	Let $E\subset A$ be a countable set. This means we can enumerate elements of $E$:
	\begin{align*}
		s_1&: 0,1,0,1,0,0,0,0,1,0,\dots \\
		s_2&: 0,0,0,0,0,0,0,0,1,\dots \\
		s_3&: 0,1,1,1,1,0,0,1,0,0,\dots \\
			&\qquad\vdots \\
		s_k&: 0,0,1,0,1,0,0,0,1,\dots
	\end{align*}
	- these are all elements of $E$.
	We will construct an element $s^*\in A$ but $s^*\notin E$.
	Define $$s^*(k) = 1-s_k(k) = \begin{cases} 1 & \text{if } s_k(k) = 0 \\ 0 & \text{if } s_k(k) = 1 \end{cases}.$$
	Then $s^*$ is a sequence of 0's and 1's and hence $s^*\in A$.
	By construction $s^*\notin s_k$ for all $k\in\mb N$ for at least in one place. 
	This implies $s^*\in A$ but $s^*\notin E \implies E$ is a proper subset of $A$ since $E$ is arbitrary, $A$ must be uncountable. This is Cantor's diagonalization method.
\end{proof}
\begin{corollary}
	$\mb R$ is uncountable.
\end{corollary}
\begin{proof}
	Later in chapter using topology.
\end{proof}

\begin{theorem}
	$(0,1)\subset \mb R$ is uncountable.
\end{theorem}
\begin{proof}
	Let $E\subset (0,1)$ be countable. We will show $E\subsetneq (0,1)$.
	Since $E$ is countable, elements of \ul{$E$ can be} \ul{enumerated}. Also, elements of $E$ can be written as decimal expansion: Then
	$$s_1: 0.a_{11}a_{12}a_{13}a_{14}\dots$$
	$$s_2: 0.a_{21}a_{22}a_{23}a_{24}\dots$$
	$$s_3: 0.a_{31}a_{32}a_{33}a_{34}\dots$$
	$$ \vdots$$
	$$s_k: 0.a_{k1}a_{k2}a_{k3}a_{k4}\dots$$
	$$ \vdots $$
	Construct $s^*\in(0,1)$ as follows: $s^* := 0.s_1^*s_2^*s_3^*\dots$ with $s_1^*\neq a_{11}, s_2^*\neq a_{22}, s_3^*\neq a_{33}, \dots, s_k^* \neq a_{kk}$ and $s_i^*\neq 9$ for all $i\in\mb N$.
	Then $s^*\in(0,1)$ and $s^*\notin E$. So $E\subsetneq (0,1)$. Therefore $(0,1)$ is uncountable.
\end{proof}

\subsection{Metric spaces}

\begin{definition}
	[Metric] Let $X$ be any set. Then $\rho:X\times X\ra \mb R$ is a metric if it satisfies the following:
	\begin{enumerate}
		\item[(i)] $\rho(a,b)>0$ for all $a,b\in X$ and $\rho(a,b) = 0 \Llr a= b$.
		\item[(ii)] $\rho(a,b) = \rho(b,a)$ - symmetric.
		\item[(iii)] $\rho(a,b)\leq \rho(a,c) + \rho(c,b)$ - triangle inequality.
	\end{enumerate}
\end{definition}
\begin{example}
	$X = \mb R$ and $\rho(a,b) = |a-b|_\mb R$.
\end{example}
\begin{example}
	$X = \mb C$ and $\rho(z,w) = |z-w|_\mb c = [(z-w)\conj{(z-w)}]^{\frac{1}{2}}$.
\end{example}
\begin{example}
	$X = \mb R^k$ with $\vx = (x_1,\dots,x_k),\vy = (y_1,\dots,y_k)$ and $\rho(\vx,\vy) = |\vx - \vy|_{\mb R^k} = \left( \sum_{i=1}^k (x_i-y_i)^2 \right)^{\frac{1}{2}}$.
\end{example}
\begin{example}
	$X$ be any set and define $\rho(x,y) = \begin{cases} 1 & \text{if } x\neq y \\ 0 & \text{if } x = y \end{cases}$ - discrete metric. Verify $\rho$ is a metric.
\end{example}
\begin{definition}
	[Convex set] Let $E\subset\mb R^k$. Then $E$ convex if $\lambda\vx + (1-\lambda)\vy \in E,\ \forall\vx,\vy\in E$ and $\forall \lambda\in[0,1]$.
\end{definition}
\begin{example}
	Open ball in $\mb R^k$: $B_r(\vx) := \{ \vy\in\mb R^k : |\vx-\vy|<r \}\subset \mb R^k$ - ball centered at $\vx$ with radius $r>0$.
	
	\ul{Claim}: $B_r(\vx)$ is convex so that $\lambda\vy + (1-\lambda)\vz\in B_r(\vx)$ for all $\vy,\vz\in B_r(\vx)$ and $0\leq \lambda\leq 1$.
	\begin{proof}
		Let $\vy,\vz\in B_r(\vx)$ and $\lambda\in[0,1]$. Then
		\begin{align*}
			|\vx -(\lambda\vy + (1-\lambda)\vz)|_{\mb R^k} &\os{?}{<} r \\
			&= | \vx - \lambda\vy - \vz + \lambda\vz +\lambda\vx - \lambda\vx| \\
		 	&= |(\vx - \vz) + \lambda(\vx -\lambda\vy) +\lambda(\vx +\vz)| \\
			&= |(1-\lambda)(\vx-\vz) + \lambda(\vx-\vy)| \\
			&\os{\Delta}{\leq} (1-\lambda)|\vx-\vz|_{\mb R^k} + \lambda|\vx-\vy|_{\mb R^k} \\
			&\leq (1-\lambda)r + \lambda r = r \implies \lambda\vy + (1-\lambda)\vz\in B_r(\vx)
		\end{align*}
		Thus $B_r(\vx)$ is convex.
	\end{proof}
\end{example}

\begin{definition}
	[Neighborhood] $N_r(x) = \{y\in X: \rho(x,y)<r\}$.
\end{definition}
\begin{definition}
	[Limit point] $p$ is a limit point of $E$ if $\forall r>0$, there exists $q\in E\subset X$ such that $q\in~N_r(p)\backslash\{p\}$.
\end{definition}
\begin{example}
	$X = (\mb R,\us{\rho}{|\cdot|})$ and $E:= \{\frac{1}{n}:n\in\mb N\}\subset\mb R$.
	If $e\in E$, then $e = \frac{1}{n}$ for some $n\in\mb N$.
	Take $r:= \min\{\frac{1}{n}-\frac{1}{n+1},\frac{1}{n-1}-\frac{1}{n}\}$.
	Then $N_r(e)$ does not contain any point of $E$. $\implies E$ does not contain any limit point of $E$.
	But $x=0$ is a limit point of $E$. Indeed, let $r\in(0,1)$. Then $N_r(0)i$ contains points of $E$.
\end{example}
\begin{remark}
	Limit points of a set do not necessarily belong to $E$.
\end{remark}
\ul{Notation}: $E':=$ set of all limit points of $E$.
\begin{definition}
	[Closed set] $E$ is closed if $E'\subset E$.
\end{definition}
\begin{definition}
	[Interior point] A point $p\in E$ is interior if $\exists r$ such that $N_r(p)\subset E$.
\end{definition}
\ul{Notation}: $E^\circ := $ set of all interior points of $E$.
\begin{definition}
	[Open set] If every point is an interior point. i.e., $E^\circ = E$.
\end{definition}

$(X,\rho)$ is a metric space.

\begin{theorem}
	Every neighborhood in $X$ is an open set.
\end{theorem}
\begin{proof}
	Let $p\in X$ and let $N_r(p)$ be a neighborhood of $p$ in $X$.
	\ul{Want to show}: Every point of $N_r(p)$ is an interior point of $N_r(p)$.
	Let $q\in N_r(p)\backslash\{p\}$. Then $\rho(p,q)<r$. So let $h = r-\rho(p,q)$.
	Then $N_h(q)\subset N_r(p)$. Indeed, if $s\in N_h(q)$, then $\rho(q,s)<h$, so 
	$$\rho(s,p) \os{\Delta}{\leq} \rho(s,q)+\rho(q,p) < h+ \rho(q,p) = r-\rho(p,q)+\rho(p,q) =~r$$
	implies $\rho(s,p) < r \implies s\in N_r(p) \implies N_h(q) \subset N_r(p)$.
	So $N_r(p)$ is open.
\end{proof}

\begin{theorem}
	If $p$ is a limit point of $E\subset (X,\rho)$, then every neighborhood of $p$ contains infinitely many points of $E$.
\end{theorem}
\begin{proof}
	By construction via induction. Since $p\in E'$, for any $r>0$ (fixed), $\exists e_1\in E$ and $e_1\in N_r(p)\backslash\{p\}$.
	Take $r_1 := \rho(p,e_1)$. Then $\exists e_2\in E$ and $\rho_2\in N_{r_1}(p)\backslash\{p\}$ and $e_1\neq e_2$.
	If $e_1,\dots,e_n$ are chosen, take $r_n:=\rho(p,e_n)$. Then $\exists e_{n+1}\in E$ and $e_{n+1}\in N_{r_n}(p)\backslash\{p\}$ and $e_{n+1}\neq e_i$ for all $i=1,\dots, n$.
	By induction, $\exists \{e_n\}_{n=1}^\infty\in E$ such that $\{e_n\}_{n=1}^\infty \subset N_r(p)\backslash\{p\}$.
\end{proof}
\begin{proof}
	\ul{Book}: By contradiction.
	Suppose $\exists r>0$ such that $N_r(p)$ contains finitely many points, say $q_1,\dots,q_n\in E$ such that $q_i\neq p$.
	Take $r_0 = \us{1\leq i \leq n}{\min} \rho(p,q_i) > 0$, since $p\neq q_i$.
	Then $N_{r_0}(p) = \{p\}$ - a contradiction that $p$ is a limit point of $E$. This proves the theorem.
\end{proof}

\newpage

\begin{theorem}
	A set $E$ is open $\Llr E^c$ is closed.
\end{theorem}
\begin{proof}
	\say{$\Lla$} Suppose $E^c$ is closed. Let $x\in E$.
	\ul{Want to show}: $\exists r>0$ such that $N_r(x)\subset E$.
	Clearly $x\notin E^c$. So $x$ is not a limit point of $E^c$.
	Hence $\exists r>0$ such that $N_r(x)\cap E^c = \emptyset$.
	$\implies N_r(x) \subset E \implies E$ is open.

	\say{$\implies$} Suppose $E$ is open. We want to show $F=E^c$ is closed i.e., $F'\subset F$.
	Let $x\in F'$. Then $\forall r>0$, there exists $y\in F$ such that $y\in N_r(x)\backslash\{x\}$.
	$\implies y\in N_r(x)$ but $y\notin E$ because $y\in E^c$.
	$\implies N_r(x)\not\subset E \implies x$ is not an interior point of $E$ (open).
	$\implies x\notin E \implies x\in E^c$
\end{proof}

\ul{HW 5 due on 10/17/2017} Test 2, Saturday 10/28/2017. 11am - 1pm. Not meeting 10/10 and 10/12.

\begin{theorem}
	[de Morgan's law]
	Let $\{E_\alpha\}_{\alpha\in A}$ be a collection of subsets of $X$ and $A$ be any set.
	Then $\left( \bigcup_{\alpha\in A} E_\alpha\right)^c = \bigcap_{\alpha\in A} E_\alpha^c$. \ul{Eg}: $(A\cup B)^c = A^c\cap B^c$.
\end{theorem}
\begin{proof}
	\say{$\subset$} Let $x\in\left(\bigcup_{\alpha\in A} E_\alpha\right)^c$. Then $x\notin \bigcup_{\alpha\in A} E_\alpha \implies x \notin E_\alpha$  \ul{for all $\alpha\in A$}.
	This implies $x\in E_\alpha^c$ for all $\alpha\in A$. $\implies x\in \bigcap_{\alpha\in A} E_\alpha^c \implies \left(\bigcup_{\alpha\in A} E_\alpha\right)^c \subset \bigcap_{\alpha\in A} E_\alpha^c$.
	
	\say{$\supset$} Let $x\in \bigcap_{\alpha\in A} E_\alpha^c$. This implies $x\in E_\alpha^c$ for all $\alpha \in A \implies x\notin E_\alpha$ for all $\alpha \in A \implies x\notin \bigcup_{\alpha\in A} E_\alpha \implies x\in\left( \bigcup E_\alpha \right)^c \implies \bigcap_{\alpha\in A} E_\alpha^c \subset(\bigcup E_\alpha )^c$.
	
	Therefore  $\left(\bigcup_{\alpha\in A}E_\alpha\right)^c = \bigcap_{\alpha\in A} E_\alpha^c$.
\end{proof}

\begin{theorem}
	Let $(X,\rho)$ be a metric space and $A$ be a set of indices. Then
	\begin{enumerate}
		\item[(i)] $\{G_\alpha\}_{\alpha\in A}$ open $\implies \bigcup_{\alpha\in A} G_\alpha$ is open.
		\item[(ii)] $\{F_\alpha\}_{\alpha\in A}$ closed $\implies \bigcap_{\alpha\in A} F_\alpha$ is closed.
		\item[(iii)] If $G_1,\dots,G_n$ is open then $\bigcap_{i=1}^n G_i$ is open.
		\item[(iv)] If $F_1\dots,F_n$ is closed then $\bigcup_{i=1}^n F_i$ is closed.
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(i)] Let $x\in \bigcup_{\alpha\in A} G_\alpha$ be arbitrary.
			\ul{WTS}: $x$ is an interior point of $\bigcup_{\alpha\in A} G_\alpha$ i.e., $\exists r>0$ such that $N_r(x)\subset \bigcup_{\alpha\in A} G_\alpha$.
			$x\in\bigcup_{\alpha\in A}G_\alpha \implies \exists \alpha_0\in A$ such that $x\in G_{\alpha_0}$.
			$G_{\alpha_0}$ open $\implies \exists r_{\alpha_0}>0$ such that $N_{r_{\alpha_0}}(x)\subset G_{\alpha_0} \subset \bigcup_{\alpha\in A} G_\alpha$.
			Thus $x$ an interior point of $\bigcup_{\alpha\in A} G_\alpha$ and hence $\bigcup_{\alpha\in A} G_\alpha$ open.
		\item[(ii)] Note that $\bigcap_{\alpha\in A} F_\alpha = \left(\bigcup F_\alpha^c)\right)^c$ is closed, since $F_\alpha^c$ open and $\bigcup F_\alpha^c$ is open by (i).
		\item[(iii)] Let $G_1,\dots,G_n$ be open.
			\ul{Want to show}: $\bigcap_{i=1}^n G_i$ is open i.e., every point of $\bigcap_{i=1}^n G_i$ is an interior point.
			Let $x\in\bigcap_{i=1}^n G_i$ be arbitrary. $G_i$ open $\implies\exists r_i>0$ such that $N_{r_i}(x)\subset G_i$ for all $i=1,\dots,n$.
			Take $r=\us{1\leq i\leq n}{\min} r_i>0$ since $r_i>0$ and $i=1,\dots,n$.
			Then $N_r(x) = \bigcap_{i=1}^n N_{r_i}(x)\subset G_i$ for every $i=1,\dots n \implies N_r(x)\subset\bigcap_{i=1}^n G_i \implies x$ is an interior point of $\bigcap_{i=1}^n G_i \implies \bigcap_{i=1}^n G_i$ open.
	\end{enumerate}
	Done.
\end{proof}
\begin{remark} Counter examples:
	\begin{enumerate}
		\item Intersection of infinitely many open sets need not be open.
			\begin{example}
				Take $X = \mb R$ with $\rho(x,y) = |x-y|$.
				Take $G_n := (-\frac{1}{n},\frac{1}{n})$ - open for all $n\in\mb N$.
				But $\bigcap_{i=1}^\infty G_i \os{?}{=} \{0\}$ - closed (a set with finitely many elements is closed).
				Clearly $\{0\}\subset \bigcap_{i=1}^\infty G_i \checkmark$.
				\say{$\subset$} Let $x\in\bigcap{i=1}^\infty G_i$.
				$x\in\mb R$ (an ordered field), so we need to show $x\neq 0$.
				Let $x>0$. Then by Archimedean principle, $\exists n_0\in\mb N$ such that $n_0 x>1$ i.e., $x>\frac{1}{n_0}$, a contradiction to $x<\frac{1}{n}$ for every $n\in\mb N$. So $x\ngtr 0$.
				Let $x<0$. Then $-x>0$. By Archimedean principle, $\exists n_1\in\mb N$ such that $n_1(-x) >1$ i.e., $x<-\frac{1}{n_1}$, a contradiction to $x>-\frac{1}{n}$ for every $n\in\mb N$.
				So $x = 0 \implies \bigcap_{i=1}^\infty G_i = \{0\}$.
			\end{example}
		\item Union of infinitely many closed sets may not be closed.
			\begin{example}
				$\bigcup_{n\in\mb N}[-1+\frac{1}{n},1-\frac{1}{n}] = (-1,1)\subset\mb R$ open, and $[-1+\frac{1}{n},1-\frac{1}{n}]$ is closed $\forall n\in\mb N$.
			\end{example}
	\end{enumerate}
\end{remark}

\begin{recall}
	$E' = $ set of limit points of $E$. (Eg: $E = \{\frac{1}{n}\}_{n\in\mb N}$, $E' = \{0\}$.). $\conj{E} = E\cup E'$ = closure of $E$.
\end{recall}
\begin{theorem}
	Let $E\subset(X,\rho)$. Then
	\begin{enumerate}
		\item[(a)] $\conj E$ is closed.
		\item[(b)] $E = \conj E \Llr E$ is closed.
		\item[(c)] $\conj E\subset F$ for every closed set $F\subset X$ containing $E$ or $E\subset F$ ($\conj E$ is the smallest \ul{closed} set containing $E$).
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] We will show $(\conj E)^c$ is open. Let $x\in (\conj E)^c$ be arbitrary. 
			This implies $x\notin \conj E = E\cup E' \implies x\notin E$ and $x\notin E'$, $x$ not a limit point of $E$.
			This implies $\exists r>0$ such that $N_r(x)\cap (E\cup E') = \{x\}$ but $x\notin E$ and $x\notin E'$, so $N_r(x)\cap \conj E = \emptyset$.
			This implies $N_r(x)\subset (\conj E)^c \implies x$ is an interior point of $E$. This implies $(\conj E)^c$ is open $\implies \conj E$ is closed.
		\item[(b)] \say{$\implies$} by (a).
			\say{$\Lla$} Suppose $E$ is closed.
			\ul{Want to show}: $E\subset \conj E\checkmark$ and $\conj E\subset E$.
			Since $E$ is closed, $E'\subset E$. Then $\conj E = E\cup E'\subset E\cup E = E$. Therefore $\conj E = E$.
		\item[(c)] Let $F\subset X$ be closed and $E\subset F$.
			\ul{WTS}: $\conj E \subset F$.
			$F\subset X$ closed $\implies F'\subset F = \conj F$. Since $E\subset F$, we just need to show that $E'\subset F$.
			Let $x\in E'$. Then $\exists r>0$ such that $N_r(x)\cap (E\backslash\{x\})\neq \emptyset$.
			That implies that $N_r(x)\cap(F\backslash\{x\}(\neq \emptyset$ (since $E\subset F$).
			That means that $x$ is a limit point of $F$ i.e., $x\in F' \implies x\in F'\cup F = F \implies \conj E \subset F$.
	\end{enumerate}
	Done.
\end{proof}

\ul{Exam question groups}
\begin{enumerate}
	\item \ul{Allan}, Maribeth, Uyeong, Stephen
	\item \ul{Keri}, Daniel, Michael, Nathan
	\item \ul{Cole}, Philip, Anurag, Ellie
\end{enumerate}
\ul{From each group}:
\begin{itemize}
	\item 6 Easy - Definitions, statements, examples, and 2-3 liners
	\item 5 Medium - Important short results (proof), problems from exercises
	\item 4 Difficult - Involved problems (from exercises or other wise)
\end{itemize}
Due on \ul{\ul{17$^\text{th}$}}.
Free to use up to Thm 2.42, up to \#16 (Exercises).

\ul{Relative open sets}
Let $X$ be a metric space, $E\subset X$ open if for each $e\in E$, $\exists r_e>0$ such that $$N_r(e) = \{x\in X:\rho(x,e)<r_e\} \subset E.$$
If $E\subset Y\subset X$, then we say \ul{$E$ is open in} $Y$ if for each $e\in E$, $\exists r_e>0$ such that $$N_{r_e}^Y(e) := \{y\in \ul{\ul{Y}}:\rho(y,e)< r_e\} \subset E.$$

\begin{theorem}
	Let $Y\subset X$, where $X$ is a metric space. Then $E\subset Y$ is open relative to $Y \Llr E = Y\cap G$ for some open set $G$ in $X$.
\end{theorem}
\begin{example}
	$X = \mb R$ and $Y = [0,1]$. Then $(\frac{1}{2},1] = [0,1]\cap(\frac{1}{2},2)$ is open in $[0,1]$ but not open in $\mb R$.
\end{example}
\begin{proof}
	\say{$\implies$} Suppose $E\subset Y$ is open relative to $Y$.
	\ul{\ul{NTS}}: $\exists$ an open set $G$ of $X$ such that $E = Y\cap G$.
	Since $E$ is open relative to $Y$, for each $e\in E$, $\exists r_e>0$ such that $N_{r_e}^Y(e) \subset E$.
	Set $G: = \bigcup_{e\in E} V_e$, where $V_e = N_r(e)$ open neighborhood of $e$ in $X$.
	This implies $G$ is open in $X$.
	\ul{We need to show}: $E = Y\cap G$.
	\say{$\subset$}: $E\subset Y$ (given). We only need to show $E\subset G$.
	Let $e\in E$. Then $e\in V_e$ and so $e\in \bigcup_{e\in E} V_e = G$.
	So $E\subset Y\cap G$.
	\say{$\supset$} $Y\cap G = Y\cap\left(\bigcup_{e\in E} V_e\right) = \bigcup_{e\in E} (V_e \cap Y) \subset E$ by definition of relative open sets, since $V_e$ is neighborhood of $X$ and $V_d\cap Y$ is neighborhood of $e$ in $Y$.
	$\implies Y\cap G = E$.

	\say{$\Lla$} Suppose $\exists G$ open in $X$ such that $E = Y\cap G$. We will show $E$ is open in $Y$.
	Let $e\in E$, NTS: $e$ is an interior point of $E$ of $E$).
	Then $e\in Y\cap G$. But $G$ is open in $X$, so $\exists r>0$ such that $N_r(e) \subset G$.
	This implies $N_r(e)\cap Y\subset G\cap Y = E$.
	Therefore $e$ is an interior point of $E$ and $E$ is open in $Y$.
\end{proof}

\subsection{Compact sets}
$(X,\rho)$ metric space is $X^{m.s.}$.
\begin{definition}
	[Open cover] Let $\{G_\alpha\}$ be collection of open sets of $X$ and $E\subset X$.
	We say that $\{G_\alpha\}$ is an open covering of $E$ if $E\subset\bigcup_\alpha G_\alpha$.
\end{definition}
\begin{remark}
	Fitting people under umbrellas in the rain (umbrella neighborhood).
\end{remark}
\begin{definition}
	[Compact set] $E\subset X$ is a compact set if \ul{every} open cover of $E$ has a \ul{finite} subcover of $E$ i.e., if $\{G_\alpha\}$ is an open cover of $X$, $\exists \alpha_1,\dots,\alpha_n$ such that $E\subset \bigcup_{i=1}^n G_{\alpha_i}$.
\end{definition}

\begin{theorem}
	Suppose $K\subset Y\subset X$. Then $K$ is compact relative to $X \Llr K$ is compact relative to $Y$.
\end{theorem}
\begin{proof}
	\say{$\implies$} Suppose $K$ is compact relative to $X$.
	\ul{\ul{NTS}}: $K$ is compact relative to $Y$. Suppose $\{V_\alpha\}_\alpha$ be an open cover of $K$ with \ul{$V_\alpha$ open in $Y$}.
	This means $V_\alpha = Y\cap G_\alpha$ for some open set $G_\alpha$ in $X$, for each $\alpha$.
	We have $K\subset\bigcup_\alpha V_\alpha = \bigcup_\alpha (Y\cap G_\alpha) = Y\cap \left(\bigcup_\alpha G_\alpha\right) \subset \bigcup_\alpha G_\alpha \implies \{G_\alpha\}$ is an open cover of $K$ in $X$. But $K$ is compact in $X$, $\exists \alpha_1,\dots,\alpha_n$ such that $K\subset \bigcup_{i=1}^n G_{\alpha_i}$.
	Since $K\subset Y$, $K\subset \left( \bigcup_{i=1}^n G_{\alpha_i} \right) \cap Y = \bigcup_{i=1}^n (G_{\alpha_i} \cap Y) = \bigcup_{i=1}^n V_{\alpha_i} \implies K$ has a finite subcover in $Y$.
	So $K$ is compact in $Y$.

	\say{$\Lla$} Suppose $K$ is compact in $Y$.
	\ul{\ul{NTS}}: $K$ is compact in $X$.
	Let $\{G_\alpha\}$ be an open cover of $K$ in $X$, so $G_\alpha$ open in $X$ i.e., $K\subset \bigcup G_\alpha$.
	Take $V_\alpha = Y\cap G_\alpha$ - open in $Y$.
	Then $\bigcup V_\alpha = \bigcup (Y\cap G_\alpha) = Y\cap\left( \bigcup_\alpha G_\alpha\right) = Y\cap \left( \bigcup_\alpha G_\alpha \right) \supset K$ and $K\subset Y \implies \{V_\alpha\}$ an open cover of $K$ in $Y$.
	But $K$ compact in $Y$, so $\exists \alpha_1,\dots,\alpha_n$ such that $K\subset \bigcup_{i=1}^n V_{\alpha_i} = \bigcup_{i=1}^n (Y\cap G_{\alpha_i}) = Y\cap \left( \bigcup_{i=1}^n G_{\alpha_i} \right) \subset \bigcup_{i=1}^n G_{\alpha_i} \implies K$ is compact in $X$.
\end{proof}

\begin{theorem}
	If $K\subset X^{m.s.}$ is compact, then $K$ is closed. %(If $K$ is not closed, $K$ is compact.).
\end{theorem}
\begin{proof}
	Let $K\subset X$ be compact. We will show $K^c$ is open.
	Let $x\in K^c$. For $y\in K$, let $V_y = N_{\frac{1}{2}\rho(x,y)}(y)$ - neighborhood of $y$ with radius $\frac{1}{2}\rho(x,y)$.
	Then $K\subset \bigcup_{y\in K}V_y$ i.e., $\{V_y\}_{y\in K}$ is an open cover of $K$.
	$K$ compact $\implies \exists y_1,y_2,\dots,y_n\in K$ such that $K\subset \bigcup_{1\leq i\leq n} V_{y_i} = V$.
	Let $W_{y_i} := N_{\frac{1}{2}\rho(x,y_i)}(x)$ - neighborhood of $x$ with radius $\frac{1}{2}\rho(x,y_i)$ for $i = 1,\dots n$ and set $W:=\bigcap_{i=1}^n W_{y_i} \ra$ open.
	Also, $V\cap W = \emptyset$ and $K\subset V$, so $x\in W\subset K^c \implies K^c$ is open.
	Therefore, $K$ is closed.
\end{proof}

\begin{theorem}
	Let $F\subset K\subset X^{m.s.}$.
	If $F$ is closed and $K$ is compact, then $F$ is compact.
\end{theorem}
\begin{proof}
	Let $\{V_\alpha\}$ be an open cover of $F$ i.e., $F\subset \bigcup V_\alpha$.
	Since $F$ is closed, $F^c$ is open. So $K\subset (\bigcup V_\alpha) \cup F^c$ - an open cover of $K$.
	$K$ compact $\implies \exists \alpha_1,\dots,\alpha_n$ such that $K\subset V_\alpha \cup\dots\cup V_{\alpha_n}\cup F^c$. This implies $F\subset V_{\alpha_1}\cup\dots\cup V_{\alpha_n}\cup F^c$ and $F\cap F^c = \emptyset \implies F\subset V_\alpha\cup\dots\cup V_{\alpha_n} \implies F$ is compact.
\end{proof}
\begin{corollary}
	$F\subset X^{m.s.}$ closed and $K\subset X^{m.s.}$ compact, then $F\cap K$ is compact.
\end{corollary}
\begin{proof}
	$K$ compact $\implies K$ closed. $F$ and $K$ closed $\implies F \cap K$ is closed.
	$F\cap K\subset K$ and $K$ compact $\implies F\cap K$ is compact.
\end{proof}

\begin{theorem}
	Let $\{K_\alpha\}$ be a collection of nonempty compact sets of $X$.
	If every finite intersection of this collection is nonempty, then $\bigcap K_\alpha \neq \emptyset$.
	\label{thm2-36}
\end{theorem}
\begin{proof}
	By contradiction suppose $\bigcap K_\alpha = \emptyset$.
	Let $K_1\subset \{K_\alpha\}$ be fixed. Suppose if $x\in K_1$ then $x\notin K_\alpha$ for some $\alpha$.
	That is, if $x\in K_1$ then $x\in K_\alpha^c$ for some $\alpha$.
	So, $K_1\subset \bigcup K_\alpha^c$ - an open cover of $K_1$ but $K_1$ is compact, so $\exists \alpha_1,\dots,\alpha_n$ such that $K_1\subset \bigcup_{i=1}^n K_{\alpha_i}^c = (\bigcap_{i=1}^n K_{\alpha_i})^c \implies K_1 \cap (\bigcap_{i=1}^n K_{\alpha_i}) = \emptyset \implies K_1\cap K_{\alpha_1}\cap \dots\cap K_{\alpha_n} = \emptyset$, a contradiction to finite interaction being nonempty.
	So $\bigcap K_\alpha \neq \emptyset$.
\end{proof}

\begin{theorem}
	Let $K\subset^{m.s.}$ be compact and $E\subset K$ be infinite.
	Then $E$ has a limit point in $K$.
	\label{thm2-37}
\end{theorem}
\begin{proof}
	Suppose by contradiction that $K$ does not have limit point of $E$.
	Then for each $q\in K$, there exists a neighborhood $V_q$ of $q$ which contains \ul{at most} one point $q$ of $E$ (if $q\in E$).
	Then $E\subset \bigcup_{q\in E} V_q$ and $K\subset \bigcup_{q\in K} V_q$.
	Since $E$ is infinite and $V_q$ contains at most one pointof $E$, so there is no finite subcover of $E$, and hence of $K$. This is a contradicts $K$ being compact.
	So $E$ has a limit point in $K$.
\end{proof}

\begin{theorem}
	If $\{I_n\}$ is a sequence of closed intervals \ul{in $\mb R$}, such that $I_n\supset I_{n+1}$ (for $n = 1,2,3\dots$), then it follows $\bigcap_n I_n\neq \emptyset$.
	\label{thm2-38}
\end{theorem}
\begin{proof}
	Let $I_n := [a_n,b_n]$ for $n=1,\dots$ and $E:= \{a_n: n = 1,2,\dots\}$.
	Then $E$ is nonempty and bounded above. So $\sup E\in \mb R$, call it $x:= \sup E$.
	Then $x\geq a_n$ for all $n\in \mb N$.
	Want to show: $x\leq b_m$ for all $m\in \mb N$. Clearly, $a_n\leq b_m$ for all $n,m$.
	Then $\sup \{a_n\} \leq b_m$ for all $m$ i.e., $x\leq b_m$ for all $m$.
	Hence $x\in[a_n,b_n]$ for all $n\in\mb N \implies x\in \bigcap [a_n,b_n]$.
\end{proof}

\begin{definition}
	[$k$-cell] $\{\vx = (x_1,\dots,x_k) : a_i\leq x_i\leq b_i\, (i = 1,\dots,k)\}$. So 1-cell is interval $[a_1,b_1]$, 2-cell is rectanlge with corners $(a_1,a_2)$ and $(b_1,b_2)$, 3-cell is box, etc.
\end{definition}
\begin{theorem}
	If $\{I_n\}$ a sequence of $k$-cells (in $\mb R^k$) such that $I_n\supset I_{n+1}$ for $n=1,2,\dots$, then $\bigcap_n I_n\neq\emptyset$.
\end{theorem}
\begin{proof}
	Let $I_n:=\{\vx = (x_1,\dots,x_k): a_{n,j} \leq x_j \leq b_{n,j} \, (j = 1,\dots,k)\}$ for $n = 1,2,\dots$ and set $I_{n,j} = [a_{n,j},b_{n,j}] \subset \mb R$ for fixed $j$.
	For each fixed \ul{$j$}, $\{I_{n,j}\}_n$ satisfies $I_{n,j} \supset I_{n+1,j}$ for $n = 1,2,\dots$.
	By Theorem \ref{thm2-38}, $\bigcap_n I_{n,j} \neq \emptyset$ implies $\exists x_j^*\in I_{n,j}$ for all $n=1,2,\dots$.
	Take $x^* = (x_1^*,\dots,x_k^*)$. Then $x^*\in I_n$ for all $n=1,\dots$, so $\bigcap_n I_n\neq \emptyset$.
\end{proof}

\begin{theorem}
	Every $k$-cell is compact.
\end{theorem}
\begin{proof}
	Skip.
\end{proof}
\begin{example}
	1-cell or $[a,b]\subset \mb R$ is compact.
\end{example}

\begin{theorem}
	Let \ul{$E\subset\mb R^k$}. Then the following statements are equivalent.
	\begin{enumerate}
		\item[(i)] $E$ is closed and bounded.
		\item[(ii)] $E$ is compact.
		\item[(iii)] Every infinite subset of $E$ has a limit point in $E$.
	\end{enumerate}
\end{theorem}
\begin{remark}
	Some remarks:
	\begin{enumerate}
		\item[(I)] (i) $\Llr$ (ii) in $\mb R^k$ - Heine-Borel Theorem.
		\item[(II)] (ii) $\Llr$ (iii) holds in general metric space.
		\item[(III)] (i) $\not\Lr$ (ii) or (iii) in metric space.
	\end{enumerate}
\end{remark}
\begin{example}
	Take $X = \mb Q$ and set $E:=\{q\in\mb Q: 2<q^2<3\}$.
	Then $E$ is closed and bounded but not compact in $\mb Q$.
\end{example}
\begin{example}
	Take $X = \mb R$ with discrete metric.
	$E := \{x\in\mb R : 0\leq x\leq 1\}$. Then $E$ is closed and bounded but not compact.
\end{example}
\begin{proof}
	We will show: (i) $\implies$ (ii), (ii) $\implies$ (iii) and (iii) $\implies$ (i).

	(i) $\implies$ (ii): Suppose $E\subset\mb R^k$ is closed and \ul{bounded}.
	$E$ bounded $\implies \exists$ a $k$-cell $K$ such that $E\subset K$.
	But $E$ is closed and $K$ is compact, so $E$ is compact.

	(ii) $\implies$ (iii) follows by Theorem \ref{thm2-37}.

	(iii) $\implies$ (i): We will prove by contradiction.
	Suppose $E$ is not bounded.
	Then for each $n = 1,2,\dots$ there exists $\vx_n\in E$ such that $|\vx_n|_{\mb R^k}>n$.
	Let $S := \{\vx_n\in E : |\vx_n|_{\mb R^k} > n\}\subset E$.
	Then $S$ is infinite and does not have a limit point in $E$, a contradiction.
	Now suppose $E$ is not closed. Then $\exists \vx_0\in\mb R^k\backslash E$ such that $\vx_0$ is a limit point of $E$.
	Then for each $n = 1,2,\dots$ there exists $\vx_n\in E$ such that $|\vx_n-\vx_0|_{\mb R^k} < \frac{1}{n}$ (neighborhood of $\vx_0$).
	Let $S := \{\vx_n\in E : |\vx_n - \vx_0|<\frac{1}{n}\}$. Then $S$ is infinite and $\vx_0$ is a limit point of $S$. But $\vx_0\notin E$.
	We're done if there are no other limit points of $S$.
	Suppose $\vy\in\mb R^k$ and $\vx_0\neq\vy$. Then $|\vx_0 - \vy_0|_{\mb R_k} = |\vx_0 - \vx_n + \vx_n - \vy_0|_{\mb R^k} \os{\Delta}{\leq} |\vx_0 - \vx_n|_{\mb R^k} + |\vx_n - \vy|_{\mb R^k} < \frac{1}{n} + |\vx_n - \vy|_{\mb R^k} \implies |\vx_n - \vy|_{\mb R^k} > |\vx_0 - \vy|_{\mb R^k} - \frac{1}{n} > \frac{1}{2} |\vx_0-\vy|_{\mb R^k}$ for some \ul{$n$ large} $\implies \vy$ is not a limit point of $E$, a contradiction.
\end{proof}

\begin{theorem}
	[Weierstrass] Every \ul{bounded} \ul{infinite} subset of $\mb R^k$ has a limit point in $\mb R^k$.
\end{theorem}
\begin{proof}
	Let $E\subset\mb R^k$ be a bounded infinite subset.
	$E$ bounded $\implies E\subset K$ - a compact $k$-cell.
	Theorem \ref{thm2-37} $\implies E$ has a limit point in $K\subset\mb R^k$.
\end{proof}

\begin{definition}
	[Perfect set] $E\subset X$ is perfect if
	\begin{enumerate}
		\item[(a)] $E$ is closed (i.e., $E'\subset E$), and
		\item[(b)] every point of $E$ is a limit point of $E$ (i.e., $E\subset E'$).
	\end{enumerate}
	i.e., $E = E'$.
\end{definition}
\begin{example}
	$[a,b]\subset\mb R$ is perfect.
\end{example}
\begin{theorem}
	Let $P\subset\mb R^k$ nonempty and perfect. Then $P$ is uncountable.
\end{theorem}
\begin{proof}
	Suppose by contradiction that $P$ \ul{is countable}. Then we can enumerate elements of $P$ as $\vx_1,\vx_2,\vx_3,\dots$.
	Hence we used the fact that since $P$ is perfect, $P$ has infinite elements.
	We will construct neighborhoods: Let $V_1 := N_r(\vx_1)$. $\vx_1\in P$ and $P$ is perfect $\implies \vx_1$ is a limit point of $P$.
	This implies $\exists \vx\in V_1$ such that $\vx\in V_1\cap P$. Since $\vx\in V_1$ and $V_1$ is open, $\exists r'>0$ such that $N_{r'}(\vx)\subset V_1$.
	Define $r_1 := \min\{\frac{r'}{2}, \frac{|\vx-\vx_1|}{2}\}$.
	Let $V_2 := N_{r_1}(\vx)$. Then
	\begin{itemize}
		\item $\conj{V_2} \subset V_1$,
		\item $\vx_1\notin \conj V_2$,
		\item $V_2\cap P\neq \emptyset$.
	\end{itemize}
	Inductively, we construct $\{V_n\}$:
	\begin{enumerate}
		\item[(i)] $\conj{V_{n+1}}\subset V_n$,
		\item[(ii)] $\vx_n\notin V_{n+1}$,
		\item[(iii)] $V_{n+1}\cap P\neq \emptyset$.
	\end{enumerate}
	Now, let $K_n:= \conj{V_n}\cap P$, where $\conj{V_n}$ closed and $P$ closed.
	Then $K_n$ is closed and hence compact (since $\conj{V_n}$ is bounded).
	Also, by construction $K_n\supset K_{n+1}$ for $n=1,2,\dots$.
	This implies \ul{$\bigcap K_n\neq \emptyset$} (Theorem \ref{thm2-36} Corollary).
	We know $\vx_n\notin \conj{V_{n+1}}$. So $\vx_n\notin K_{n+1}$ and so $\vx_n\notin \bigcap_n K_n\subset P$ and $\vx_n\in P$.
	Therefore $\bigcap K_n=\emptyset$, a contradiction. So $P$ is uncountable.
\end{proof}

\begin{definition}
	[Cantor set] Example of a perfect set in $\mb R$ that contains no \ul{segment}.
	\begin{align*}
		E_0 &: [0,1] \\
		E_1 &: [0,\frac{1}{3}]\cup[\frac{2}{3},1] \\
		E_2 &: [0,\frac{1}{9}]\cup[\frac{2}{9},\frac{1}{3}]\cup[\frac{6}{9}, \frac{7}{9}]\cup [\frac{8}{9},1]
	\end{align*}
	\begin{note}
		Some notes:
		\begin{itemize}
			\item No end points are removed,
			\item $E_{n+1}$ contains only points of $E_n$ i.e., $E_n\supset E_{n+1}$,
			\item $P = \bigcap_n E_n\neq\emptyset$ - $P$ is the Cantor set.
		\end{itemize}
	\end{note}
	Properties of $E_n$ and $P$:
	\begin{enumerate}
		\item $E_n$ is the union of $2^n$ intervals of length $\frac{1}{3^n}$.
		\item $P$ is compact.
		\item $P$ contains no segment.
		\item $P$ is a perfect set - hence uncountable.
	\end{enumerate}
\end{definition}

\subsection{Connected set}

\begin{definition}
	[Separated sets] $A,B\subset X^{m.s.}$ are separated if $A\cap\conj B=\emptyset$ and $B\cap\conj A = \emptyset$.
\end{definition}
\begin{example}
	$X = \mb R$ with usual metric. $A = (0,1)$ and $B = (1,2)$. Then $A\cap\conj B = (0,1)\cap\conj{(1,2)} = (0,1)\cap[1,2] = \emptyset$ and $\conj A\cap B = \conj{(0,1)}\cap(1,2) = [0,1]\cap(1,2) = \emptyset$. $A,B$ separated.
	
	However, $A = (0,1]$ and $B = (1,2)$ are \ul{not separated} since $A\cap\conj B = (0,1]\cap[1,2] = \{1\} \neq \emptyset$.
\end{example}
\begin{definition}
	[Connected set] $E\subset X$ is connected if $E$ is \ul{not} a union of two nonempty separated sets.
\end{definition}

\begin{theorem}
	$E\subset\mb R$ is connected $\Llr$ if $x,y\in E$ and $x<z<y$ then $z\in E$.
\end{theorem}
\begin{proof}
	\say{$\implies$} Suppose $x,y\in E$ and $\exists z\in (x,y)$ but $z\notin E$.
	We will show: $E$ is not connected. We will construct two nonempty separated sets.
	Let $A:= E\cap (-\infty,z)$ and $B:= E\cap(z,\infty)$.
	Then $A\neq\emptyset$ since $x\in E$ and $x\in(-\infty,z)$, and $B\neq\emptyset$ since $y\in E$ and $y\in(z,\infty)$.
	Now, $\conj A \subset (-\infty,z]$ and $\conj B\subset[z,\infty)$.
	So, $\conj A\cap B=\emptyset$ and $\conj B\cap A = \emptyset$.
	Also, $E = A\cup B$.
	Therefore $E$ is a union of two nonempty separated sets and hence not connected.

	\say{$\Lla$} Suppose $E$ is not connected. We will show: if $x,y\in E$, $\ul{\exists z}\in(x,y)$ such that $z\notin E$.
	Since $E$ is not connected, there exist nonempty sets $A$ and $B$ such that $E = A\cup B$, $A\cap\conj B=\emptyset$ and $\conj A\cap B = \emptyset$.
	Let $x\in A$, $y\in B$ and WLOG $x<y$.
	Define $z:= \sup(A\cap [x,y])$.
	Then $z$ is well defined since $x\in A\cap[x,y]$ and $A\cap[x,y]$ is bounded by $y$.
	By Theorem 2.28 (book) $z\in \conj{A\cap[x,y]}\os{?}{=} \conj A\cap\conj{[x,y]} = \conj A\cap [x,y] \implies \ul{z\in \conj A} \implies z\notin B$ since $\conj A\cap B = \emptyset$. This implies $z\neq y$ (since $y\in b$), but least upper bound $z\leq y$ upper bound, \ul{so $z<y$}.
	If $z\notin A$ then $z\neq x$ ($x\in A$). This means \ul{$z>x$}. Combining $x<z<y$.
	Since $z\notin A$ and $z\notin B$, $z\notin E = A\cup B$. We're done.

	If \ul{$z\in A$}, then we repeat the argument with $z$ instead of $x$ and $y\in B$ to find $z_1\in (z,y)$ such that $z_1\notin E$.
\end{proof}

\section{Numerical sequences and series}

\begin{definition}
	[Convergent sequences] $(X,\rho)$ - metric space.
	$\{p_n\}\subset X$ is said to be convergent to $p\in X$ if $\forall \epsilon >0$, $\exists N\in\mb N$ such that $\rho(p_n,p)<\epsilon$ for all $n\geq N$.
\end{definition}
\begin{note}
	$N = N(\epsilon,p)$ - depends on $\epsilon$ and $p$.
\end{note}
\ul{Notation}: If $\{p_n\}$ converges to $p\in X$, we write $p_n\us{n\ra\infty}{\lra}p$ \ul{\ul{or}} $\lim_{n\ra\infty} p_n = p$.
\begin{example}
	$\{\frac{1}{n}:n=1,2,\dots\}\subset\mb R$, $\frac{1}{n}\us{n\ra\infty}{\lra}0$.
\end{example}
\begin{proof}
	Let $\epsilon>0$ be given. Want to show: $\exists N\in\mb N$ such that $|\frac{1}{n} - 0|<\epsilon$ for all $n\geq N$.
	Take $N>\frac{1}{\epsilon}$. Then for $\ul{n\geq N}$, $|\frac{1}{n}-0| = \frac{1}{n} < \epsilon$. So $\frac{1}{n} \us{n\ra\infty}{\lra}0$.
\end{proof}
\begin{example}
	$\{\frac{1}{n}\}_n$ does not converge \ul{in $(0,1)$}. - space matters.
\end{example}
\begin{example}
	$\{\frac{1}{n}\}_n$ does not converge in $\mb R$ with \ul{discrete metric}.
\end{example}

\begin{theorem}
	Let $\{p_n\}\subset(X,\rho)^{m.s.}$. Then
	\begin{enumerate}
		\item[(a)] $p_n\ra p$ in $X \Llr$ every neighborhood of $p$ contains all but finitely many points of $\{p_n\}$.
		\item[(b)] If $p_n\ra p$ and $p_n\ra p'$ then $p'=p$ (uniqueness of limit).
		\item[(c)] If $\{p_n\}$ converges, then $\{p_n\}$ is bounded.
		\item[(d)] If $E\subset X$ and $p\in E'$ then there exists a sequence $\{p_n\}\subset E$ such that $p_n\ra p$.
	\end{enumerate}
	\label{thm-3-2}
\end{theorem}
\newpage
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] $p_n \ra p \iff$ every neighborhood of $p$ contains all but finitely many points of $\{p_n\}$.
			
			\say{$\implies$} Suppose \ul{$p_n\ra p$}. Let $N_r(p) = \{x\in X: \rho(x,p) < r\}$ be any neighborhood of $p$.
			Since $p_n \ra p$, for \ul{$\epsilon = r$}, $\exists N\in\mb N$ such that $\rho(p_n,p) < \epsilon = r$ for all $n\geq N$.
			This implies $N_r(p)$ contains all except possibly $N-1$ elements of $\{p_n\}$.
			
			\say{$\Lla$} Let $\epsilon > 0$. \ul{NTF}: $N\in\mb N$ such that $\rho(p_n,p)<\epsilon$ for all $n\geq N$.
			By assumption, $\epsilon$-neighborhood $N_\epsilon(p)$ contains all but finitely many points of $\{p_n\}$ i.e., $\exists N\in\mb N$ such that $\rho(p_n,p)<\epsilon$ for all $n\geq N$. This implies $p_n\ra p$.

		\item[(b)] $p_n\ra p$ and $p_n\ra p' \implies p' = p$.
			
			\ul{Claim}: $\rho(p,p') = 0 \implies p' = p)$.
			\ul{We will show}: $\rho(p,p)<\epsilon$ \ul{for any $\epsilon>0$}.
			Let $\epsilon > 0$. Since $p_n\ra p \implies \exists N_1\in\mb N$ such that $\rho(p_n,p) < \frac{\epsilon}{2}$ for all $n\geq N_1$.
			Also $p_n \ra p' \implies \exists N_2\in\mb N$ such that $\rho(p_n,p') \frac{\epsilon}{2} < $ for all $n\geq N_2$.
			Then $\rho(p,p') \leq \rho(p,p_n) + \rho(p_n,p') < \frac{\epsilon}{2} + \frac{\epsilon}{2}$ for all $n\geq N = \max\{N_1,N_2\}$.
			That implies $\rho(p,p')<\epsilon$. Since $\epsilon>0$ is arbitrary, $\rho(p,p') = 0$ and hence $p = p'$.

		\item[(c)] If $\{p_n\}$ converges, then $\{p_n\}$ is \ul{bounded} ($\exists N_r(p) \supset \{ p_n\}$).

			$\{p_n\}$ converges $\implies \exists p\in X$ such that $p_n\ra p$.
			$p_n\ra p \implies$ for $\epsilon = 1$, $\exists N\in\mb N$ such that $\rho(p_n,p) < 1$ for all $n\geq N$.
			Set $r:= \max\{1,\rho(p_1,p),\rho(p_2,p),\dots,\rho(p_{n-1},p)\}$.
			Then $p_n\in\mb N$ for all $n\in\mb N$ implies that $ \{p_n\}$ is bounded.

		\item[(d)] $E\subset X$ and $p\in E' \implies \exists \{p_n\}\subset E$ such that $p_n\ra p$.
			
			$p$ is a limit point of $E \implies$ \ul{every neighborhood} of $p$ contains \ul{at least one point of $p$}.
			That implies for each $n = 1,2,\dots$, $\exists p_n\in E$ such that $\rho(p_n,p) < \frac{1}{n}$. Now we will show: $p_n\ra p$.
			Let $\epsilon > 0$. Then for $N > \frac{1}{\epsilon}$, $\rho(p_n,p) < \frac{1}{n} \leq \frac{1}{N} < \epsilon$ for all $n\geq N$, which implies $p_n\ra p$.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	Let $\{s_n\},\{t_n\}\subset\mb C$. Then if $s_n\ra s$ and $t_n\ra t$:
	\begin{enumerate}
		\item[(a)] $s_n + t_n\ra s+t$
		\item[(b)] $c\cdot s_n \ra c\cdot s$ for any $c\in\mb C$
		\item[(c)] $s_n\cdot t_n\ra s\cdot t$
		\item[(d)] $\frac{1}{s_n} \ra \frac{1}{2}$ whenever $s_n\neq 0$ for all $n$ and $s\neq 0$ ($\implies \frac{t_n}{s_n} \ra \frac{t}{s}$ by (c)).
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] Let \ul{$\epsilon > 0$} be given. \ul{NTF}: $\exists N\in\mb N$ such that $|(s_n+t_n) - (s+t)|_{\mb C} < \epsilon$ for all $n\geq N$.i

			Then $s_n\ra s \implies \exists N_1\in\mb N$ such that $|s_n-s|_{\mb C} < \frac{\epsilon}{2}$ for all $n\geq N_1$.
			Also $t_n\ra t \implies \exists N_2\in\mb N$ such that $|t_n-t|_{\mb C} < \frac{\epsilon}{2}$ for all $n\geq N_2$.
			For $n\geq \max\{N_1,N_2\} = N$
			\begin{align*}
				| s_n + t_n - s - t|_{\mb C} \os{\Delta}{\leq} |s_n-s|_\mb C + |t_n-t|_\mb C < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon
			\end{align*}

		\item[(b)] For you.

		\item[(c)] Let $\epsilon > 0$. \ul{NTS}: $\exists N\in\mb N$ such that $|s_n t_n - st|<\epsilon$ for all $n\geq N$.

			Then $s_n\ra s\implies \exists N_1\in\mb N$ such that $|s_n-s|_\mb C< \frac{\epsilon}{2M}$ for all $n\geq N_1$
			and $t_n\ra t \implies \exists N_2\in\mb N$ such that $|t_n-t|_\mb C< \frac{\epsilon}{2(|s|+1)}$ for all $n\geq N_2$.
			For $n\geq \max\{N_1,N_2\} = N$
			\begin{align*}
				|s_nt_n-st|_\mb C = |s_nt_n-st_n + st_n - st| \os{\Delta}{\leq} |s_n - s|_\mb C\cdot |tn|_\mb C + |s|_\mb C \cdot |t_n-t|_\mb C
			\end{align*}
			$\{t_n\}$ converges $\implies \{t_n\}$ bounded in $\mb C \implies \exists M>0$ such that $|t_n|_\mb C \leq M$ for all $n$.
			Then for $n\geq N$,
			\begin{align*}
				|s_nt_n-st|_\mb C &\leq |s_n-s|_\mb C \cdot |tn|_\mb C + |t_n-t|_\mb C \cdot |s|_\mb C \\
								  &\leq M|s_n-s|_\mb C + |s|\cdot|t_n-t| \\
				&< M\cdot\frac{\epsilon}{2M} + |s|\cdot\frac{\epsilon}{2(|s|+1)} < 1 \\
				&< \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon,
			\end{align*}
			which implies that $s_nt_n\ra st$.

		\item[(d)] Let $\epsilon>0$. \ul{NTS}: $\exists N\in\mb N$ such that $|\frac{1}{s_n} - \frac{1}{2}|_\mb C <\epsilon$ for all $n\geq N$. 
			$$ \left| \frac{1}{s_n} - \frac{1}{s} \right|_\mb C = \frac{|s_n-s|_\mb C}{|s|_\mb C\cdot |s_n|_\mb C} $$ 
			\ul{Need to control} $|s_n|$.
			Then $s_n\ra s\implies \exists N_1\in\mb N$ such that $|s_n-s|_\mb C < \frac{|s|}{2}$ for all $n\geq N_1$.
			\ul{Claim}: For $n\geq N_1$, $|s_n|_\mb C > \frac{|s|_\mb C}{2}$.
			Suppose not: ($|s_n|\leq |s|/2$)
			$$ |s|_\mb C = |s-s_n + s_n|_\mb C \leq |s-s_n|\mb C + |s_n|_\mb C < \frac{|s|_\mb C}{2} + \frac{|s|_\mb C}{2} = |s|_\mb C$$ - a contradiction.
			Now, $\exists N_2\in\mb N$ such that $|s_n - s|\leq \epsilon\cdot \frac{|s|^2}{2}$ for all $n\geq N_2$.
			Take $N = \max\{N_1,N_2\}$. Then for $n\geq N$,
			$$ \left| \frac{1}{s_n} = \frac{1}{s} \right| = \frac{|s_n-s|}{|s|\cdot |s_n|} < \frac{\epsilon\cdot |s|^2\cdot 2}{2\cdot|s|\cdot |s|} = \epsilon,$$
			which implies $\frac{1}{s_n} \ra \frac{1}{s}$.
	\end{enumerate}
\end{proof}

\begin{theorem}
	Cases:
	\begin{enumerate}
		\item[(a)] Supose $\{\vx_n\} \subset \mb R^k$ and $\vx_n = (x_{1,n},x_{2,n},\dots, x_{k,n})$.
			Then $\vx_n\us{n\ra\infty}{\lra}\vx$ in $\mb R^k \iff x_{j,n} \us{n\ra\infty}{\lra} x_j$ for all $j = 1,2,\dots,k$.
		\item[(b)] Suppose $\{\vx_n\},\{\vy_n\} \subset \mb R^k$ and $\{\beta_n\}\subset\mb R$. 
			If $\vx_n\us{\mb R^k}{\ra}\vx,\vy_n\us{\mb R^k}{\ra}\vy$ and $\beta_n\us{\mb R^k}{\ra}\beta$ as $n\ra\infty$, then
			\begin{itemize}
				\item $\vx_n + \vy_n \ra \vx + \vy$
				\item $\beta_n\vx_n\ra\beta\vx$
				\item $\vx_n\cdot\vy_n\ra\vx\cdot\vy$, where \say{$\cdot$} is innter produce in $\mb R^k$.
			\end{itemize}
	\end{enumerate}
\end{theorem}
\begin{proof}
	Let
	\begin{align*}
		\vx_1 &: (x_{1,1},x_{2,1},\dots,x_{k,1}) \\ 
		\vx_2 &: (x_{1,2},x_{2,2},\dots,x_{k,2}) \\
		\vdots \\
		\vx_n &: (x_{1,n},x_{2,n},x_{k,n})
	\end{align*}
	with $\vx_n \os{\mb R^k}{\lra} \vx$ and $x_{j,n}\os{\mb R}{\lra} x_j$ as $n\ra\infty$ for $j=1,\dots,k$.

	\say{$\implies$} Suppose $\vx_n \ra \vx$. \ul{Let $\epsilon>0$ be fixed}.
	\ul{Want to show}: For each fixed $j\in\{1,\dots,k\}$, $\exists N\in\mb N$ such that $|x_{j,n}-x_j|_{\mb R} <\epsilon$ for all $n\geq N$.
	Then $\vx_n\ra\vx \implies \exists N\in\mb N$ such that $|\vx_n - \vx|_{\mb R^k} < \epsilon$ for all $n\geq N$.
	i.e., $\sqrt{(x_{1,n} - x_1)^2 + (x_{2,n} - x_2)^2 + \dots + (x_{k,n}-x_k)^2} < \epsilon$ for all $n\geq N$ implies that we have $|x_{j,n}-x_j|\leq \sqrt{(x_{1,n}-x_1)^2 + \dots + (x_{k,n} - x_k)^2} < \epsilon \implies x_{j,n} \ra x_j$ as $n\ra\infty$.

	\say{$\Lra$} Suppose $x_{j,n}\ra x_j$ for all $j = 1,\dots,k$. \ul{Want to show}: $\vx_n\ra\vx$.
	Let $\epsilon>0$ be fixed. Need to find $N\in\mb N$ such that $|\vx_n-\vx|_{\mb R^k} < \epsilon$ for all $n\geq N$.
	i.e., $\sqrt{(x_{1,n} - x_1)^2 + \dots + (x_{k,n} - x_k)^2} < \epsilon$.
	Since $x_{j,n} \ra x_j$ as $n\ra\infty$ for all $j = 1,\dots, k$, $\exists N = \max\{ N_1,\dots, N_k\}$ such that $|x_{j,n} - x_j| < \frac{\epsilon}{\sqrt{k}}$ for all $n\geq N$.
	Then $|\vx_n - \vx| < \sqrt{k\left(\frac{\epsilon}{\sqrt{k}}\right)^2} = \epsilon$ for $n\geq N$. This implies $\vx_n\ra \vx$.
	(b) follows easily.
\end{proof}

\subsection{Subsequences}

\begin{definition}
	[Sequence] $s_n$: $s_1, s_2, s_4, s_5, s_6, s_7, \dots, s_n, \dots$, then $s_{n_k}$: $s_{n_1}, s_{n_2}, s_{n_3}, s_{n_4}, \dots$ is a subsequence.
	\begin{note}
		Note:
		\begin{enumerate}
			\item $n_k \geq k$ for all $k$.
			\item $n_1 \leq n_2 \leq n_3 \leq \dots$.
		\end{enumerate}
	\end{note}
\end{definition}

\begin{lemma}
	$\{p_n\}$ converges to $p$ in $X^{m.s.} \iff$ every subsequence $\{p_{n_k}\}$ of $\{p_n\}$ converges to the same limit $p$.
\end{lemma}
\begin{proof}
	\say{$\implies$} Suppose $p_n\us{n\ra\infty}{\lra}p$. and let $\{p_{n_k}\}$ be a subsequence.
	\ul{Want to show}: $p_{n_{\ul{k}}}\us{k\ra\infty}{\lra}p$.
	Let $\ul{\epsilon}>0$. \ul{NTS}: $\exists K\in\mb N$ such that $\rho(p_{n_k},p) < \epsilon$ for all $k\geq K$.
	Then $p_n\ra p\implies \forall\epsilon>0$, $\exists N\in\mb N$ such that $\rho(p_n,p) < \epsilon$ for all $n\geq N$.
	We know $n_k \geq K$ for all $K$, so $n_k \geq K \geq N \implies \rho(p_{n_k},p) < \epsilon$ for all $k\geq N$ (implies $n_k\geq k \geq N$).
	This implies $p_{n_k}\ra p$ as $k\ra\infty$.

	\say{$\Lra$} Since $\{p_n\}$ is a subsequence of itself, $p_n\ra p$.
\end{proof}

\begin{theorem}
	Cases:
	\begin{enumerate}
		\item[(a)] Let $(X,\rho)$ be a compact metric space.
			If $\{p_n\}\subset X$, then $\exists$ a subsequence $\{p_{n_k}\}$ of $\{p_n\}$ such that $\{p_{n_k}\}$ converges.
		\item[(b)] Every \ul{bounded sequence in $\mb R^k$} has a convergent subsequence.
			($\{p_n\}$ bounded in $\mb R^k \implies \exists$ a compact $k$-cell $K$ such that $\{p_n\}\subset K \os{(a)}{\implies} \exists$ a convergent subsequence.)
	\end{enumerate}
\end{theorem}
\begin{definition}
	[Range of a sequence] $\{p_n\} := \{p_n:n\in\mb N\}$. \ul{Eg}: (1) $p_n = (-1)^n \implies$ Range $ = \{-1,1\}$ - finite $\implies$ closed. (2) $p_n = \frac{1}{n} \implies $ Range $ = \{\frac{1}{n}\}$.
\end{definition}

\begin{proof}
	\ul{Case 1}: Suppose range of $\{p_n\}$, say $E$ is finite.
	Then $\exists p\in\{p_n\}$ such that $p_{n_1} = p_{n_2} = \dots = p_{n_k} = p \implies \exists \{p_{n_k}\}$ of $\{p_n\}$ such that $p_{n_k}\ra p$.

	\ul{Case 2}: $E$ is infinite.
	Since $E\subset X^{\text{compact}}$ is infinite, $E$ has a limit $p$ in $X$.
	\begin{note}
		While every neighborhood of $p$ contains infinitely many points of $E$, this may not be a subsequence.
	\end{note}
	$p\in E'$ and $E$ is infinite, so $\exists p_{n_1}\in E$ such that $\rho(p,p_{n_1}) < 1$.
	Next, $\exists p_{n_2}\in E$ with $n_1 < n_2$ such that $\rho(p,p_{n_2}) < \frac{1}{2}$.
	Inductively, $\exists p_{n_k}$ with $n_1 < n_2 < \dots < n_k$ such that $\rho(p,p_{n_k}) < \frac{1}{2^{k-1}} \os{?}{\implies} p_{n_k} \ra p$ as $k\ra\infty$.

	\ul{Notation}: $E^* = $ set of all subsequential limits $ = \{p\in X : \exists\{ p_{n_k} \}\text{ such that }p_{n_k} \ra p\}$.
	
	\ul{Eg}: $\{(-1)^n\} \implies E^* = \{-1,1\}$.
\end{proof}
\begin{theorem}
	Let $\{p_n\}\subset X$ and $E^* = \{p\in X: \exists \{ p_{n_k}\} \text{ such that } p_{n_k}\ra p\}$.
\end{theorem}
\begin{proof}
	We will show $(E^*)' \subset E^*$.
	Let $q\in (E^*)'$ i.e, $q$ is a limit point of $E^*$.
	We will construct a subsequence $\{p_{n_k}\}$ such that $p_{n_k} \ra q$.
	Let $n_1\in\mb N$ be such that $p_{n_1}\neq q$ (if no such index exists then $E^* = \{q\}$ - closed.
	Set $\delta := \rho(q,p_{n_1}) > 0$ because $p_{n_1}\neq q$.
	Let $n_2 > n_1$ such that $\rho(p_{n_2},q) < \frac{\delta}{2}$.
	Inductively, let $n_1 < n_2 < \dots < n_k$ such that $\rho(p_{n_k},q) < \frac{\delta}{2^{k-1}}$.
	This implies $p_{n_k}\ra q$ as $k\ra\infty \implies q\in E^* \implies E^*$ is closed.
\end{proof}

\subsection{Cauchy sequence}

\begin{definition}
	$(X,\rho)$ - metric space. A sequence $\{p_n\}_n\subset X$ is Cauchy if $\forall \epsilon>0$, $\exists N = N(\epsilon)>0$ such that $\rho(p_n,p_m)<\epsilon$ for all $n,m\geq \ul{N}$.
\end{definition}

\begin{example}
	$X = \mb R$ with usual metric, then $\{\frac{1}{n}\}_a$ is Cauchy sequence.
\end{example}
\begin{proof}
	Let $\epsilon > 0$ be fixed. NTF $N\in\mb N$ such that $\left|\frac{1}{n}-\frac{1}{m}\right| < \epsilon$ for all $n,m\geq N$.
	Using $\Delta$ inequality, $|\frac{1}{n}-\frac{1}{m}| \leq |\frac{1}{n}| + |\frac{-1}{m}| = \frac{1}{n} + \frac{1}{m} < \frac{\epsilon}{2} + \frac{\epsilon}{2}$ for $n,m>\frac{2}{\epsilon} = N \implies \{\frac{1}{n}\}_n$ is Cauchy.
	Examples of Cauchy sequence that do not converge.
	\begin{enumerate}
		\item $s_n = (1+\frac{1}{n})^n\in\mb Q$ and $s_n\ra e\notin\mb Q \implies s_n$ does not converge in $\mb Q$.
		\item $\{\frac{1}{n}\}_{n\geq 2}\subset(0,1)$ Cauchy that does not converge in $(0,1)$.
	\end{enumerate}
	Done.
\end{proof}
\begin{definition}
	$E\subset X^{m.s.}$, then $\text{diam}\, E = \sup\rho(p,q)$ for $p,q\in E$.
\end{definition}
\begin{example}
	$X = \mb R$, $E = (0,1) \implies \text{diam}\, E = 1$. $X = \mb R^2$ and $E = [0,1]\times [0,1] \implies \text{diam}\, E = \sqrt{2}$.
\end{example}

Given $\{p_n\}\subset X^{m.s.}$, let $E_n := \{p_n,p_{n+1},\dots,\}$. Then \ul{$\{p_n\}$ is Cauchy $\iff \us{n\ra\infty}{\text{diam}}\, E_n = 0$}.

\begin{theorem}
	Cases:
	\begin{enumerate}
		\item[(a)] Let $E\subset(X,\rho)$. Then $\diam{E} = \diam\conj E$
		\item[(b)] If $\{K_n\}_n\subset X$ a sequence of compact sets such that
			\begin{itemize}
				\item $K_n\supset K_{n+1}$, and
				\item $\us{n\ra\infty}{\text{diam}}\, K_n = 0$
			\end{itemize}
			then $\bigcap K_n$ contains exactly one point.
	\end{enumerate}
	\label{thm-3-10}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] \say{$\geq$}
			Note that if $A\subset B$ then $\diam A\leq \diam B$.
			Then since $E\subset\conj E$, we have \ul{$\diam E\leq \diam \conj E$}.

			\say{$\leq$} We will show: $\diam\conj E\leq \diam E + \epsilon$ for all $\epsilon >0$.
			Let $\conj p, \conj q\in \conj E$. 
			\begin{enumerate}
				\item[(i)] If $\conj p, \conj q\in E$, then $$\us{\conj p,\conj q\in \conj E}{\sup}\rho(\conj p,\conj q) = \us{p,q\in E}{\sup}\rho(p,q).$$
				\item[(ii)] Suppose $\conj p, \conj q\in E'$. Then $\exists p,q\in E$ such that $\rho(\conj p,p)\leq \frac{\epsilon}{2}$ and $\rho(\conj q,q)\leq \frac{\epsilon}{2}$.
					Then $$\rho(\conj p,\conj q)\leq \rho(\conj p,p) + \rho(p,q) + \rho(q,\conj q) \leq \epsilon + \rho(p,q).$$
				\item[(iii)] Suppose $\conj p\in E'$ and $\conj q\in E$. Then $\exists p\in E$ such that $\rho(\conj p, p) < \frac{\epsilon}{2}$.
					Then $$\rho(\conj p,\conj q) \leq \rho(\conj p,p) + \rho(p,\conj q) \leq \frac{\epsilon}{2} + \diam E \leq \epsilon + \diam E.$$
			\end{enumerate}
			Then $\us{\conj p,\conj q\in \conj E}{\sup}\rho(\conj p,\conj q) \leq \epsilon + \us{p,q\in E}{\sup}\rho(p,q) \implies \diam \conj E \leq \epsilon + \diam E$.
			Since $\epsilon > 0$ is arbitrary, therefore $\diam \conj E\leq \diam E$.
			Hence $\diam\conj E = \diam E$.

		\item[(b)] We have $\bigcap_n K_n \neq \emptyset$.
			Suppose by contradiction that $\exists$ at least two points in $K = \bigcap_n K_n$.
			Then $\diam K> 0$ and $K\subset K_n$ for all $n \implies 0 < \diam K \leq \diam K_n \ra 0$ for all $n$ - a contradiction since $\us{n\ra\infty}{\text{diam}}\,K_n = 0$.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	Cases:
	\begin{enumerate}
		\item[(a)] Let $(X,\rho)$ a metric space. Then every convergent sequence is Cauchy.
		\item[(b)] Let $(x,\rho)$ a \ul{compact} metric space. Then a Cauchy sequence converges.
		\item[(c)] In $\mb R^k$, every Cauchy sequence converges.
	\end{enumerate}
\end{theorem}
\begin{definition}
	Let $(X,\rho)$ be a metric space. If every Cauchy sequence in $X$ converges, then $X$ is called a complete metric space.
\end{definition}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] Let $\{p_n\}\subset X$ be such that \ul{$p_n\ra p$} in $X$.
			\ul{WTS}: Let $\epsilon > 0$. We'll find $N\in\mb N$ such that $\rho(p_n,p_n) < \epsilon$ for all $n,m\geq N$.
			Then $p_n\ra p \implies \exists N\in\mb N$ such that $\rho(p_n,p) < \frac{\epsilon}{2}$ for all $n\geq N$.
			Then $\rho(p_n,p_m) \leq \rho(p_n,p) + \rho(p,p_m) < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon$ for all $n,m\geq N$.
			This implie $\{p_n\}$ is Cauchy.
		\item[(b)] Let $\{p_n\}\subset X^{\text{compact }m.s.}$ be Cauchy.
			\ul{NTS}: $\exists p\in X$ such that $p_n\ra p$.
			Let $E_n:=\{p_n,p_{n+1},\dots\}$.
			Then $\lim_{n\ra\infty} \diam{E_n} = \lim_{n\ra\infty}\conj E_n = 0$.
			Also $E_n\supset E_{n+1}$ and hence $\conj E_n\supset \conj E_{n+1}$ for al $n$.
			Since $\conj{E}_n\subset X^{\text{compact}}$, $\conj{E}_n$ is compact.
			Then $\bigcap \conj E_n = \{p\}$ (with $p$ unique) by Theorem \ref{thm-3-10}(b).
			\ul{Claim}: $p_n\ra p$.
			Let $\epsilon > 0$. Since $\us{n\ra\infty}{\text{diam}}\,E_n = 0$, $\exists N\in\mb N$ such that $\diam E_n < \epsilon$ for all $n\geq N$.
			Now $p\in\conj E_n$ for \ul{$n\geq N$} $\implies \rho(p,q) < \epsilon$ for all $q\in\conj E_n$ ($\subset E_n$) $\implies \rho(p,p_n)<\epsilon$ for all $n\geq N \implies p_n\ra p$.
		\item[(c)] Let $\{\vx_n\}\subset R^k$ be Cauchy, $E_n:=\{\vx_n,\vx_{n+1},\dots\}$.
			Then $\{\vx_n\}\subset \mb R^k$ Cauchy $\implies \lim_{n\ra\infty}\diam E_n = 0 \implies \exists N\in\mb N$ such that $\diam E_n < 1$ for all $n\geq N$.
			Define $R := \max\{|\vx_1|,\dots,|\vx_{N-1}|,1\}+1$.
			Then $\{\vx_n\}_n\subset B_r(\vzero)$. This implies $\{\vx_n\}$ is bounded $\implies \exists$ a compact $k$-cell $K$ such that $\{\vx_n\}\subset K$.
			By part (b) $\{x_n\}$ converges in $K$, hence in $X$.
	\end{enumerate}
	Done.
\end{proof}

Test 3 - Tuesday, Nov. 28. 
No class - Tuesday, Nov. 21. 
Meet this Saturday at 11am.

\ul{CH3}: 1-5, 7, 8, 9 (UG), 10, 11 (G), 13, 14(a)-(b) (G), 20-21, 22 (G), 23.

\begin{definition}
	A sequence $\{s_n\}$ is
	\begin{enumerate}
		\item monotonically increasing if $s_n\leq s_{n+1}$ for all $n$.
		\item monotonically decreasing if $s_n\geq s_{n+1}$ for all $n$.
	\end{enumerate}
	Sequence is monotonic if it is monotonically increasing or decreasing.
\end{definition}
\begin{theorem}
	Suppose $\{s_n\}\subset\mb R$ is monotonic. Then $\{s_n\}$ converges $\iff \{s_n\}$ is bounded.
\end{theorem}
\begin{proof}
	\say{$\implies$} $\{s_n\}$ converges $\os{\text{Thm \ref{thm-3-2}}}{\implies} \{s_n\}$ bounded.

	\say{$\Lla$} Suppose $\{s_n\}$ is bounded and assume $\{s_n\}$ is monotonically increasing.
	Let $E = \text{range}\{s_n:n\in\mb N\}$. Then $E$ is nonempty and $\{s_n\}$ bounded implies that $E$ is bounded.
	So $s:=\sup E\in\mb R$. We will show: $s_n\ra s$.
	Let $\epsilon>0$ be fixed. Then $\exists N\in\mb N$ such that $s-\epsilon< s_N< s$.
	$\{s_n\}$ monotonically increasing means $s-\epsilon< s_N\leq s_n < s$ for all $n\geq N$.
	This implies $s_n\ra s$.
\end{proof}

\begin{definition}
	[Upper and Lower \ul{limits} ($\liminf$ and $\limsup$)]
	Let $E$ be the set of all subsequential limits of $\{s_n\}\subset\mb R$.
	i.e., $E:=\{s\in\mb R:\exists\{s_{s_k}\}\subset\{s_n\} \text{ such that } s_{n_k}\ra s\}$.
	\ul{Define}: $s^*:= \sup E$ and $s_*:=\inf E$. Here $s^*,s_*\in\mb R\cup\{+\infty\}\cup\{-\infty\}$.
\end{definition}
\begin{example}
	$s_n: 3-\frac{1}{2},5+\frac{1}{3},3-\frac{1}{4},5+\frac{1}{5},3-\frac{1}{6},5+\frac{1}{7},3-\frac{1}{8},5+\frac{1}{9},\dots$.
	$E = \{3,5\}$ and $s^* = 5, s_* = 3$.

	$\inf\{s_n:n\geq 1\} = 3 - \frac{1}{2} = y_1$, and 
	$\inf\{s_n:n\geq 2,3\} = 3-\frac{1}{4} = y_2=y_3$, and
	$\inf\{s_n:n\geq 4,5\} = 3-\frac{1}{6} = y_4=y_5$, and 
	$\dots$, and
	$\inf\{s_n:n\geq k\} = y_k$
	\begin{note}
		$\{y_k\}$ is a monotonically increasing sequence bounded above by 5.
		This implies $\{y_k\}$ converges.
		Thus $s_* = \us{k=1,2,3,\dots}{\sup}(\inf\{s_n:n\geq k\})$.
	\end{note}
\end{example}
\begin{recall}
	Let $A\subset B$, then $\inf A\geq \inf B$ and $\sup A\leq \sup B$.
\end{recall}

\newpage

\ul{In general}, $s_* = \us{k=1,\dots}{\sup}(\inf\{s_n:n\geq k\}) = \lim_{k\ra\infty}(\inf\{s_n:n\geq k\})$ and $s^* = \us{k=1,2,\dots}{\inf}(\sup\{s_n:n\geq k\}) = \lim_{k\ra\infty}(\sup\{s_n:n\geq k\})$.
\ul{Book}: $s^*,s_*\in E$.

\ul{Notation}: $s^* = \sup E = \limsup_{n\ra\infty} s_n$ and $s_* = \inf E = \liminf_{n\ra\infty} s_n$.

\begin{note}
	$\displaystyle s_* = \inf E\leq \sup E = s^* \implies \ul{\liminf_{n\ra\infty} s_n\leq \limsup_{n\ra\infty} s_n}$.
\end{note}

\begin{theorem}
	Let $\{s_n\}\subset\mb R$. Then $\lim_{n\ra\infty} s_n = s\in\mb R \iff \liminf_{n\ra\infty} s_n = \limsup_{n\ra\infty} s_n = s\in\mb R$. (Holds also when $s = \pm\infty)$.
\end{theorem}
\begin{proof}
	\say{$\implies$} Suppose $s_n\ra s$. \ul{We will show}: 
	$$ \liminf_{n\ra\infty} \os{\checkmark}{\leq} \limsup_{n\ra\infty} s_n \os{(1)}{\leq} \lim_{n\ra\infty} s_n \os{(2)}{\leq} \liminf_{n\ra\infty} s_n \os{\checkmark}{\leq} \limsup_{n\ra\infty} s_n$$
	\begin{enumerate}
		\item \ul{We will show (1)}: Idea: show $\limsup_{n\ra\infty} s_n \leq \lim_{n\ra\infty} s_n + \epsilon$, for $\epsilon > 0$ arbitrary.
			Let $\epsilon > 0$ be fixed. $s_n\ra s\implies \exists N\in\mb N$ such that $|s_n-s|<\epsilon$ for all $n\geq N \implies -\epsilon < s_n-s < \epsilon$ for all $n\geq N \implies s_n < s+\epsilon$ for all $n\geq N \implies \sup\{s_n:n\geq N\}\leq s+\epsilon$.
			If $m>N$, then $\sup\{s_n:n\geq m\} \leq \sup\{s_n:n\geq N\}$.
			This means $\sup\{s_n:n\geq m\}\leq s+\epsilon \implies \lim_{n\ra\infty}(\sup\{s_n:n\geq m\})\leq s+\epsilon \implies \limsup_{m\ra\infty} s_m \leq s+\epsilon \implies \limsup_{m\ra\infty} s_m \leq s = \lim_{m\ra\infty} s_m$.
		\item Repeat the argument for (2).
			Then $\liminf_{n\ra\infty} s_n = \limsup_{n\ra\infty} s_n = \lim_{n\ra\infty} s_n$ -- ($*$).
	\end{enumerate}
	\say{$\Lra$} Suppose $(*)$ holds. We need to show $\lim_{n\ra\infty} s_n = \ul{\ul s}$.
	
	Let $\epsilon>0$ be given. $\limsup_{n\ra\infty}s_n = s \implies \lim_{k\ra\infty}(\sup\{s_n:n\geq k\}) = s \implies \exists K_1\in\mb N $ such that $|y_k-s|<\epsilon$ for all $k\geq K_1$.
	This implies $-\epsilon < y_k-s<\epsilon$ for all $k\geq K_1$, which implies $y_k < s+\epsilon$ for all $k\geq K_1 \implies \sup\{s_n:n\geq K\} < s+\epsilon$ for all $k\geq K_1 \implies s_n<s+\epsilon$ for all $n\geq K_1$ -- (3).

	Again, $\liminf_{n\ra\infty} s_n = s \implies \lim_{k\ra\infty}(\inf\{s_n:n\geq k\}) = s \implies \exists K_2\in\mb N$ such that $|z_k -s|<\epsilon$ for all $k\geq K_2$.
	This implies $-\epsilon < z_k - s< \epsilon$ for all $k\geq K_2 \implies z_k-s>-\epsilon$ or $s_k > s-\epsilon$ for all $k\geq K_2 \implies \inf\{s_n:n\geq k\} > s-\epsilon$ for all $k\geq K_2 \implies$ \ul{$s_n>s-\epsilon$ for all $n\geq K_2$} -- (4).
	For $K\geq \max\{K_1,K_2\}$, $s-\epsilon <s_n < s+\epsilon$ or $-\epsilon < s_n-s < \epsilon \implies s_n\ra s$.
\end{proof}

\begin{theorem}
	[Thm 3.20 book] Important examples - check!
\end{theorem}

\subsection{Series - of real numbers}

Let $\{a_n\}\subset\mb R$ be a sequence.
Define
\begin{align*}
	s_1 &:= a_1 \\
	s_2 &:= a_1 + a_2 \\
	s_3 &:= a_1 + a_2 + a_3 \\
	\vdots \\
	s_n &:= a_1 + a_2 + \dots + a_n
\end{align*}
- $n^\text{th}$ partial sum of ?
Then $\{s_n\}\subset\mb R$ is well defined.
If $s_n\ra s$ in $\mb R$, we say $\sum_{n=1}^\infty a_n = s$ and that $\sum_{n=1}^\infty a_n$ converges.
Otherwise $\sum_{n=1}^\infty a_n$ diverges.

\begin{recall}
	$\{s_n\}\subset\mb R$ Cauchy $\iff\{s_n\}\subset\mb R$ is convergent.
\end{recall}
\begin{theorem}
	$\sum_{n=1}^\infty a_n$ converges $\iff \forall\epsilon>0$, $\exists N\in\mb N$ such that $|s_n-s_{m-1}|<\epsilon$ for every $m\geq n>N$, where $s_n:=a_1+\dots+a_n$
	i.e., $\left|\sum_{k=1}^n a_k - \sum_{k=1}^{m-1} a_k\right|< \epsilon$
	i.e., $\left|\sum_{k=m}^n a_k\right| < \epsilon$ for all $n\geq m>N$.
\end{theorem}
\begin{note}
	Taking $m=n$, we get $|a_m|<\epsilon$ for all $m>N \implies a_m\ra 0$ as $m\ra\infty$ i.e., if $\sum a_n$ converges then $\lim_{n\ra\infty}a_n=0$. ($\implies$ if $\lim_{n\ra\infty}a_n\neq0$ then $\sum a_n$ diverges.)
\end{note}
\begin{example}
	$\sum\frac{1}{n}$ diverges and $\lim_{n\ra\infty}\frac{1}{n}=0$.
\end{example}

\begin{theorem}
	Let $a_n\geq 0$ for all $n\in\mb N$.
	Then $\sum_{n=1}^\infty a_n$ converges $\iff \{s_n\}$ is bounded.
\end{theorem}
\begin{proof}
	Proof follows from monotonic bounded sequence theorem since $s_n=a_1+\dots+a_n\leq a_1+\dots+a_{n+1}$ i.e., $s_n\leq s_{n+1}$ (monotonically increasing).
\end{proof}

\begin{theorem}
	[Comparison test] Cases:
	\begin{enumerate}
		\item[(a)] If $|a_n|\leq c_n$ for some $n\geq N$ for some $N\in\mb N$ and if $\sum_{n=1}^\infty c_n$ converges then $\sum_{n=1}^\infty a_n$ converges.
		\item[(b)] If $0\leq d_n\leq a_n$ for $n\geq N$ for some $N\in\mb N$ and if $\sum_{n=1}^\infty d_n$ diverges then $\sum_{n=1}^\infty a_n$ diverges.
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] Let $\epsilon>0$ be fixed.
			\ul{NTS}: $\exists N_0\in\mb N$ such that $\left|\sum_{k=m}^n a_k\right|<\epsilon$ for all $n\geq m>N_0$.
			Then $\sum_{n=1}^\infty c_n$ converges $\implies\exists N\in\mb N_0$ such that $\sum_{k=m}^n c_k = \left|\sum_{k=m}^n c_k\right|<\epsilon$ for all $n\geq m>N_0$.
			Given $a_n\leq|a_n|\leq c_n$ for $n\geq N$.
			Then $\left|\sum_{k=m}^n a_k\right|\os{\Delta}{\leq} \sum_{k=m}^n|a_k| \leq \sum_{k=m}^n c_k < \epsilon$ for $n\geq m>N_2 = \max\{N,N_0\}$.
			This implies $\sum_{k=1}^\infty a_k$ converges.
		\item[(b)] If $\sum a_n$ converges then by (a), since $0\leq d_n\leq a_n$, $\sum_{n=1}^\infty d_n$ converges, contradiction. Hence the proof.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	[Geometric series]
	Let $0\leq x<1$. Then $\sum_{n=0}^\infty x^n = \frac{1}{1-x}$. If $x\geq 1$ then $\sum_{n=0}^\infty x^n$ diverges.
\end{theorem}
\begin{proof}
	Let $x\neq 1$. Then $\sum_{k=0}^n x^k = 1+x+x^2+\dots+x^n \implies (1-x)\sum_{k=0}^n x^k = \sum_{k=0}^n x^k -\sum_{k=1}^{n+1}x^k = 1-x^{n+1}$.
	Then $\lim_{n\ra\infty} \frac{1-x^{n+1}}{1-x} = \frac{1}{1-x}\lim_{n\ra\infty}(1-x^{n+1}) = \ul{\frac{1}{1-x} \text{ if } |x|<1 \text{ i.e., }0\leq x<1}$.
\end{proof}

\begin{theorem}
	Suppose $a_n\geq 0$ and $a_n\geq a_{n+1}$ for all $n\in\mb N$.
	Then $\sum_n a_n$ converges $\iff\sum_k 2^ka_{2^k}$ converges.
	\label{thm-3-27}
\end{theorem}
\begin{proof}
	Let $s_n = a_1+a_2+\dots+a_n$ and $t_n = a_1 + 2a_2 + 2^2a_{2^2} + \dots + 2^ka_{2^k}$.
	\ul{Claim}: $\{s_n\}$ is bounded $\iff \{t_k\}$ is bounded.

	\ul{Case}: $n<2^k$.
	\begin{align*}
		s_n &\leq a_1 + a_2 + \os{\leq a_2}{a_3} + a_4 + \os{\leq a_4}{a_5} + \os{\leq a_4}{a_6} + \os{\leq a_4}{a_7} + a_8 + \os{=a_n}{\dots} + a_{2^k} + \os{\leq a_{2^k}}{\dots} + a_{2^{k+1}-1} + \dots + a_n \\
			&\leq a_1 + 2a_2 + 2^2a_{2^2} + \dots + 2^ka_{2^k} = t_k \implies \ul{s_n\leq t_k}.
	\end{align*}
	
	\ul{Case}: $n>2^k$.
	\begin{align*}
		s_n &= a_1 + a_2 + \os{\geq a_4}{a_3} + a_4 + \os{\geq a_8}{a_5} + \os{\geq a_8}{a_6} + \os{\geq a_8}{a_7} + \os{\geq a_8}{a_8} + \dots + a_{2^{k-1}} + \dots + a_{2^k} + \dots + a_n \\
			&\geq \frac{1}{2}a_1 + a_2 + 2a_4 + 4a_8 + \dots + 2^{k-1}a_{2^k} \implies 2s_n \geq a_1 + 2a_2 + 2^2a_{2^2} + 2^3a_{2^3} + \dots + 2^ka_{2^k} = t_k.
	\end{align*}
	This implies \ul{$s_n\geq \frac{t_k}{2}$ for $n>2^k$} $\implies \{s_n\}$ is bounded $\iff\{t_k\}$ is bounded.
\end{proof}

\begin{recall}
	Suppose $a_n\geq 0$ and $a_n\geq a_{n+1}$ for all $n$.
	Then $\sum_n a_n$ converges $\iff \sum2^k a_{2^k}$ converges.
\end{recall}
\begin{theorem}
	\ul{$p$-series} $\sum_{n=1}^\infty\frac{1}{n^p}$ converges if $p>1$, and diverges if $p\leq 1$.
	\label{thm-3-28}
\end{theorem}
\begin{proof}
	If $p\leq 0$, then $\lim_{n\ra\infty}\frac{1}{n^p}\neq 0$, $\sum \frac{1}{n^p}$ diverges.
	If $p>0$, then $\frac{1}{n}\geq\frac{1}{n+1} \implies \frac{1}{n^p}\geq\frac{1}{(n+1)^p}$ by monotonicity of power $p \implies \set{\frac{1}{n^p}}$ is monotonically decreasing, and $\frac{1}{n^p}\geq 0$ for all $n$ (Theorem \ref{thm-3-27} can be applied).
	Note that $\sum_k 2^k\frac{1}{(2^k)^p} = \sum_k 2^{k(1-p)} = \sum_k [2^{(1-p)}]^k$.
	This series converges (geometric) if $1-p<0$ i.e., $p>1$, and diverges if $1-p\geq0$.
\end{proof}

\begin{theorem}
	[$\log$ $p$-series] $\sum_{n=1}^\infty\frac{1}{n(\log n)^p}$ converges if $p>1$ and diverges if $p\leq 1$.
\end{theorem}
\begin{proof}
	We will use Theorem \ref{thm-3-27}. Clearly $n(\log n)^p\geq 0$ for $n\geq 2$.
	Assume $\log n$ is monotonically increasing.
	Then using the monotonicity of power $p$, $\frac{1}{\log n}\geq\frac{1}{(\log{(n+1)})^p\cdot(n+1)}$ for all $n\geq 2$.
	We can apply Therem \ref{thm-3-27}.
	Then $\sum_k 2^k\cdot\frac{1}{2^k(\log{2^k})^p} = \sum_k \frac{1}{(k\log2)^p} = \frac{1}{(\log 2)^p}\sum_k\frac{1}{k^p}$ is $p$-series that converges if $p>1$ and diverges if $p\leq 1$ by Theorem \ref{thm-3-28}.
\end{proof}

\newpage
\begin{definition}
	[$e$] $e:=\sum_{n=0}^\infty\frac{1}{n!}$ ($0! = 1$)
\end{definition}
We will justify that the series converges.
We will show: $\set{s_n}$ is monotonically increasing and bounded above.
$s_n:= 1+1+\frac{1}{2!} + \frac{1}{3!} + \dots + \frac{1}{n!} \implies s_n\leq s_{n+1}$ for all $n$.
\begin{align*}
	s_n &= 1+1+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}+\dots+\frac{1}{n!} \\
		&= 1+1+\frac{1}{2}+\ub{<\frac{1}{2^2}}{\frac{1}{2\cdot3}}+\ub{<\frac{1}{2^3}}{\frac{1}{2\cdot3\cdot4}}+\dots+\ub{<\frac{1}{2^{n-1}}}{\frac{1}{2\cdot3\cdot\dots\cdot(n-1)\cdot n}} \\
		&< 1+1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\dots+\frac{1}{2^{n-1}} \\
		&= 1+\sum_{k=0}^{n-1}\frac{1}{2^k} < 1 + \sum_{k=1}^\infty\frac{1}{2^k} = 1 + \frac{1}{1-\frac{1}{2}} = 3
\end{align*}
implies $\set{s_n}$ is bounded above by 3 for all $n$ or $s_n<3$ for all $n$.
Therefore $\sum_{n=0}^\infty\frac{1}{n!}$ converges.

\begin{theorem}
	$\lim_{n\ra\infty}(1+\frac{1}{n})^n = e$.
\end{theorem}
\begin{proof}
	Skip.
\end{proof}

\begin{theorem}
	$e\in\mb R\bs\mb Q$, where $e = \sum_{n=0}^\infty\frac{1}{n!}$.
\end{theorem}
\begin{proof}
	Suppose by contradiction that $e\in\mb Q$. Then $e = \frac{p}{q}$, where $p,q\in\mb N$ (since $e>0$).
	Consider 
	\begin{align*}
		e-s_n &= \sum_{k=0}^\infty\frac{1}{k!}-\sum_{k=0}^n\frac{1}{k!} 
			  = \sum_{k=n+1}^\infty\frac{1}{k!} \\
			  &= \frac{1}{(n+1)!}+\frac{1}{(n+2)!}+\frac{1}{(n+3)!} + \dots \\
			  &= \frac{1}{(n+1)!}\left[1+\frac{1}{n+2}+\frac{1}{(n+2)(n+3)}+\dots\right] \\
			  &< \frac{1}{(n+1)!}\left[1+\frac{1}{n+1}+\frac{1}{(n+1)^2}+\dots\right] \\
			  &= \frac{1}{(n+1)!}\sum_{k=0}^\infty\frac{1}{(n+1)^k} = \frac{1}{(n+1)!}\sum_{k=0}^\infty\left(\frac{1}{n+1}\right)^k \\
			  &= \frac{1}{(n+1)!}\cdot\frac{1}{1-\frac{1}{n+1}} = \frac{1}{(n+1)n!}\cdot\frac{n+1}{n} = \frac{1}{n!n}
	\end{align*}
	i.e., $e-s_n<\frac{1}{n!n}$ for all $n\geq 1$.
	Therefore $0<e-s_q<\frac{1}{q!q}$. This implies $0<q!(e-s_q)<\frac{1}{q} \leq 1$ (since $q\geq 1$).
	Since $e = \frac pq$, $p=eq\in\mb N$, so $q!e\in\mb N$.
	Now $q!s_q = q!(1+1+\frac{1}{2\cdot1}+\frac{1}{3\cdot2\cdot1}+\dots+\frac{1}{q!})\in\mb N$.
	Therefore, $q!(e-s_q)\in\mb N$, which is a contradiction since $0<q!(e-s_q)<\frac{1}{q}\leq 1$.
	Therefore $e\in\mb R\bs\mb Q$.
\end{proof}

\subsection{The Root and Ratio test for Series}

\begin{theorem}
	[Root test] Consider $\sum_n a_n$ and define $\alpha = \limsup_{n\ra\infty} \nrt{n}{|a_n|}$.
	Then
	\begin{enumerate}
		\item[(a)] $\sum_n a_n$ converges if $\alpha<1$.
		\item[(b)] $\sum_n a_n$ diverges if $\alpha>1$.
		\item[(c)] Test is inconclusive if $\alpha = 1$.
	\end{enumerate}
\end{theorem}
\newpage
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] Suppose 
			\begin{align*}
				\alpha &= \limsup_{n\ra\infty} \nrt{n}{|a_n|}<1 \\
					   &= \lim_{m\ra\infty}\left(\sup\setc{\nrt{n}{|a_n|}}{n\geq m} \right) < 1
			\end{align*}
			Let $\epsilon>0$ such that $\alpha < \alpha +\epsilon < 1$.
			Then $\exists N\in\mb N$ such that $\sup\setc{\nrt{n}{|a_n|}}{m\geq N} < \alpha+\epsilon \implies \nrt{n}{|a_n|}<\alpha+\epsilon$ for all $n\geq N$.
			This implies $|a_n|<(\alpha+\epsilon)^n$ for all $n\geq N$.
			Since $0<\alpha+\epsilon<1$, $\sum_{n\geq N}(\alpha+\epsilon)^n$ converges as a geometric series.
			By comparison test, $\sum_n a_n$ converges.
		\item[(b)] Suppose $\alpha = \limsup_{n\ra\infty} \nrt{n}{|a_n|} >1$.
			Then $\alpha = \sup\setc{s\in\mb R}{\exists \nrt{n_k}{|a_{n_k}|}\ra s}$.
			This implies $\exists$ a subsequence $\set{\nrt{n_k}{|a_{n_k}|}}$ such that $\nrt{n_k}{|a_{n_k}|}\ra \alpha > 1$.
			Infinitely many terms of the subsequence, and hence of sequence $\set{\nrt{n}{|a_n|}}$ is greater than 1.
			So $\lim_{n\ra\infty}\nrt{n}{|a_n|}\neq 0$ and hence $\lim_{n\ra\infty} a_n\neq 0$.
			So $\sum_na_n$ diverges.
		\item[(c)] Consider (i) $\sum\frac1n$ (diverges) and (ii) $\sum\frac1{n^2}$ (converges).
			\begin{enumerate}
				\item[(i)] $\displaystyle\lim_{n\ra\infty}n^\frac{1}{n} = 1\implies \lim_{n\ra\infty} \frac{1}{n^\frac{1}{n}} = 1$.
				\item[(ii)] $\displaystyle\lim_{n\ra\infty}\frac{1}{n^\frac{2}{n}} = \lim_{n\ra\infty} \frac{1}{(n^\frac{1}{n})^2} = 1$.
			\end{enumerate}
	\end{enumerate}
	Done.
\end{proof}

\begin{example}
	Consider $0,0,\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{3}{8},\frac{7}{8},\frac{7}{16},\frac{15}{16},\frac{15}{32},\frac{31}{32},\dots$.
	Then $\sup\setc{a_n}{n\geq 1} = 1$, $\inf\setc{a_n}{n\geq 3}=\frac{1}{4}$.
\end{example}

\begin{example}
	Look at Example 3.34 in book: $\liminf |a_n|^\frac{1}{n}$ and $\limsup |a_n|^\frac{1}{n}$.
\end{example}

\begin{theorem}
	[Ratio test] Consider $\sum_n a_n$ with $a_n\neq 0$ for all $n$ (enough for sufficiently large $n$). Then
	\begin{enumerate}
		\item[(a)] $\sum a_n$ converges if $\displaystyle\limsup_{n\ra\infty} \left|\frac{a_{n+1}}{a_n}\right|<1$.
		\item[(b)] $\sum a_n$ diverges if $\displaystyle\left| \frac{a_{n+1}}{a_n}\right| \geq 1$ for $n\geq N \la$ fixed $N\in\mb N$.
		\item[(*)] If $\displaystyle\liminf_{n\ra\infty}\left|\frac{a_{n+1}}{a_n}\right| \leq 1 \leq \limsup_{n\ra\infty}\left|\frac{a_{n+1}}{a_n}\right|$, the test gives no information.
	\end{enumerate}
	\label{thm-3-34}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item[(a)] Let $\displaystyle a^*:=\limsup_{n\ra\infty}\left|\frac{a_{n+1}}{a_n}\right|<1$.
			Let $\epsilon>0$ be such that $a^*<a^*+\epsilon<1$.
			\ul{NTS}: $\exists$ a convergent series $\sum_n b_n$ such that $|a_n|\leq b_n$ for $n$ large.
			Since $a^*<a^S+\epsilon<1$, $\exists N\in\mb N$ such that $\left|\frac{a_{n+1}}{a_n}\right|<a^*+\epsilon$ for $n\geq N$.
			In particular, $|a_{N+1}|<|a_N|(a^*+\epsilon) \implies |a_{N+2}|<|a_{N+1}|(a^*+\epsilon) < |a_N|(a^*+\epsilon)^2$ and further $$|a_{N+k}|<|a_N|(a^*+\epsilon)^k \implies |a_n|<|a_N|(a^*+\epsilon)^{n-N} = \ob{\text{fixed}}{|a_N|(a^*+\epsilon)^{-N}}(a^*+\epsilon)^n.$$
			But $\sum(a^*+\epsilon)^n$ is a convergent geometric series since \ul{$a^*+\epsilon<1$}, so by comparison test $\sum a_n$ converges.
		\item[(b)] $\left|\frac{a_{n+1}}{a_n}\right|\geq 1$ for $n\geq N$ implies that $|a_{N+k}|\geq |a_N|\neq 0$ for all $\displaystyle k \implies \lim_{k\ra\infty} |a_{N+k}|\neq 0 \implies \lim_{n\ra\infty}a_n\neq~0 \implies \sum a_n$ diverges.
\end{enumerate}
\end{proof}

\begin{theorem}
	$\sum c_n$ with $c_n\geq 0$ for all $n$ and $c_n\neq 0$ for large $n$. Then
	$$\liminf_{n\ra\infty}\frac{c_{n+1}}{c_n}\leq \liminf_{n\ra\infty}\nrt{n}{c_n}\leq \limsup_{n\ra\infty}\nrt{n}{c_n},$$
	$$\text{and}\qquad\limsup_{n\ra\infty}\nrt{n}{c_n}\leq\limsup_{n\ra\infty}\frac{c_{n+1}}{c_n}.$$
	%\label{thm-3-37}
\end{theorem}
\begin{remark}
	Root test is more powerful than ratio test:
	$$1+1+\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8}+\dots$$
	So $\limsup_{n}\nrt{n}{a_n} = \frac{1}{2} < 1 \implies$ converges.
	Then $\limsup_{n\ra\infty}\frac{a_{n+1}}{a_n}=1$ (Test is inconclusive).
\end{remark}

\subsection{Power series}

\begin{definition}
	$\displaystyle\sum_{n=0}^\infty c_nz^n;\ c_n\in\mb R, z\in\mb C.$
\end{definition}

\ul{\ul{Q}}: Under what assumptions on $c_n$ and \say{$z$ itself} the series converges/diverges?

\begin{theorem}
	Consider $\sum c_nz^n$. Define $\alpha:=\limsup_{n\ra\infty}\nrt{n}{|c_n|}$ and $R:=\frac{1}{\alpha}$.
	Then $\sum c_nz^n$ converges if $|z|<R$ and diverges if $|z|>R$.
\end{theorem}
\begin{proof}
	Let $a_n:=c_nz^n$. Then $\displaystyle\limsup_{n\ra\infty}\nrt{n}{|a_n|} = \limsup_{n\ra\infty}\nrt{n}{|c_n|\cdot|z|^n} = |z|\ub{\alpha}{\limsup_{n\ra\infty} \nrt{n}{|c_n|}} = |z|\cdot\alpha$.
	By root test, $\sum c_nz^n$ converges if $|z|\cdot\alpha<1$ or $|z|<\frac{1}{]\alpha} = R$ and diverges if $|z|>\frac{1}{\alpha} = R$.
\end{proof}
\begin{example}
	Consider $\sum_n 1\cdot x^n$ with $1\ra c_n$. Then $\alpha = \lim_{n\ra\infty}(1) = 1$.
	Converges if $|x|<\frac{1}{\alpha} = 1 = R$, diverges if $|x|>\frac{1}{\alpha}=1=R$.
\end{example}
\begin{recall}
	$\lim_{n\ra\infty} \nrt{n}{n} = 1$.
\end{recall}
\begin{example}
	Consider $\displaystyle\sum\frac{2^n}{n^2}\cdot x^n$. Then $\displaystyle\alpha = \lim_{n\ra\infty} \nrt{n}{\frac{2^n}{n^2}} = \lim_{n\ra\infty}\frac{2}{n^{\frac{2}{n}}} = 2 \implies \ul{R = \frac{1}{2}}$.
\end{example}

\subsection{Series with product}

\begin{theorem}
	Let $A_n:=\sum_{k=0}^n a_k$ and define $A_{-1}=0$. Suppose
	\begin{enumerate}
		\item[(a)] $\set{A_n}$ is bounded
		\item[(b)] $b_0\geq b_1\geq b_2\geq \dots$
		\item[(c)] $\lim_{n\ra\infty} b_n = 0$.
	\end{enumerate}
	Then $\sum a_nb_m$ converges.
	\label{thm-3-42}
\end{theorem}

\begin{proof}
	Let $\epsilon>0$ be given. NTS: $\exists N\in\mb N$ such that $|\sum_{k=m}^n a_kb_k|<\epsilon$ for $n\geq m>N$.
	\ul{We claim}: For $0\leq p\leq q$, $\sum_{k=p}^q a_kb_k = \sum_{k=p}^{q-1} A_k(b_k-b_{k+1}) + A_qb_q - A_{p-1}b_p$ --- (1).
	By (a), $\exists M>0$ such that $|A_n|\leq M$ for all $n\in\mb N$.
	By (c), $\exists N\in\mb N$ such that $|b_n|<\dots$ for $n\geq N$.
	Then using (1), 
	\begin{align*}
		\left|\sum_{p=m}^n a_kb_k\right| &= \left|\sum_{k=m}^{n-1} A_k(b_k-b_{k-1}) + A_nb_n - A_{m-1}b_m\right| \\
										 &\os{\Delta}{\leq} \left|\sum_{k=m}^{n-1} A_k(\ob{\geq0}{b_k-b_{k+1}})\right| + |A_n|\cdot|b_n| + |A_{m-1}|\cdot|b_m| \\
										 &\leq M\sum_{k=m}^{n-1} (b_k-b_{k+1}) + M|b_n| + M|b_m|.
	\end{align*}
	Note that (b) and (c) imply $b_n\geq 0$ for all $n\in\mb N$. For $n\geq m\geq N$,
	$$M\Bigg(\ub{b_m-b_{m+1}+b_{m+1}+\dots+b_{n-1}-b_n}{\sum_{k=m}^{n-1}(b_k-b_{k+1})}+b_n+b_m\Bigg) = 2Mb_m <\epsilon$$ 
	This implies $\sum a_k b_k$ converges.
\end{proof}

\ul{Test 3}: Tuesday, Nov. 28
Ch 2: - connected sets 19-21.
\ul{Ch 3}: 1-10, 11 (graduate students), 20-22, 23 (graduate students).

\begin{recall}
	-- proof is complete if we show $\sum_{k=m}^n a_kb_k = \sum_{k=m}^{n-1} A_k(b_k-b_{k+1}) + A_n b_n - A_{m-1}b_m$ --- (1), where $A_k = a_0+a_1+\dots+a_k$, $A_{k-1} = a_0+\dots+a_{k-1}$.
\end{recall}
\begin{proof}
	Observe that $a_k=A_k-A_{k-1}$. Then left hand side of (1) as:
	\begin{align*}
		\sum_{k=m}^n(A_k - A_{k-1})b_k &= \sum_{k=m}^n A_kb_k - \sum_{k=m}^n A_{k-1} b_k
		= \sum_{k=m}^n A_kb_k - \sum_{k=m-1}^{n-1} A_k b_{k+1} \\
									   &= \sum_{k=m}^{n-1} A_kb_k - \sum_{k=m}^{n-1} A_k b_{k+1} + A_n b_n - A_{m-1}b_m \\
									   &= \sum_{k=m}^{n-1} A_k(b_k-b_{k+1})+A_nb_n - A_{m-1} b_m = RHS
	\end{align*}
	Done.
\end{proof}

\begin{theorem}
	[Alternating series test]
	Consider $\sum_n c_n$. Suppose
	\begin{enumerate}
		\item[(a)] $|c_1|\geq |c_2|\geq |c_3| \geq \dots$.
		\item[(b)] $c_{2m-1}\geq 0$, $c_{2m}\leq 0$ for all $m\in\mb N$.
		\item[(c)] $\lim_{n\ra\infty} c_n = 0$.
	\end{enumerate}
	Then $\sum c_n$ converges.
	\label{thm-3-43}
\end{theorem}
\begin{note}
	$\sum_{n=1}^\infty c_n = c_1+c_2+c_3+c_4+\dots = |c_1|+(-1)|c_2|+|c_3|+(-1)|c_4| + \dots = \sum_{n=1}^\infty (-1)^n |c_n|$.
\end{note}
\begin{proof}
	We will use Theorem \ref{thm-3-42}.
	Let $A_n = \sum_{k=0}^n (-1)^{k+1}$. Then $|A_n|\leq 1$ for all $n$.
	Let $b_n = |c_n|$. Then (a) and (c) satisfy assumptions (b) and (c) of Theorem \ref{thm-3-42}.
	Hence $\sum(-1)^{n+1}|c_n| = \sum c_n$ converges.
\end{proof}
\begin{example}
	$\sum_{n=1}^\infty (-1)^{n+1}\frac{1}{n}$ -- converges.
\end{example}
\begin{example}
	$\sum_{n=1}^\infty (-1)^{n+1} \frac{1}{n^p}$, where $\ul{o>0}$, converges.
\end{example}

\begin{theorem}
	Suppose $z\in\mb C$ and
	\begin{enumerate}
		\item[(a)] $R=1$ for $\sum c_n z^n$.
		\item[(b)] $c_0\geq c_1\geq c_2\geq\dots$.
		\item[(c)] $\lim_{n\ra\infty} c_n = 0$.
	\end{enumerate}
	Then $\sum c_n z^n$ converges at every point on $|z|=1$ except possibly at $z=1$.
\end{theorem}
\begin{remark}
	Converges in $|z|<1$, diverges on $|z|>1$, \ul{$|z|=1$}.
\end{remark}
\begin{proof}
	We will use Theorem \ref{thm-3-42}. Hypotheses (b) and (c) satisfy hypotheses (b) and (c) of Theorem \ref{thm-3-42}.
	We only need to check that $A_n:=\sum_{k=0}^n z^k$ is bounded for all $n$.
	\begin{align*}
		|A_n| &= \left| \sum_{k=0}^n z^k\right| = \left| \frac{1-z^{n+1}}{1-z}\right| \leq \frac{|1-z^{n+1}|}{|1-z|} \\
			  &\os{\Delta}{\leq} \frac{1+|z|^{n+1}}{|1-z|} = \frac{2}{|1-z|},
	\end{align*}
	which implies $\set{A_m}$ is bounded for all $n$ on $|z|=1$ except at $z=1$.
	Therefore $\sum c_n z^n$ converges on $|z|=1$ (except at $z=1$, \ul{essential singularity}).
\end{proof}

\begin{definition}
	[Absolute convergence]
	$\sum a_n$ converges absolutely if $\sum |a_n|$ converges.
\end{definition}
\begin{example}
	$\sum (-1)^{n+1}\frac 1n$ does not converge absolutely, since $\sum |(-1)^{n+1}\frac{1}{n}| = \sum \frac 1n$ diverges.
	\label{example-convergence}
\end{example}
\begin{example}
	$\sum (-1)^{n+1}\frac{1}{n^p}$ ($p>1$) converges absolutely since $\sum \frac{1}{n^p}$ converges for $p>1$.
\end{example}
\begin{definition}
	[non-absolutely convergent or conditionally convergent]
	$\sum a_n$ converges conditionally if $\sum a_n$ converges, but $\sum |a_n|$ diverges.
\end{definition}
See example \ref{example-convergence}.
\begin{theorem}
	If $\sum a_n$ converges absolutely, then $\sum a_n$ converges.
\end{theorem}
\begin{proof}
	[Proof. (Assume $a_n\in\mb R$)]
	Then $a_n\leq |a_n|$ and $\sum |a_n|$ converges $\implies \sum a_n$ converges.
\end{proof}
\begin{proof}
	[Proof. (Assume $a_n\notin\mb R$ but $a_n\in\mb C$)]
	Let $\epsilon>0$ be given.
	\ul{NTS}: $\exists N\in\mb N$ such that $m\geq n>N$ implies $\left|\sum_{k=n}^m a_k \right| <\epsilon$.
	Then $\sum |a_n|$ converges $\implies \exists N_1\in\mb N$ such that $m\geq n>N_1$ implies $\left| \sum_{k=n}^m |a_k| \right| <\epsilon$.
	Then for $m\geq n>N_1$, $\left|\sum_{k=n}^m a_k\right| \os{\Delta}{\leq} \sum_{k=n}^m |a_k| < \epsilon$.
	Therefore $\sum a_k$ converges.
\end{proof}

\begin{theorem}
	[Sum and constant multiple]
	Suppose $\sum a_n = A$, $\sum b_n = B$. Then $\sum(a_n+b_n) = A+B$ and $\sum c\cdot a_n = cA$ for some fixed $c \la$ \ul{constant}.
\end{theorem}
\begin{proof}
	Let $\set{A_n}$ and $\set{B_n}$ be sequence of partial sums $\sum a_n$ and $\sum b_n$.
	Then $A_n\ra A$ and $B_n\ra B$. Then (using sequence results) $A_n+B_n\ra A+B$ and $c\cdot A_n = cA$.
\end{proof}
\begin{recall}
	[Cauchy product] $\sum a_n$ and $\sum b_n$.
	Let $c_n = \sum_{k=0}^n a_k b_{n-k} = a_0 b_n + a_1 b_{n-1} + a_2 b_{n-2}+ \dots + a_n b_0$.
\end{recall}
\begin{theorem}
	Suppose
	\begin{enumerate}
		\item[(a)] $\sum a_n$ converges absolutely
		\item[(b)] $\sum a_n = A$
		\item[(c)] $\sum b_n = B$
	\end{enumerate}
	Then $\sum_{n=0}^\infty c_n = AB$, $c_n = \sum_{k=0}^n a_k b_{n-k}$.
\end{theorem}

\begin{example}
	[Ch 3, \#7] $\sum a_n$ with $a_n\geq 0$ converges $\implies \sum \frac{\sqrt{a_n}}{n}$ converges.
	\ul{Hint}: Use Cauchy-Schwartz inequality $\left| \sum_{n=1}^m a_n\conj b_n \right| \leq \left( \sum |a_n|^2\right)^\frac{1}{2} \left(\sum |b_n|^2 \right)^\frac{1}{2}$.
	Other techniques can also work.
\end{example}

\end{document}