# Math 521 - All definitions and theorems
## Relations
- A relation on $A$ is a subset of $A \times A$
Example: $x \leq y$ on $\{1, 2, 3\}$ means $\{(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)\}$
- An order on $S$ is a relation such that:
- $\forall x \in S: x \leq x$
- $\begin{cases} x \leq y \\ y \leq x \end{cases} \Rightarrow x=y$
- $\begin{cases} x \leq y \\ y \leq z \end{cases} \Rightarrow x \leq z$
- $\forall x,y \in S: x \leq y \text{ or } y \leq x$
- An ordered set is a set $S$ with an order.
If $T \subset S$ and $(S, \leq)$ is an ordered set, $(T, \leq)$ is an ordered set
## Bounds
- $\max E$ exists $\Rightarrow \sup E = \max E$
- An ordered set $S$ has the least-upper-bound property (LUBP) if the following is true:
$\begin{cases} E \subset S \\ E \ne \emptyset \\ E \text{ is bounded above} \end{cases} \Rightarrow \sup E$ exists in $S$
- $S$ has LUBP $\Leftrightarrow S$ has GLBP
- $\mathbb{R}$ is an ordered fields. $\mathbb{Q}$ is a subfield of $\mathbb{R}$
- Archimedian property: $\forall x \in \mathbb{R}, y \in \mathbb{R}, x > 0: \exists n \in \mathbb{N}: nx > y$
- $\mathbb{Q}$, $\mathbb{I}$ are dense in $\mathbb{R}$
## Cauchy-Schwarz inequality
- In $\mathbb{C}$: $\Bigg | \sum_{j=1}^n a_j\bar{b_j} \Bigg| \leq \Bigg(\sum_{j=1}^n |a_j|^2 \Bigg)\Bigg(\sum_{j=1}^n |b_j|^2 \Bigg)$
- In $\mathbb{R}^k$: $|\vec{x} \cdot \vec{y}| \leq |\vec{x}||\vec{y}|$
## Triangle inequality
- In $\mathbb{C}$: $|z| + |w| \leq |z+w|$
- In $\mathbb{R}^k$: $|\vec{x}| + |\vec{y}| \leq |\vec{x}+\vec{y}|$
## Cardinality
- Let $A, B$ be two sets. $card(A) = card(B) \Leftrightarrow \exists f: A \rightarrow B$ such that $f$ is a bijective function.
- If $\exists f: A \rightarrow B$ injective function, $card(A) \leq card(B)$
- If $\exists f: A \rightarrow B$ surjective function, $card(A) \geq card(B)$
- $card(A) = card(B) \Leftrightarrow A \sim B$
Let $J_n = \{1, 2, 3, ..., n\}$
- $A$ is finite $\Rightarrow A \sim J_n$
- $A$ is countable $\Rightarrow A \sim \mathbb{N}$
- $A$ is uncountable if $A$ is not finite and $A$ is not countable.
- $A$ is at most countable if $A$ is finite or $A$ is countable.

$\mathbb{N}, \mathbb{Z}, \mathbb{Q}$ are countable.
Every infinite subset of countable set is countable.

- Let $(E_n)_{n=1}^\infty$ be a sequence of countable sets. Then $\cup_{n=1}^\infty E_n$ is countable.
- $A$ is countable $\Rightarrow A^k$ is countable.
## Metric spaces
Let $X$ be a set. A function $d: X^2 \rightarrow \mathbb{R}$ is a distance function if for all $x,y,z \in X$:
- $d(x,y) \geq 0$
- $d(x,y) = 0 \Leftrightarrow x = y$
- $d(x,y) = d(y,x)$
- $d(x,y) + d(y,z) \geq d(x,z)$

$(X,d)$ is called a metric space

## Open, closed
$B(x,r) = \{y \in X: d(x,y) < r\}$
$\bar{B}(x,r) = \{y \in X: d(x,y) \leq r\}$
$U$ is open $\Leftrightarrow \forall p \in U: \exists r > 0: \forall q, d(q,p) < r: q \in U$
The set of interior point of $U$ is $U^o$
$p$ is an accumulation point of $U$ if $\forall r > 0: \exists q \in B(p,r): q \in U \setminus \{p\}$
$U'$ is the set of accumulation point of $U$
$U$ is closed $\Leftrightarrow U' \subset U$

- If $p$ is an accumulation point of $E$, then $B(p,r)$ contains infinitely many points of $E$
- A finite set has no accumulation point.
- $X$ and $\emptyset$ are both open and closed.
- $E$ is open $\Leftrightarrow E^c$ is closed.
### Union / Intersection
- An arbitrary union of open sets is open.
- An arbitrary intersection of closed sets is closed.
- A finite intersection of open sets is open.
- A finite union of closed sets is closed.

### Closure
$\bar{E} = E \cup E'$
$\bar{E}$ is closed.
$\bar{E} = E \Leftrightarrow E$ is closed.
If $F \subset X$ is closed and $E \subset F$, then $\bar{E} \subset F$

### Bounded, dense
- $E$ is bounded if $\exists x \in X, r > 0: E \subset B(x,r)$
- $E$ is dense if $\bar{E} = X$

### Relative openness
$(X,d)$ metric space. $Y \subset X \Rightarrow (Y,d)$ metric space.
$U$ is open in $(Y,d) \Leftrightarrow E = Y \cap U$ for some $U$ open in $(X,d)$

## Compactness
Let $(X,d)$ be a metric space:
- A collection of open set $\{U_{\alpha}\}_\alpha$ is an open cover for $E$ is $E \in \cup_{\alpha} U_{\alpha}$
- $K$ is compact if for every open cover $\{U_\alpha\}_\alpha$ for $K$, $\exists \alpha_1, \alpha_2, ..., \alpha_n: K \subset \cup_{i=1}^n U_{\alpha_i}$

Every finite set is compact.
$Y \subset X$. $K$ is compact in $X \Leftrightarrow K$ is compact in $Y$.
$K$ is compact $\Rightarrow K$ is closed.
$\begin{cases}
K \text{ is compact} \\
F \subset K \\
F \text{ is closed in } X
\end{cases} \Rightarrow F \text{ is compact}$
$\begin{cases}
K \text{ is compact} \\
F \text{ is closed}
\end{cases} \Rightarrow K \cap F \text{ is compact}$
$K$ is compact $\Rightarrow K$ is bounded
$K$ is compact $\Leftrightarrow \forall F \subset K, F \text{ infinite}: \exists p \in K: p \text{ is an accumulation point of } F$

## Compactness in $(\mathbb{R}^k, d)$
Let $k \in \mathbb{N}$. If $\{I_n\}_{n \in \mathbb{N}}$ a sequence of $k$-cells such that $I_{n+1} \subset I_n$, then $\cap_{n=1}^\infty I_n \ne \emptyset$

Every $k$-cell is compact.

In $(\mathbb{R}^k, d)$
$\begin{cases}
K \text{ is closed} \\
K \text{ is bounded}
\end{cases} \Leftrightarrow K \text{ is compact}$

$E \subset \mathbb{R}^k$ is bounded and infinite.
Then $\exists x_0 \in \mathbb{R}^k: x_0 \in E'$

## Perfect sets
Let $(X,d)$ be a metric space. A set $E \subset X$ is perfect if $E = E'$ ($E$ is closed and does not have any isolated points)

Non-empty perfect sets in $(\mathbb{R}^k, d_{eucl})$ are uncountable

Let $(X,d)$ be a metric space. Let $\{K_{\alpha}\}_{\alpha \in A}$ be a collection of compact sets $K_\alpha \subset X$ for all $\alpha \in A$ such that $\cap_{\alpha \in B} K_{\alpha} \ne \emptyset$ for all finite set $B \subset A$.
Then $\cap_{\alpha \in A} K_{\alpha} \ne \emptyset$

Let $(X,d)$ be a metric space. Let $(K_n)_{n \in \mathbb{N}}$ be a sequence of compact sets in $(X,d)$ such that $K_{n+1} \subset K_{n}$ for all $n \in \mathbb{N}$ and $K_n \ne \emptyset$ for all $n \in N$
Then $\cap_{n \in \mathbb{N}} K_n \ne \emptyset$

$[a,b]$ is uncountable. Moreover, $\mathbb{R}$ is uncountable.

## Convergence
$p_n \rightarrow p \Leftrightarrow \begin{cases}
p \in X \\
\forall \epsilon > 0: \exists N \in \mathbb{N}: \forall n \geq N: d(p_n, p) < \epsilon
\end{cases}$
Note: $(\frac{1}{n})_{n \in \mathbb{N}}$ converges in $\mathbb{R}$, but diverges in $(0,2)$

The limit is unique.
$(p_n)$ converges $\Rightarrow \{p_n\}$ is bounded
$p_n \rightarrow p \in X \Leftrightarrow \forall r > 0: B(p,r)$ contains all but finitely many points $p_n$

Let $(X,d)$ be a metric space. $(p_n) \rightarrow p \in X$
- $(\{p_n\})' \subset \{p\}$
- $(\{p_n\})' = \emptyset \Leftrightarrow p_n = p$ for all but finitely many $n \in \mathbb{N}$

Let $(X,d)$ be a metric space. $E \subset X$. Then
$p \in E' \Leftrightarrow \exists (p_n)_{n \in \mathbb{N}} \text{ in } E \setminus \{p\}: p_n \rightarrow p$

## Subsequence
Given $(p_n)_{n \in \mathbb{N}}$, consider $(n_k)_{k \in \mathbb{N}}$ of $\mathbb{N}$ such that $n_1 < n_2 < ...$
Then $(p_{n_k})_{k \in \mathbb{N}}$ is a subsequence of $(p_n)_{n \in \mathbb{N}}$

Let $(X,d)$ be a metric space.
$p_n \rightarrow p \in X \Leftrightarrow$ every subsequence $(p_{n_k}) \rightarrow p$

Let $(X,d)$ be a metric space. $(p_n)$ be a sequence.
$p \in (\{p_n\})' \Rightarrow \exists$ a subsequence that converges to $p$

Let $(X,d)$ be a compact metric space.
If $(p_n)$ is a sequence in $X$, it has a subsequence that converges in $X$

$(X,d)$ is sequentially compact if every sequence in $(X,d)$ has a convergent subsequence.

compact $\Leftrightarrow$ accumulation point compact $\Leftrightarrow$ sequentially compact

Let $(X,d)$ be a metric space and $(p_n)$ be a sequence in $X$
Let $S = \{p_n\}$
$S^* = \{p \in X | \exists (p_{n_k}): p_{n_k} \rightarrow p\}$
$S^\infty = \{p \in X | p_n = p \text{ for infinitely many } n \in \mathbb{N}\}$
Then
- $S = S' \cup S^\infty$
- $S*$ is closed

$S^* = S' \cup S^\infty \subset S' \cup S = \overline{S}$

## Cauchy sequences
Let $(X,d)$ be a metric space. $(p_n)$ is Cauchy if $\forall \epsilon > 0: \exists N \in \mathbb{N}: \forall n,m \geq N: d(p_n,p_m) < \epsilon$

convergent $\Rightarrow$ Cauchy (Note the converse is not true)

$(p_n)$ is Cauchy in $(X,d)$ and $\{p_n\} \subset Y \subset X$, then $(p_n)$ is Cauchy in $(Y,d)$

In $(X,d)$, $(p_n)_{n \in \mathbb{N}}$ Cauchy $\Rightarrow \{p_n\}$ bounded

In $(X,d)$, let $Y \subset X$.
- $Y$ complete $\Rightarrow Y$ is closed in $X$
- $\begin{cases} X \text{ complete} \\ Y \text{ closed in } X\end{cases} \Rightarrow Y \text{ complete}$

## Complete metric space
$(X,d)$ is complete if every Cauchy sequence converges.

$\begin{cases}
(p_n)_{n \in \mathbb{N}} \text{ Cauchy} \\
p_{n_k} \rightarrow p \in X
\end{cases} \Rightarrow p_n \rightarrow p \in X$

A Cauchy sequence has at most one subsequential limit.

compact $\Rightarrow$ complete

## Convergence in $(\mathbb{R}^k, d_{eucl})$
In $(\mathbb{R}^k, d_{eucl})$, every bounded sequence contains a convergent subsequence.
$(\mathbb{R}^k, d_{eucl})$ is complete.
In $(\mathbb{R}, d_{eucl})$. $(x_n)$ is bounded and monotonic. Then, if $(x_n)$ is increasing, (not necessarily strictly increasing), $x_n \rightarrow \sup \{x_n\}$. If $(x_n)$ is decreasing, $x_n \rightarrow \inf \{x_n\}$

## Upper and lower limit in $(\mathbb{R}, d_{eucl})$
$x_n \rightarrow \infty \Leftrightarrow \forall M \in \mathbb{R}: \exists N \in \mathbb{N}: \forall n \geq N: x_n \geq M$

Let $(x_n)$ be a sequence in $(\mathbb{R}, d_{eucl})$
Let $S^*$ be the set of subsequential limits in $\mathbb{R}$
Let $E$ be the set of subsequential limits in $\overline{\mathbb{R}}$
Then $E \subset S^* \cup \{\pm \infty\} \subset \overline{R} = \mathbb{R} \cup \{\pm \infty\}$
$\limsup_{n \rightarrow \infty} x_n = \sup E = x^*$
$\liminf_{n \rightarrow \infty} x_n = \inf E = x_*$
Note that $\sup E$ and $\inf E$ always exists in $\overline{R}$
Moreover,
- $x^* \in E \Rightarrow \sup E = \max E$
- $x > x^* \Rightarrow \exists N \in \mathbb{N}: \forall n \geq N: x_n < x$
- $x^*$ is the only number that satisfies the above two properties

$\limsup_{n \rightarrow \infty} x_n = \lim_{k \rightarrow \infty} (\sup \{a_n | n \geq k\})$
If $(x_n)_{n \in \mathbb{N}}$ decreasing, $\limsup_{n \rightarrow \infty} x_n = \inf_{k \in \mathbb{N}} \sup_{n \geq k} x_n$

$\lim_{n \rightarrow \infty} x_n = x \Leftrightarrow \limsup_{n \rightarrow \infty} x_n = \liminf_{n \rightarrow \infty} x_n = x$

## Limit of a function at a point
Let $(X,d_X), (Y, d_Y)$ be metric spaces.
Let $E \subset X$, $f: E \rightarrow Y$ and $p \in E'$.
$\lim_{x \rightarrow p} f(x) = q \Leftrightarrow \forall \epsilon > 0: \exists \delta > 0: \forall x \in E, 0 < d_X(x,p) < \delta: d_Y(f(x), f(p)) < \epsilon$
In other words,
$\forall \epsilon > 0: \exists \delta > 0: f(B_X(p, \delta) \cap E \setminus \{p\}) \subset B_Y(q, \epsilon)$

Let $(X, d_X), (Y, d_Y)$ be metric spaces
Let $E \subset X, p \in E', q \in Y, f: E \rightarrow Y$ function. Then
$\lim_{x \rightarrow p} = q \Leftrightarrow \forall (p_n)_{n \in \mathbb{N}}, \lim_{n \rightarrow \infty} p_n = p: \lim_{n \rightarrow \infty} f(p_n) = q$

The limit of a function is unique

Remark:
- $f(p)$ might not exist

## Continuous function
$(X, d_X), (Y, d_Y)$ metric spaces
$E \subset X, p \in E$
$f: E \rightarrow Y$ function
$f$ is continuous at $p \Leftrightarrow \forall \epsilon > 0: \exists \delta > 0: \forall x \in E, d_X(x, p) < \delta: d_Y(f(x), f(p)) < \epsilon$

$f$ is continuous on $E \Leftrightarrow f$ is continuous at all points in $E$

Remark:
- $f(p)$ must exists
- $p$ is an isolated point of $E \Rightarrow f$ is continuous at $p$
- $p \in E \cap E' \Rightarrow \Big (f \text{ is continuous at } p \Leftrightarrow \lim_{x \rightarrow p} f(x) = f(p) \Big)$

$(X, d_X), (Y, d_Y)$ metric spaces. $f: X \rightarrow Y$ function. Then
$f \text{ is continuous on } X \Leftrightarrow \forall V \text{ open in } Y: f^{-1}(V) \text{ is open in } X$

Let $(X, d_X), (Y, d_Y), (Z, d_Z)$ be metric spaces
Let $f: X \rightarrow Y$, $g: Y \rightarrow Z$ be continuous functions
Then $g \circ f: X \rightarrow Z$ is continuous

## $\mathbb{R}^k$-valued functions
A $\mathbb{R}^k$ function is continuous $\Leftrightarrow$ every coordinate function is continuous
Examples of continuous functions:
- Polynomial functions
- Rational functions (denominator is not zero)
- Modulus of functions $\vec{x} \mapsto ||\vec{x}||$

## Continuity and Compactness
$(X, d_X), (Y, d_Y)$ metric spaces
$\begin{cases}
K \subset X \text{ compact} \\
f: X \rightarrow Y \text{ continuous }
\end{cases} \Rightarrow f(K)$ is compact

$(X, d)$ metric space
$\begin{cases} f: X \rightarrow \mathbb{R} \text{ continuous} \\
K \subset X \text{ compact}
\end{cases} \Rightarrow \exists x,y \in K: \sup f(K) = f(x), \inf f(K) = f(y)$
$\Rightarrow \exists x,y \in K: \forall p \in K: f(x) \leq f(p) \leq f(y)$

$(X, d_X), (Y, d_Y)$ metric spaces
$\begin{cases}
X \text{ compact} \\
f: X \rightarrow Y \text{ continuous bijective}
\end{cases} \Rightarrow f^{-1}: Y \rightarrow X \text{ is continuous}$

## Uniformly continuous
$(X, d_X), (Y, d_Y)$ metric spaces
$f: X \rightarrow Y$ function
$f \text{ is uniformly continuous} \Leftrightarrow \forall \epsilon > 0: \exists \delta > 0: \forall x,y \in X, d_X(x,y)<\delta: d_Y(f(x),f(y)) < \epsilon$

Uniform continuity $\Rightarrow$ continuity

$(X, d_X), (Y, d_Y)$ metric spaces

$\begin{cases}
f: X \rightarrow Y \text{ continuous} \\
X \text{ compact}
\end{cases} \Rightarrow f \text{ is uniformly continuous}$

## Connectedness
$A, B$ are separated $\Leftrightarrow \begin{cases}
A \cap \overline{B} = \emptyset \\
B \cap \overline{A} = \emptyset
\end{cases}$

$E$ is connected $\Leftrightarrow \forall A,B \text{ separated}, E = A \cup B: A = \emptyset \text{ or } B = \emptyset$

$\begin{cases}
f: X \rightarrow Y \text{ continuous} \\
E \text{ connected}
\end{cases} \Rightarrow f(E) \text{ connected}$

## Connectedness in $(\mathbb{R}, d_{eucl})$
$E \subset \mathbb{R}$ is convex $\Leftrightarrow \forall x,y \in E: x < z < y \Rightarrow z \in E$

In $(\mathbb{R}, d_{eucl}), E \subset \mathbb{R}$, $E$ is connected $\Leftrightarrow E$ is connected.

$[a,b]$ is connected in $\mathbb{R}$

### Intermediate Value Theorem
$f: [a,b] \rightarrow \mathbb{R}$ continuous $\Rightarrow \forall f(a) < c < f(b): \exists x \in (a,b): f(x) = c$

## Infinite limits

## Discontinuities
### First kind
- Both left and right limits exist
- (Removable) $f(x^+) = f(x^-)$ but discontinuous at $x$
- (Jump) $f(x^+) \ne f(x^-)$
### Second kind (essential)
- Left limit or right limit does not exist

## Monotonic functions
increasing, dereasing $\ne$ strictly increasing / strictly decreasing

$f: (a,b) \rightarrow \mathbb{R}$ monotically increasing, then $f(x^+)$ and $f(x^-)$ exists at every point and
$\sup_{a<t<x} f(t) \leq f(x^-) \leq f(x) \leq f(x^+) \leq \inf_{a < t < x} f(t)$
Moreover, if $a < x < y < b$, then $f(x^+) \leq f(y^-)$

$f: (a,b) \rightarrow \mathbb{R}$ monotonic. Let $E \subset (a,b)$ be the set of points at which $f$ is discontinuous.
Then, $E$ is at most countable.

## Differentiation
- Diff $\Rightarrow$ Cont
- $\begin{cases} f \text{ is diff} \\ g \text{ is diff} \end{cases} \Rightarrow f+g, fg \text{ is diff}$. For $\frac{1}{g}$, we need $g \ne 0$
- $f,g$ diff and $g \circ f$ exists, then $g \circ f$ is diff.
- $f$ cont on $[a,b]$, Sign of $f'$ on $(a,b) \Rightarrow f$ monoticity.
## Generalized MVT
- $f,g$ cont on $[a,b]$, diff on $(a,b)$. Then $\exists c \in (a,b): g'(c)(f(b)-f(a)) = f'(c)(g(b)-g(a))$
## L'Hospital
- Can use for $\frac{0}{0}$ and $\frac{\infty}{\infty}$ cases
## Taylor's theorem
End of Chapter 5
## FTC
### Version 1
Let $f: [a,b] \rightarrow \mathbb{R}$, $f \in \mathcal{R}([a,b])$
Let $F: [a,b] \rightarrow \mathbb{R}$, $F(x) = \int_a^x f(t) dt$
Then
- $F$ is uniformly continuous on $[a,b]$
- If $f$ is cont at $x_0 \in (a,b)$, then $F$ is diff at $x_0$ and $F'(x_0) = f(x_0)$
### Version 2
Let $f: [a,b] \rightarrow \mathbb{R}$, $f \in \mathcal{R}([a,b])$
Let $F: [a,b] \rightarrow \mathbb{R}$ cont on $[a,b]$, diff on $(a,b)$ s.t. $F' = f$ on $(a,b)$
Then, $\int_a^b f = F(b) - F(a)$
### Integration by parts
$\int_a^b udv = uv - \int_a^b vdu$
Note $u, v$ cont on $[a,b]$, diff on $(a,b)$. $u, v \in \mathcal{R}([a,b])$

## Theorem from HW
### HW4
$(X,d)$ be a metric space.
- $E \subset X$. Then $E'$ is closed.
- $E, F \subset X$. Then $(E \cup F)' = E' \cup F', \overline{E \cup F} = \overline{E} \cup \overline{F}$. This is also true with finite number of sets.
- With countable number of sets, we have:
$\cup_{i=1}^\infty \overline{E_i} \subset \overline{\cup_{i=1}^\infty E_i}$
- $(\overline{E})^c = (E^c)^o$
- $E$ is dense $\Leftrightarrow \forall V \subset E, V \text{ open}: \exists x \in E: x \in V$

In $(\mathbb{Q}, d_{eucl})$, $(\sqrt{2}, \sqrt{3})$ is closed, open, bounded, but not compact.

In $(X, d_{dis})$, $K$ compact $\Rightarrow K$ is finite.

## Nested sets
Let $(X,d)$ be a metric space.
Let $(K_n)_{n \in \mathbb{N}}$ be a sequence of nested non-empty compact sets in $X$
Then, $\lim_{n \rightarrow \infty} \text{diam } K_n = 0 \Rightarrow |\cap_{n=1}^\infty K_n| = 1$

Let $(X,d)$ be a complete metric space.
Let $(K_n)_{n \in \mathbb{N}}$ be a sequence of nested non-empty closed and bounded sets in $X$
Then, $\lim_{n \rightarrow \infty} \text{diam } K_n = 0 \Rightarrow |\cap_{n=1}^\infty K_n| = 1$

## Distance function
$d(x,E) = 0 \Leftrightarrow x \in \overline{E}$
$E$ compact $\Rightarrow \exists p^* \in E: d(x,E) = d(x,p^*)$

## HW6
In $(\mathbb{R}, d_{eucl})$, if $\lim_{n \rightarrow \infty} x_n = x$, then $\lim_{n \rightarrow \infty} \sigma_n = x$ with $\sigma_n = \frac{x_1 + x_2 + ... x_n}{n}$
Note the converse is not true.

## HW7
The distance function from a point is continuous

$A \subset f^{-1}f(A)$
$f(f^{-1}(B)) \subset B$
$f(C) \setminus f(A) \subset f(C \setminus A)$
$f^{-1}(D \setminus B) = f^{-1}(D) \setminus f^{-1}(B)$

$f$ is well-behaved with union. It does not well-behaved with intersection and set-minus. Specifically
$f(\cap A) \subset \cap f(A)$
$f^{-1}$ is well-behaved with set minus, intersection, and union.