Logic

Set Theory

Graph Theory

Graph

Definition
A graph $G$ consists of a finite collection of vertices $V(G)$ and edges $E(G)$ where each edge connects a distinct pair of vertices.
- We only discuss the undirected graph, which is the simple graph (at most one edge between any two vertices) and its edges have no orientation.
- The order of $G$ is $|V|$ and the size of $G$ is $|E|$.
- Two vertices are adjacent vertices if they are connected by a edge.
- The degree of a vertice is the number of adjacent vertices of it. A vertex with an odd (even) degree is an odd (even) vertice.
- A graph is complete if every distinct pair of vertices is connected by an edge.
Properties
- Graphs $F$ and $G$ are isomorphic if there exists a function $f:V(F)\rightarrow V(G)$ that is both one-to-one and onto, and all adjacencies are preserved.

Path, Cycle, Forest and Tree

A path is a sequence of adjacent vertices and the connecting edges. A graph is connected if every pair of vertices can be connected by at least one path. A path that begins and ends at the same vertex is a cycle. A graph with no cycles is a forest, and if such a graph is connected, it is a tree.

Subgraph, Spanning Graph And Spanning Tree

Let $G$ be a graph with vertex and edge sets $V(G)$ and $E(G)$. $H$ is a subgraph of $G$ if

$V( H) \subseteq V(G)$;
$E(H)\subseteq E(H)$;
every edge of $H$ connects two vertices of $H$,
which means that the vertices of $H$ are a subset of the vertices of $G$, and every pair of adjacent vertices in $H$ also appears in $G$.

Furthermore, if $V(H)=V(G)$, then $H$ is a spanning subgraph of $G$. In addition, if $H$ is a tree, then $H$ is a spanning tree of $G$.

Algorithms

Combinatorics

Probability And Statistics

Point-Set Topology

Topology

Let $X$ be a nonempty set and $\mathcal{P}(X)$ be the power set of $X$. A topology on $X$, denoted by $T\subset \mathcal{P}(X)$, is a family of subsets of $X$, for which satisfies

$\varnothing\in T$ and $X\in T$.
If $O_1,O_2\in T$, then $O_1\cap O_2\in T$. (finite intersection)
If $O_i\in T$ for $i\in I$, then $\bigcup\limits_{i\in I}O_i\in T$. (infinite union)

We can define a topology by a basis $B\subset \mathcal{P}(X)$:

$\forall\ x\in X$, $\exists\ V\in B$, s.t. $x\in V$.
$\forall\ V_1,V_2\in B$ and $x\in X$, if $x\in V_1\cap V_2$, then $\exists\ V_3\in B$, s.t. $x\in V_3\subset V_1\cap V_2$.

The open sets in $T$ are all the possible unions of sets in $B$. In general, bases are not unique.

We call the sets in $T$ the open sets. A set $C$ is closed if $X\setminus C$ is open.

Hausforff Topology

A topology is Hausforff if $\forall\ x,y\in X$, $\exists\ V_x,V_y\in T$, $V_x\cap V_y=\varnothing$, s.t. $x\in V_x,y\in V_y$.

Subspace Topology

Given $A\subset X$, the subspace topology on $A$ consists of the open sets $\{A\cap U|U\in T\}$.

Continuity

Open Maps

Definition
A map $f:X_1\rightarrow X_2$ is open if the image of every open set in $X_2$ is open in $X_1$.

Continous Maps

A map $f:X_1\rightarrow X_2$ is continuous if for any open set in $X_2$, the inverse image in $X_1$ is open.

A map $f:X_1\rightarrow X_2$ is continuous if for any set in $T_2$, the inverse image is in $T_1$.

Equivalently, $f$ is continuous if and only if for any $C$ closed in $X_2$, $f^{-1}(C)$ is closed in $X_1$.

Homeomorphisms

Definition
If a map $f:X_1\rightarrow X_2$ is a bijection, and both $f$ and $f^{-1}$ are continuous (or equivalently, $f$ is a continuous and open map), then $f$ is a homeomorphism.

Homeomorphism is similar to isomorphism between groups or rings, in the sense that it preserves topological structure including the cardinal number of topology, connectedness and compactness.

Properties
- Let $f:X_1\rightarrow X_2$ be a bijective, continuous map of topological spaces. If $X_1$ is compact and $X_2$ is Huasdorff, then $f$ is a homeomorphism.

Connectedness

Let $(X,T)$ be a topological space. Then $X$ is connected if the only subsets of $X$, which are both open and closed are $\varnothing$ and $X$.

$X$ is disconnected, if there exsits $U,V\in T$, $U,V\neq \varnothing$ and $U\cap V=\varnothing$, s.t. $X=U\cup V$. Equivalently, $X$ is disconnected if there exists a continuous surjective map $f:X\mapsto \{0,1\}$.

For the subspace topology on $A\subset X$, if $A$ is connected, then $\forall\ B$ such that $A\subseteq B\subseteq \overline{A}$, $B$ is connected.

$X$ is path-connected if for
any two points $x, y \in X$, there exists a continuous function $f : [0, 1] \rightarrow X$ such that $f(0) = x $ and $f(1) = y$. Every path-connected space is connected.

If $X$ is path connect, then $X$ is connected. For open sets in $\mathbb{R}^n$, $X$ is path connected if and only if $X$ is connected.

Compactness

Given a topology space $(X,T)$, a subset $A\subset X$ is compact if for every open cover there is a finite subcover.

Every finite set is compact.

In $\mathbb{R}^n$, a set is compact if and only if it is closed and bounded.

In a Hausdorff space, a set is closed if it is compact.

In a compact space, a set is compact if it is closed.

For example, $\mathbb{R}$ is Hausdorff but not compact since it is not bounded. A compact subset of $\mathbb{R}$ is closed and bounded. But not all closed subsets are compact.

Metric Spaces

Definition
Let $X$ be a nonempty set. A metric on $X$ is a function $d:X\times X\mapsto \mathbb{R}$ if for all $x,y,z\in X$,

$d(x,y)\geq 0$ and $d(x,y)=0$ if and only if $x=y$.
$d(x,y)=d(y,x)$.
$d(x,z)\leq d(x,y)+d(y,z)$.

We call $d(x, y)$ the distance between $x$ and $y$. A set X, together with a metric on X, is called a metric space.

$B_d(x,\epsilon)=\{y\in X:d(x,y)<\epsilon\}$ is called an $\epsilon$-ball. The metric topology induced by $d$ is the collection of all $\epsilon$-balls $B=\{B_d(x,\epsilon:x\in X,\epsilon>0\}$.

Main Results

If $X,Y$ are connected/compact, then $X\times Y$ is connected/compact.
If $X,Y$ are connected and $X\cap Y\neq \varnothing$, then $X\cup Y$ is connected.
If $X$ is connected/compact and $f:X\mapsto Y$ is continuous, then $f(X)$ is connected/compact.
If $X$ is compact and $f:X\mapsto \mathbb{R}$, then $f$ attains its global maximum and minimum.
If $X$ is compact, $Y$ is Hausdorff and $f:X\mapsto Y$ is continuous, then $f$ is a closed map.
If $X$ is compact, $Y$ is Hausdorff and $f:X\mapsto Y$ is bijective and continuous, then $f$ is a homeomorphism.
If $f$ is a homeomorphism, then $X$ is connected/compact if and only if $Y$ is connected/compact.
If $(X,T,d)$ is a metric space, then $A\subset X$ is compact if and only if every sequence in $A$ has a convergent subsequence.

Real Analysis

Complex Variables

Complex Numbers

Introduction

Thre complex numbers $\mathbb{C}$ is a set of all order pairs of real numbers $(x,y)$. The imaginary unit $i$ is a complex number such that $i^2=-1$. Then each complex number can be expressed as $z=x+yi$ where $x\in\mathbb{R}$ and $y\in\mathbb{R}$ are called the real part and imaginary part of $z$, denoted by $\text{Re} z$ and $\text{Im} z$ respectively. The (complex) conjugate of $z$ is the number $\overline{z}=x-yi$.

The complex numbers can be graphed on the complex plane ($xy$-plane). The horizontal $x$-axis is called the real axis and the vertical $y$-axis is called the imaginary axis.

The modulus, magnitude or absolute value of $z$ is given by $|z|=\sqrt{x^2+y^2}$. The absolute value of $z$ satisfies $|z|^2=z\overline{z}$.

The Polar Form

The angle $\theta$ that the vector (from the origin to $z$) makes with the positive real axis is called an argument of $z$, denoted by $\text{arg} z$. We can add any integer multiple of $2n\pi$ to an argument of $z$, and the result is another argument of $z$. Therefore, we define the principal argument of $z$, denoted by $\text{Arg} z$ as the unique value of the argument that lies in the interval $-\pi<\theta\leq \pi$.

Let $r=|z|$, $x=r\cos\theta$ and $y=r\sin\theta$, then the polar form of $z$ is given by

$z=r(\cos\theta+i\sin\theta).$

The Exponential Form

From the Euler’s Formula $e^{i\theta}=\cos\theta+i\sin\theta,$
the exponential form of $z$ is given by $z=re^{i\theta}.$
A useful result that follows from Euler’s Formula is $(\cos\theta+i\sin\theta)^n=\cos(n\theta)+i\sin(n\theta).$

Complex Functions

Complex Roots

If $n$ is a positive number, we can solve the equation $z^n=1$ and the solutions are called $n^{\text{th}}$ roots of unity. The equation can be expressed as $r^ne^{in\theta}=e^{i2k\pi}$ for $k\in \mathbb{Z}$. So $r=1$, $\theta= \frac{2k\pi}{n}$ and $z=e^{i\frac{2k\pi}{n}}$ for $k=0,1,\ldots,n-1$.

More generally, if we want to solve the equation $z^n=w$, or equivalently, $r^ne^{i\theta}=Re^{i(\Theta+2k\pi)}$ for $k\in\mathbb{Z}$. Then the solution is given by $R^{\frac{1}{n}}e^{i\frac{\Theta+2k\pi}{n}}$ for $k=0,1,\ldots,n-1$.

Vieta for $z^n-Re^{i\theta}=0$ $n>2$ is

The sum of roots is 0.
The product of roots is $(-1)^{n+1}Re^{i \theta}$

Complex Logarithms

If we write $z=re^{i(\theta+2k\pi)}$ for $k\in\mathbb{Z}$, then the logarithms of $z$ is given by $\log z=\log r+i(\theta+2k\pi)$. The principal logarithm of $z$ is gievn by $\text{Log}z=\log|z|+i\text{Arg}z.$

Complex Powers

For complex numbers $z$ and $w$, the complex power is given by $z^w=e^{w\log z}$ and the principal value of $z^w$ is equal to $z^w=e^{w\text{Log} z}$.

The Trigonometric Functions

The cosine and sine of a complex number are defined as

$\cos z=\frac{e^{iz}+e^{-iz}}{2}\qquad \sin z=\frac{e^{iz}-e^{-iz}}{2i}.$

The Hyperbolic Functions

The hyperbolic cosin and the hyperbolic sine are defined as

$\cosh z=\frac{e^z+e^{-z}}{2}\qquad \sinh z=\frac{e^{z}-e^{-z}}{2}.$

Differentiability of Complex Functions

The Derivative of A Function of A Complex Variable

The function $f$ can be expressed as $f(z)=f(x+yi)=u(x,y)+iv(x,y)$. A function $f(z)$ is said to be differentiable at the point $z_0$ if $\lim\limits_{z\rightarrow z_0}\frac{f(z)-f(z_0)}{z-z_0}$ exists. The nonzero complex number $z$ can approach the origin from infinitely many directions, which is a very strong condition.

The Cauchy-Riemann Equations

If $f$ is differentiable at $z_0$, then the limit $\lim\limits_{z\rightarrow z_0}\frac{f(z)-f(z_0)}{z-z_0}=\lim\limits_{z\rightarrow z_0}\frac{u(x,y)-u(x_0,y_0)}{z-z_0}+\lim\limits_{z\rightarrow z_0}i\frac{v(x,y)-v(x_0,y_0)}{z-z_0}$ exists. If we let $z$ approach the origin along the real axis, then $\lim\limits_{z\rightarrow z_0}\frac{f(z)-f(z_0)}{z-z_0}=\frac{\partial u}{\partial x}+i\frac{\partial v}{\partial x}.$ If we let $z$ approach the origin along the imaginary axis, then $\lim\limits_{z\rightarrow z_0}\frac{f(z)-f(z_0)}{z-z_0}=\frac{1}{i}\frac{\partial u}{\partial y}+\frac{\partial v}{\partial y}=\frac{\partial v}{\partial y}-i\frac{\partial u}{\partial y}.$
Therefore, $\frac{\partial u}{\partial x}=\frac{\partial v}{\partial y}\qquad \frac{\partial v}{\partial x}=-\frac{\partial u}{\partial y},$ which is called the Cauchy-Riemann equations. Conversely, if the Cauchy-Riemann equations are satisfied and the four partial derivatives are continuous throughout an open set containing $z_0$, then the function $f$ is differentiable at the point $z_0$.

Holomorphic Functions

If $f(z)$ is differentiable at $z_0$ and at every point throughout some open set in the complex plane containing $z_0$, then we say that $f(z)$ is holomorphic at the point $z_0$. In general, if $f(z)$ is differentiable throughout some open set $O$ in the complex plane, then $f(z)$ is said to be holomorphic in $O$.

If $f(z)$ is holomorphic on an open set $O$, then Cauchy-Riemann conditions are satisfied on $O$ and $f(z)$ is differentiable infinitely many times. Conversely, if Cauchy-Riemann conditions are satisfied on an open set $O$ and $u_x,u_y,v_x,v_y$ are continuous on $O$, then $f(z)=u(x,y)+v(x,y)$ is holomorphic on $O$.

If Cauchy-Riemann conditions are satisfied when $z=z_0$ and $u_x,u_y,v_x,v_y$ are continuous on an open set $O$ containing $z_0$, then $f(z)=u(x,y)+v(x,y)$ is differentiable at $z=z_0$.

Analytic Functions

$f(z)$ is analytic at $z_0$, if there exists a power series $\sum\limits_{n=0}^{\infty}a_n(z-z_0)^n$ which converges to $f(z)$ in an open neighborhood $O$ of $z_0$, i.e., $\forall\ z\in O,$ $\lim\limits_{N\rightarrow\infty}|f(z)- \sum\limits_{n=0}^Na_n(z-z_0)^n |=0.$
The radius of convergence (Cauchy-Hadamard) is $R=\frac{1}{\limsup\limits_{n\rightarrow\infty}|a_n|^{\frac{1}{n}}}$. We can also use the ratio test if the limit exists: $R=\lim\limits_{n\rightarrow\infty}\left|\frac{a_{n+1}}{a_n}\right|.$

If $f(z)=\sum\limits_{n=0}^{\infty}a_n(z-z_0)^n$ converges with radius $R$, then the series converges absolutely in $\{z||z-z_0|<R\}$, and converges uniformly in $\{z||z-z_0|<R-\epsilon\}$, $\forall\ \epsilon\in(0,R)$.

$f(z)$ is analytic in an open set $O$ if it is analytic at any $z\in O.$

$f(z)$ is analytic in $O$ if and only if $f(z)$ is holomorphic in $O$.

If $f(z)$ is analytic everywhere in the complex plane, then $f(z)$ is said to be an entire function.

Meromorphic Functions

Meromorphic functions are analytic except some isolated points called poles.

If a function $f(z)$ is not analytic at $z_0$, but is analytic at some point in every punctured disk center at $z_0$, then $z_0$ is said to be a singularity of $f(z)$.
If $z_0$ is a singularity of $f(z)$ and $f(z)$ is analytic at every point in some puctured open disk centered at $z_0$, then we call $z_0$ an isolated singularity. If there is a positive number $n$ such that $f(z)=\frac{g(z)}{(z-z_0)^n}$ with $g(z)$ analytic in a nonpunctured open disk centered at $z_0$ and $g(z_0)\neq 0$, then the isolated singularity $z_0$ of $f$ is called a pole of order $n$. Otherwise, $z_0$ is called an essential singularity if we canot write $f(z)$ in this form for any $n\in\mathbb{N}$.
Nonisolated singularities can be cluster points or natural boundaries.

Complex Line Integrals

Definition

Let $C$ be a smooth path in the complex plane, which is given parametrically by the equation $z(t) = x(t) + iy(t)$, from $t = a$ to $t = b$ (where $t$ is real). If $f(z )$ is a continuous function along $C$, then we have: $\int_C f(z)\mathrm{d}z=\int_a^b f(z(t))\cdot z'(t)\mathrm{d}t.$
Alternatively, we could have invoked the fundamental theorem of calculus abd written $\int_Cf(z)\mathrm{d}z=F(z(b))-F(z(a)),$ where $F(z)$ is an antiderivative of $f( z )$.

Complex Line Integrals of Analytic Functions

Cauchy’s Theorem: If $f(z)$ is analytic throughout a simply connected, open set $O$, then for every closed path $C$ in $O$, we have: $\oint_C f(z）\mathrm{d}z=0.$ In particular, if $f(z)$ is an entire function, then $\oint_C f(z）\mathrm{d}z=0$ for any closed path in the plane.
Morera’s Theorem: If $f(z)$ is continuous throughout an open, connected set $O$ in the complex plane, and $\oint_C f(z)\mathrm{d}z = 0$ for every closed curve $C$ in $O$, then $f (z)$ is analytic in $O$.
Cauchy’s Integral Formulas: If $f(z)$ is analytic at all points within and on a simple, closed path, $C$, that surrounds the point $z_0$, then: $f(z_0)=\frac{1}{2\pi i}\oint_C\frac{f(z)}{z-z_0}\mathrm{d}z.$ Furthermore, the $n$th derivative, $f^{(n)}(z)$, is also analytic at $z_0$ for all positive integers $n$, and: $f^{(n)}(z_0)=\frac{n!}{2\pi i}\oint_C\frac{f(z)}{(z-z_0)^{n+1}}\mathrm{d}z.$

The Residue Theorem

If $z_0$ is the only singularity in a connected open set $O$, and $C\in O$ is a simple, closed, positively oriented curve in the annulus where the Laurent series expansion of $f(z)$ is valid, then $a_{-1}=\frac{1}{2\pi i}\oint_Cf(z)\mathrm{d}z.$
The number $a_{-1}$, which is the coefficient of $(z-z_0)^{-1}$ in the Laurent series of $f(z)$, called the residue of $f(z)$ at the singularity $z_0$, denoted by $\text{Res}(z_0,f)$.

Furthermore, if $z_0$ is a pole of order $k$, then $\text{Res}(z_0,f)=\frac{1}{k!}\lim\limits_{z\rightarrow z_0}\frac{\mathrm{d^{k-1}}}{\mathrm{d}z^{k-1}}[(z-z_0)^kf(z)].$

If the curve $C$ surrounds more than one singularity of $f(z)$, the residue theorem says that if $f(z)$ is analytic throughout the interior of $C$, except at a finite number of singularity $z_1,\ldots,z_n$ inside $C$, then $\oint_Cf(z)\mathrm{d}z=2\pi i\cdot\sum\limits_{i=1}^n\text{Res}(z_n,f).$

Series Expansion

Taylor Series

List of Maclaurin series of some common functions is given by

$\begin{align*} e^{x}&=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}&&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+\cdots\\ \ln(1-x)&=-\sum _{n=1}^{\infty }{\frac {x^{n}}{n}}&&=-x-{\frac {x^{2}}{2}}-{\frac {x^{3}}{3}}-\cdots \\\ln(1+x)&=\sum _{n=1}^{\infty }(-1)^{n+1}{\frac {x^{n}}{n}}&&=x-{\frac {x^{2}}{2}}+{\frac {x^{3}}{3}}-\cdots \\ {\frac {1}{1-x}}&=\sum _{n=0}^{\infty }x^{n}\\{\frac {1}{(1-x)^{2}}}&=\sum _{n=1}^{\infty }nx^{n-1}\\{\frac {1}{(1-x)^{3}}}&=\sum _{n=2}^{\infty }{\frac {(n-1)n}{2}}x^{n-2}\\ (1+x)^{\alpha }&=\sum _{n=0}^{\infty }{\binom {\alpha }{n}}x^{n}\\ \sin x&=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{(2n+1)!}}x^{2n+1}&&=x-{\frac {x^{3}}{3!}}+{\frac {x^{5}}{5!}}-\cdots &&{\text{for all }}x\\[6pt]\cos x&=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{(2n)!}}x^{2n}&&=1-{\frac {x^{2}}{2!}}+{\frac {x^{4}}{4!}}-\cdots &&{\text{for all }}x\\[6pt]\tan x&=\sum _{n=1}^{\infty }{\frac {B_{2n}(-4)^{n}\left(1-4^{n}\right)}{(2n)!}}x^{2n-1}&&=x+{\frac {x^{3}}{3}}+{\frac {2x^{5}}{15}}+\cdots &&{\text{for }}|x|<{\frac {\pi }{2}}\\[6pt]\sec x&=\sum _{n=0}^{\infty }{\frac {(-1)^{n}E_{2n}}{(2n)!}}x^{2n}&&=1+{\frac {x^{2}}{2}}+{\frac {5x^{4}}{24}}+\cdots &&{\text{for }}|x|<{\frac {\pi }{2}}\\[6pt]\arcsin x&=\sum _{n=0}^{\infty }{\frac {(2n)!}{4^{n}(n!)^{2}(2n+1)}}x^{2n+1}&&=x+{\frac {x^{3}}{6}}+{\frac {3x^{5}}{40}}+\cdots &&{\text{for }}|x|\leq 1\\[6pt]\arccos x&={\frac {\pi }{2}}-\arcsin x\\&={\frac {\pi }{2}}-\sum _{n=0}^{\infty }{\frac {(2n)!}{4^{n}(n!)^{2}(2n+1)}}x^{2n+1}&&={\frac {\pi }{2}}-x-{\frac {x^{3}}{6}}-{\frac {3x^{5}}{40}}-\cdots &&{\text{for }}|x|\leq 1\\[6pt]\arctan x&=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}x^{2n+1}&&=x-{\frac {x^{3}}{3}}+{\frac {x^{5}}{5}}-\cdots &&{\text{for }}|x|\leq 1,\ x\neq \pm i \end{align*}$

Laurent Series

If $f(z)$ is analytic in an annulus $R_1<|z-z_0|<R_2$ where $R_1\in[0,\infty)$, $R_2\in(0,\infty]$ and $R_1<R_2$, then it can be expanded in a Laurent series,

$f(z)=\underbrace{\sum\limits_{n=1}^{\infty}a_{-n}(z-z_0)^{-n}}_{\text{singular part}}+\underbrace{\sum\limits_{n=0}^{\infty}a_{n}(z-z_0)^{n}}_{\text{analytic part}}.$

The coefficients can be calculated as

$a_n=\frac{1}{2\pi i}\oint\frac{f(z)}{(z-z_0)^{n+1}}\mathrm{d}z=\frac{f^{(n)}(z_0)}{n!}$ $a_{-n}=\frac{1}{2\pi i}\oint\frac{f(z)}{(z-z_0)^{-n+1}}\mathrm{d}z$

for $n\geq0$.

In practice, we don’t usually figure out the Laurent coefficients from this formula; instead, we derive them by algebraic manipulations of the Taylor series.

Main Theorems

Let $C=\{z||z-z_0|=R\}$ and $M=\max\limits_C |f(z)|$, then $|f^{(n)}(z_0)|\leq \frac{n!}{R^n}M$.
If $f(z)$ is an entire function and is bounded, then $f(z)$ is constant.