离散数学与结构 课程笔记
Visits: 10834
授课教师:刘天任。
第一次学这些内容,难免有不严谨甚至错误之处,欢迎批评指正!
WordPress 插件对 LaTeX 的渲染与 Typora 不一致,故有部分 LaTeX 渲染炸了,但不打算进行适配。
公理集合论
集合论的公理化
- 设 $a,b$ 是代表集合的字母,规定 $(a \in b)$,$(a = b)$ 是合式公式 (well-formed formula)。$\phi$ 是合式公式,记作 $\phi \in \operatorname{WFF}$。
- 如果 $\phi \in \operatorname{WFF}$,那么规定 $(\lnot \phi) \in \operatorname{WFF}$,
- 如果 $\phi,\psi \in \operatorname{WFF}$,那么规定 $(\phi \land \psi),(\phi \lor \psi) \in \operatorname{WFF}$。
- 如果 $\phi,\psi \in \operatorname{WFF}$,那么规定 $(\phi \Rightarrow \psi),(\phi \Leftrightarrow \psi) \in \operatorname{WFF}$。
- 如果 $\phi(x) \in \operatorname{WFF}$,那么规定 $(\forall x,\phi(x)),(\exist x,\phi(x)) \in \operatorname{WFF}$。
- 其余均不是合式公式。
Zermelo–Fraenkel 集合论
- 外延公理:两个集合相等,当且仅当它们的所有元素都相同。
$$
(\forall X,(\forall Y,((\forall x,((x \in X) \Leftrightarrow (x \in Y))) \Leftrightarrow (X = Y))))
$$
意义:规定了 $=,\in$ 的含义,保证了集合的唯一性。 -
分离公理模式:对任何集合 $Y$,可以通过不包含 $\forall x,\exist x, X$ 的合式公式 $\phi(x)$,分离出一个新的集合 $X \coloneqq {x \in Y : \phi(x)}$,称为 $Y$ 的子集,记作 $X \sube Y$。
$$
(\forall Y,(\exist X,(\forall x,((x \in X)\Leftrightarrow((x \in Y)\land \phi(x))))))
$$
意义:避开了罗素悖论,定义了子集的含义。 -
定理:不存在万有集,即包括一切集合的集合。
证明:若存在,设为 $W$。由分离公理模式,存在集合 ${S \in W: (S \notin S)}$,这会导致罗素悖论。
注记:将 $((\lnot Y) \in X)$ 记作 $(Y \notin X)$。 -
引理:存在空集,记作 $\varnothing$。
$$
(\exist X, (\forall x, (x \notin X)))
$$
说明:事实上,我们首先需要一个公理来保证真的存在一个集合,即无穷公理。我们先承认真的存在一个集合,设为 $W$,则由分离公理模式,存在集合 ${S \in W: ((\lnot S) = S)}$,即为 $\varnothing$。 -
配对公理:对任何集合 $X,Y$,存在集合 ${X,Y}$。
$$
(\forall X,(\forall Y, (\exist Z, (\forall u, ((u \in Z)\Leftrightarrow((u = X)\or(u = Y)))))))
$$
意义:可以导出无序对和有序对的概念。 -
并集公理:对任何集合(集族)$I$,存在集合 $A$,使得 $A$ 中的元素恰为 $I$ 中一切集合的一切元素,记作 $A = \bigcup I$。
$$
\forall I,(\exist A,(\forall x,((x \in A)\Leftrightarrow(\exist i,((i \in I)\land(x \in i))))))
$$
结合配对公理可以进行取并操作,将 $\bigcup{A,B}$ 记作 $A \cup B$。 -
命题:对任何集合(集族)$I$,由分离公理模式,存在集合 $X \coloneqq {x : (\forall i,((i \in I)\Rightarrow(x \in i)))}$,记作 $X = \bigcap I$。
结合配对公理可以进行取交操作,将 $\bigcap{A,B}$ 记作 $A \cap B$。 -
类似地可定义不交并 $A \sqcup B$、差集 $A \setminus B$、对称差 $A \oplus B$ 等常用的集合操作。
-
设 $x,y$ 是集合,定义有序对 $(x,y) \coloneqq {{x},{x,y}}$。
-
幂集公理:对任何集合 $X$,存在其一切子集组成的集合,称为 $X$ 的幂集,记作 $2^X$。
$$
(\forall X,(\exist Y,(\forall Z,((Z \sube X)\Leftrightarrow(Z \in Y)))))
$$ -
命题:设 $X,Y$ 是集合,则存在笛卡尔积 $X \times Y \coloneqq {(x,y):x \in X,y \in Y}$。
证明:$\forall x \in X, y \in Y$,
$$
{x},{x,y} \sube X \cup Y \
\Rightarrow {x},{x,y} \in 2^{X \cup Y} \
\Rightarrow (x,y) = {{x},{x,y}} \sube 2^{2^{X \cup Y}} \
\Rightarrow X \times Y \coloneqq {(x,y):x \in X,y \in Y} \sube 2^{2^{X \cup Y}} \
$$
然后用分离公理。 -
称 $R \sube X \times Y$ 为集合 $X,Y$ 之间的一个关系,将 $(x,y) \in R$ 记作 $xRy$。
特别地,$R \sube X \times X$ 称为集合 $X$ 上的一个关系。 -
映射是指集合 $X,Y$ 之间的一个关系 $R$,满足 $\forall x \in X$,$\exist! y \in Y$ 满足 $xRy$,记作 $f:X \rightarrow Y$,$x \mapsto y$ 或 $f(x) = y$。
注记:$\exist!$ 表示存在唯一,可用轻易合式公式表示。 -
选择公理:对任何不包含空集的(无限)集合(集族),均存在一个选择映射,它从每个集合中选择一个元素。
$$
(\forall X,((\varnothing \notin X) \Rightarrow (\exist f:X \rightarrow \bigcup X, (\forall A \in X,(f(A) \in A)))))
$$ -
正则公理:对任何非空集合 $X$,都存在一个 $y \in X$ 使得 $y \cap X = \varnothing$。
$$
(\forall X,((X \ne \varnothing)\Rightarrow(\exist y,((y \in X) \land (y \cap X = \varnothing)))))
$$ -
推论:不存在以自身为元素之一的集合。
证明:假设存在 $X \in X$,由配对公理可得 $X \in {X}$,因此 $X \in X \cap {X}$,但由正则公理 $X \cap {X} = \varnothing$,矛盾! -
替换公理模式:对任何集合 $X$,如果 $\forall x \in X$,满足合式公式 $\phi(x,y,p)$ 的 $y$ 唯一,那么这些 $y$ 构成集合。
$$
(\forall X,(\forall x,((x \in X)\Rightarrow(\exist!y,\phi(x,y,p)))) \Rightarrow (\exist Y,(\forall y,((y \in Y)\Leftrightarrow(\exist x,((x \in X)\land\phi(x,y,p)))))))
$$
意义:任何可定义函数下集合的像是集合。 -
无穷公理:存在归纳集
$$
(\exist X,((\varnothing \in X) \land (\forall x,((x \in X) \Rightarrow (x^+ \in X)))))
$$
其中后继 $x^+ \coloneqq x \cup {x}$。 -
定理:设 $X$ 是归纳集,则 $X$ 所有归纳子集的交良定且唯一,称为自然数集,记作 $\omega$ 或 $\N$。
$$
0 = \varnothing \
1 = {\varnothing} = {0} \
2 = {\varnothing, {\varnothing}} = {0,1} \
3 = {\varnothing, {\varnothing}, {\varnothing, {\varnothing}}} = {0,1,2} \
\cdots
$$ -
Peano 公理:自然数集 $\omega$ 和 $0$ 满足:
- $0$ 是自然数;
- 每个自然数都有唯一后继;
- $0$ 不是任何自然数的后继;
- 不同自然数有不同后继;
- $\omega$ 满足归纳原理:设集合 $A \sube \omega$ 满足 $0 \in A$,且 $\forall n \in \omega$,$n \in A \Rightarrow n^+ \in A$,那么 $A = \omega$。
序
- 良序原理:自然数集的任何一个非空子集都有最小数,即它不大于任何一个该子集中的自然数。
- 设 $R$ 是集合 $X$ 上的一个关系,若它满足自反性、反对称性和传递性,就称它是一个偏序,记作 $\le$,此时称 $X$ 为偏序集。若 $x \le y \land x \ne y$,记作 $x < y$。
- 若 $X$ 中所有元素对都可比,则 $\le$ 成为全序,称 $X$ 为全序集。偏序集的全序子集称为链,而元素两两不可比的子集称为反链。
- 集合 $X$ 上的一个序称为良序,若其任意一个非空子集都有最小元素。
基数
- 设集合 $A,B$,若存在一个双射 $f:A\to B$,则称 $A,B$ 对等,记作 $A \sim B$。如果 $f$ 只是单射,则称 $A$ 受制于 $B$,记作 $A \preceq B$。若 $A \preceq B \land A \not\sim B$,记作 $A \prec B$。
-
能够和某个自然数建立对等关系的集合称为有限集,否则称为无限集。
-
引理:集合 $A$ 为无限集当且仅当 $A$ 与其某个真子集对等。
证明:充分性显然,下证必要性。
显然 $A$ 非空,故取 $a_0 \in A$。依选择公理,定义映射 $f:\N \to A$,让 $f(0) = a_0$,$f(i)(i>0)$ 为集合 $A \setminus {f(0),f(1),\cdots,f(i-1)}$ 中任意一个元素 $a_i$。
考虑映射 $g:A\to A\setminus {a_0}$:
$$
g(x) = \begin{cases}a_{i+1}\quad\exist i \in \N, x=f(i) \ x \quad \forall i \in \N, x \ne f(i)\end{cases}
$$
则 $g$ 是双射。 -
推论:$\N$ 是最小的无限集。
-
推论:$\N \sim \Z \sim \Z \times \Z \sim \Q$。
关键:“蛇形游走”证明 $\Z \sim \Z \times \Z$。 -
推论:$\R \sim (0,1)\sim (0,1] \sim [0,1]$。
关键:考虑函数 $f(x) = \frac{\arctan x}{\pi} + \frac12$ 证明 $\R \sim (0,1)$。 -
引理:设集合 $X$ 非空,若映射 $f:2^X \to 2^X$ 为单调映射,即满足 $A \sube B \sube X \Rightarrow f(A) \sube f(B)$,则 $\exist T \sube X$,$f(T) = T$。
证明:取 $T = \bigcup {A \sube X:A \sube f(A)}$,则
$$
T \sube \bigcup {f(A):A \sube f(A)}
$$
又 $\forall A \in {A \sube X:A \sube f(A)}$,有 $A \sube T$,故 $f(A) \sube f(T)$,则
$$
\bigcup {f(A):A \sube f(A)} \sube f(T)
$$
故 $T \sube f(T)$。
再作用一次 $f$ 得到 $f(T) \sube f(f(T))$,则 $f(T)$ 也是满足条件的一个 $A$,故 $f(T) \sube T$。
故 $f(T) = T$。 -
Schröder–Bernstein 定理:若集合 $X$ 与集合 $Y$ 的一个子集对等,且集合 $Y$ 与集合 $X$ 的一个子集对等,则 $X \sim Y$。
证明:设有单射 $f:X \to Y$,$g:Y \to X$。考虑映射 $F:2^X \to 2^X$,$A \mapsto X \setminus g(Y \setminus f(A))$,易证其单调,于是 $\exist T \sube X$,$F(T) = T$。
考虑映射 $h:X \to Y$:
$$
h(x) = \begin{cases} f(x) \quad x \in T \ g^{-1}(x) \quad x \notin T\end{cases}
$$
则 $h$ 是双射。 -
Cantor 定理:若 $A \ne \varnothing$,则 $A \not\sim 2^A$。
证明:假设存在双射 $f:A \to 2^A$,考虑集合 $S = {a \in A: a \notin f(a)} \in 2^A$,则 $\exist s \in A$,$f(s) = S$,但 $s \in S \Leftrightarrow s \notin f(s) = S$,矛盾! -
集合 $A$ 的基数记作 $\operatorname{card}(A)$。
-
若某集合和自然数存在一一对应,就称它可数,其基数为可数基数 $\omega$。
-
定理:$[0,1]$ 不是可数的。
关键:Cantor 对角线法。 -
若某集合和 $(0, 1)$ 存在一一对应,其基数为连续基数 $\mathfrak c$。
-
定理:$\operatorname{card}(2^\N) = \mathfrak c$。
关键:证明 $(0,1] \preceq 2^\N$,考虑实数的二进制小数表示(取字典序较大者为唯一表示);证明 $2^\N \preceq (0,1]$,考虑实数的三进制小数表示(二进制小数表示则不为单射)。 -
连续统假设:$\omega,\mathfrak c$ 之间不存在其他基数。
数理逻辑
Propositional Logic
- Alphabet:
- proposition symbols / atomic propositions: $p_0,p_1,p_2,\cdots$ and $\bot$,
- not: $(\lnot)$,
- connectives $\square$: $\land,(\lor),\to,(\leftrightarrow)$,
- auxiliary symbols: $(,)$,
- abbreviations:
$$
\lnot \phi \coloneqq (\phi \to\bot) \ \phi \lor \psi \coloneqq \lnot(\lnot \phi \land \lnot \psi) \ \phi \leftrightarrow \psi \coloneqq (\phi \to \psi) \and (\psi \to \phi)
$$
- The set $PROP$ of propositions is the smallest set with the properties:
- $\forall i \in \N$, $p_i \in PROP$,
- $\bot \in PROP$,
- $\phi \in PROP \Rightarrow \lnot \phi \in PROP$,
- $\phi,\psi \in PROP \Rightarrow (\phi\square\psi) \in PROP$.
Semantics
-
A mapping $v : PROP \rightarrow {0,1}$ is a valuation if
$$
v(\bot) = 0 \
v(\phi \land \psi) = \min(v(\phi), v(\psi)) \
v(\phi \lor \psi) = \max(v(\phi), v(\psi)) \
v(\phi \to \psi) = 0 \Leftrightarrow v(\phi) = 1 \operatorname{and} v(\psi) = 0 \
$$ -
$\vDash \phi$ means $v(\phi) \equiv 1$ for all valuations $v$.
Let $\Gamma$ be a set of propositions, $\Gamma \vDash \varphi$ means $(\forall \psi \in \Gamma, v(\psi) = 1) \Rightarrow v(\phi) = 1$ for all valuations $v$.
Natural Deduction
-
Derivations:
$$
\frac{\phi \quad \psi}{\phi \land \psi} (\land I)\quad \frac{\phi \land \psi}{\phi} (\land E_1) \quad \frac{\phi \land \psi}{\psi} (\land E_2) \
\frac{[\phi] \cdots \psi}{\phi \to \psi}(\to I) \quad \frac{\phi \quad \phi \to \psi}{\psi} (\to E) \
\frac{\bot}{\phi} (\bot) \quad \frac{[\neg \phi] \cdots \bot}{\phi} (\text {RAA})
$$ -
Let $\Gamma$ be a set of propositions, $\Gamma \vdash \phi$ means $\phi$ is derivable from $\Gamma$.
if $\Gamma = \varnothing$, we write $\vdash \phi$, which means $\phi$ is a theorem.
Completeness
- Soundness: $\Gamma \vdash \phi \Rightarrow \Gamma \vDash \phi$.
- Completeness Theorem: $\Gamma \vdash \phi \Leftrightarrow \Gamma \vDash \phi$.
Predicate Logic
-
Alphabet:
- predicate symbols: $P_1,\cdots,P_n$,
-
function symbols: $f_1,\cdots,f_m$,
-
constant symbols: $c_i(\forall i \in I)$,
-
variables: $x_i(\forall i \in \N)$,
-
bot: $\bot$,
-
not: $(\lnot)$,
-
connectives $\square$: $\land,(\lor),\to,(\leftrightarrow)$,
-
quantifiers: $\forall,(\exist)$,
-
auxiliary symbols: $(,)$,
-
abbreviations:
$$
\lnot \phi \coloneqq (\phi \to\bot) \ \phi \lor \psi \coloneqq \lnot(\lnot \phi \land \lnot \psi) \ \phi \leftrightarrow \psi \coloneqq (\phi \to \psi) \and (\psi \to \phi) \
\exist x_i, \phi \coloneqq \lnot(\forall x_i, \lnot \phi)
$$
-
The set $TERM$ of terms is the smallest set with the properties:
- $\forall i \in I$, $c_i \in TERM$,
- $\forall i \in \N$, $x_i \in TERM$,
- $\forall i = 1,\cdots m$, $t_1,\cdots,t_{a_i} \in TERM \Rightarrow f_i(t_1,\cdots,t_{a_i}) \in TERM$.
- The set $FORM$ of formulas is the smallest set with the properties:
- $\forall i = 1,\cdots,n$, $t_1,\cdots,t_{r_i} \in TERM \Rightarrow P_i(t_1,\cdots,t_{r_i}) \in FORM$,
- $\bot \in FORM$,
- $\phi \in FORM\Rightarrow \lnot \phi \in FORM$,
- $\phi,\psi \in FORM\Rightarrow (\phi\square\psi) \in FORM$.
- $\phi \in FORM \Rightarrow (\forall x_i, \phi),(\exist x_i, \phi) \in FORM$.
- Free variables: $(\forall x_i, \phi)$ contains $x_i$ bound.
-
Substitution:
$$
y[t/x] \coloneqq \begin{cases}y\quad y \ne x \ z \quad y = x\end{cases}
$$
Semantics
- A mapping $v : PROP \rightarrow {0,1}$:
$$
v(\bot) = 0 \
v(\phi \land \psi) = \min(v(\phi), v(\psi)) \
v(\phi \lor \psi) = \max(v(\phi), v(\psi)) \
v(\phi \to \psi) = 0 \Leftrightarrow v(\phi) = 1 \operatorname{and} v(\psi) = 0 \
v(\forall x,\phi(x)) = \min_x(\phi(x)) \
v(\exist x, \phi(x)) = \max_x(\phi(x))
$$
Natural Deduction
- We adopt all the rules of propositional logic and we add:
$$
\frac{\phi(x)}{\forall x,\phi(x)}(\forall I)\quad \text{where $x$ is bound.}
\
\frac{\forall x,\phi(x)}{\phi(t)}(\forall E)\quad \text{where $t$ is free.}
$$
一致性与完备性
- Godel 第一定理:任何一致的形式系统,只要蕴涵皮亚诺算术公理,就可以在其中构造在体系中不能被证明的真命题,因此通过推理演绎不能得到所有真命题(即体系是不完备的)。
- Godel 第二定理:任何逻辑自洽的形式系统,只要蕴涵皮亚诺算术公理,它就不能用于证明其本身的一致性。
代数
- 设 $A$ 是非空集合,映射 $A \times A \to A$ 称为 $A$ 上的一个代数运算。
群
- 对非空集合 $G$,若 $G$ 上代数运算满足结合律,就称 $G$ 是半群。
- 对半群 $G$,若 $G$ 中有幺元,就称 $G$ 是幺半群。
- 对幺半群 $G$,若 $G$ 中每个元素都有逆元,就称 $G$ 是群。
注记:这意味着群中有消去律。 - 对群 $G$,若 $G$ 上代数运算满足交换律,就称 $G$ 是交换群(或 Abel 群)。
- 对有限群 $G$,其元素个数称为阶,记作 $|G|$。
子群
-
对群 $G$,若 $G$ 的非空子集 $H$ 在 $G$ 上的代数运算下也构成一个群,就称 $H$ 是 $G$ 的子群,记作 $H \le G$。
$$
H \le G \Leftrightarrow \forall a,b \in H, ab^{-1} \in H
$$ -
对群 $G$,若 $G$ 的有限子集 $H$ 满足 $\forall a,b \in H, ab \in H$,则 $H \le G$。
-
对群 $G$,$G$ 中所有包含非空子集 $S$ 的子群中最小的称为 $S$ 生成的子群,记作 $\lang S\rang$。
$$
\lang S \rang = \left{\prod_{i=1}^{|S|} s_i^{m_i}: s_i \in S,m_i \in \Z\right}
$$ -
对群 $G$,设 $g \in G$,称最小的使 $g^n=1$ 的正整数 $n$ 为 $g$ 的阶,记为 $o(g)$。如果不存在这样的 $n$,则 $o(g) = \infty$。
称 $\lang g \rang$ 为 $g$ 生成的循环群。如果 $o(g)$ 有限,则
$$
\lang g \rang = {1,g,g^2,\cdots,g^{o(g)-1}}
$$ -
对群 $G$,$H \le G$,对 $a \in G$,称 $aH$ 为 $H$ 的一个左陪集,$Ha$ 为 $H$ 的一个右陪集。
$$
aH = bH \Leftrightarrow ab^{-1} \in H
$$
陪集分解:$H$ 的任意两个左(右)陪集相等或不交,$G$ 可以表示为若干个不交的左(右)陪集的并。 -
Lagrange 定理:对有限群 $G$,$H \le G$,则 $|H|\mid |G|$。
称 $H$ 在 $G$ 中的不同陪集个数为 $H$ 的指数,记作 $[G:H]$,则 $|G| = |H|[G:H]$。 -
定理:对素数 $p$,$p$ 的既约剩余系 $\Z_p^$ 是循环群。
证明:记 $g(d)$ 表示 $\Z_p^$ 中 $d$ 阶元个数。
若存在 $d$ 阶元 $a$,则
$$
\lang a \rang = {1,a,a^2,\cdots,a^{d-1}}
$$
又 $\lang a \rang$ 中 $d$ 个元素均满足 $x^d=1$,而 $x^d=1$ 的解至多只有 $d$ 个,故 $\lang a \rang$ 构成了 $x^d=1$ 的解集,因此所有 $d$ 阶元均在 $\lang a \rang$ 中,得到 $g(d) = \varphi(d)$,其中 $\varphi$ 是欧拉函数。
于是 $g(d)$ 要么为 $\varphi(d)$,要么为 $0$。由 Lagrange 定理,只有当 $d$ 为 $|\Z_p^|=p-1$ 的因数时,$g(d)$ 才可能不为 $0$。因此有
$$
p-1 = \sum_{d=1}^{p-1} g(d) = \sum_{d \mid p-1} g(d) \le \sum_{d \mid p-1} \varphi(d) = p – 1
$$
故当 $d | p-1$ 时,$g(d) = \varphi(d)$。特别地,$g(p-1) = \varphi(p-1)$,故存在 $p-1$ 阶元(称为原根),所以 $\Z_p^$ 是循环群。 -
Wilson 定理:对素数 $p$,$(p-1)! \equiv -1 \pmod p$。
证明:由 $\Z_p^*$ 是循环群,有
$$
(p-1)! = \prod_{i=0}^{p-2} g^i = g^{\frac{p-1}2}
$$
注意到 $g^{\frac{p-1}2}$ 是二阶元,而二阶元只有 $\varphi(2) = 1$ 个,它就是 $-1$。 -
对群 $G$,$C = {c \in G: \forall g \in G, cg = gc}$ 称为 $G$ 的中心,$C \le G$。
对 $x \in G$,$C_x = {gxg^{-1}:g \in G}$ 称为 $x$ 的共轭类。
有限群的类方程:$|G| = |C| + \sum |C_i|$,其中 $C_i$ 是所有不止一个元素的共轭类。
同态与同构
-
对群 $G,H$,映射 $\sigma:G\to H$ 称为同态,若
$$
\forall x,y \in G, \sigma(x)\sigma(y) = \sigma(xy)
$$
如果同态 $\sigma$ 是双射,就称它是同构,记作 $G \cong H$。 -
对同态 $\sigma : G \to H$,同态核 $\ker \sigma \coloneqq {g \in G: \sigma(g) = 1_H}$。
称 $\ker \sigma$ 的所有陪集构成的群为 $G$ 模 $\ker \sigma$ 的商群,记作 $G/\ker \sigma$。 -
对群 $G$,$H \le G$,称 $H$ 为正规子群,若
$$
\forall a \in G, aH = Ha
$$
记作 $H \lhd G$。
$$
H \lhd G \Leftrightarrow \forall g \in G, h \in H, ghg^{-1} \in H
$$
考虑典范同态 $\sigma : G \to G/H : g \mapsto gH$,则 $\ker \sigma = H$。 -
同态基本定理:对同态 $\sigma : G \to H$,$G / \ker \sigma \cong \operatorname{im} \sigma$。
-
循环群分类定理:无限循环群都同构于 $\Z$,$n$ 阶循环群都同构于 $\Z_n$。
直积
- 对群 $G_1,G_2$,$G = G_1 \times G_2$ 在运算 $(g_1,g_2)(g_1^\prime, g_2^\prime) \coloneqq (g_1g_1^\prime,g_2g_2^\prime)$ 下构成群,称 $G$ 为 $G_1,G_2$ 的外直积。
- 对群 $G$,$G_1,G_2$ 是 $G$ 的正规子群,且 $G = G_1G_2$,$G_1 \cap G_2 = {1}$,则称 $G$ 为 $G_1,G_2$ 的内直积。
- 外直积和内直积在同构意义下是一致的。
环
-
对非空集合 $R$,若 $R$ 上有两种代数运算加法 $+$ 和乘法 $\cdot$,且满足:
- $(R,+)$ 构成交换群;
- $(R,\cdot)$ 构成半群;
- 乘法分配律:$a(b+c) = ab+ac$,$(b+c)a = ba+ca$;
就称 $R$ 是环。
-
对环 $R$,若 $(R \setminus {0}, \cdot)$ 构成群,就称 $R$ 为除环。
-
对环 $R$,若乘法是可交换的,就称 $R$ 为交换环。
-
交换除环称为域。
-
无零因子的交换环称为整环。域一定是整环,有限整环是域。
-
对环 $R$,若 $R$ 的非空子集 $S$ 在 $R$ 上的代数运算下也构成一个环,就称 $S$ 是 $R$ 的子环。
$S$ 是 $R$ 的子环当且仅当 $\forall x,y \in S, x – y \in S, xy \in S$。
理想
-
对环 $R$,称加法子群 $S \sube R$ 为理想,若 $\forall r \in R$,$rS,Sr \sube S$。
-
对环 $R$,$R$ 中所有含 $a \in R$ 的最小理想称为 $a$ 生成的主理想,记作 $(a)$。
$$
(a) = \left{ \sum_{i=1}^k r_ias_i:r_i,s_i \in R, k \in \N\right}
$$
若环 $R$ 的理想都是主理想,就称 $R$ 是主理想环。 -
$\Z$ 是主理想整环。
-
对环 $R$,$I$ 是 $R$ 的理想,称 $I$ 的所有加法陪集构成的环为 $R$ 模 $I$ 的商环,记作 $R/I$。
考虑典范同态 $\sigma : R \to R/I : r \mapsto r + I$,则 $\ker \sigma = I$。 -
对环 $R$,$I,J$ 是 $R$ 的理想,定义理想的乘法
$$
IJ \coloneqq \left{ \sum_{i=1}^k a_ib_i:a_i \in I, b_i \in J, k \in \N \right}
$$
则 $IJ \sube I \cap J \sube I + J$ 且均为 $R$ 的理想。
唯一分解整环 (UFD),主理想整环 (PID),欧几里得整环 (ED)
-
$\Z(\sqrt{-5}) \coloneqq {m+n\sqrt{-5}:m,n \in \Z }$ 不是唯一分解整环。考虑
$$
9=3\cdot 3 = (2 + \sqrt{-5})(2-\sqrt{-5})
$$ -
对整环 $R$,$R$ 是唯一分解整环当且仅当 $R$ 满足因子链条件和素性条件。
- 因子链条件:$R$ 中不存在无限序列 $a_1,a_2,\cdots$ 使得 $a_{i+1}$ 是 $a_i$ 的真因子。
- 素性条件:$R$ 中的任何不可约元 $p$ 满足 $(p \mid ab) \Rightarrow (p \mid a) \or (p \mid b)$。
- 对整环 $R$,若存在 $\delta:R \setminus {0} \to \N$ 满足:
- 若 $a,b \in R$ 且 $b \ne 0$,则 $\exist q,r \in R$ 使得 $a = bq+r$,且或者 $r = 0$ 或者 $\delta(r) < \delta(b)$;
- 若 $a,b \in R \setminus {0}$,则 $\delta(a) \le \delta(ab)$;
则称 $R$ 是欧几里得整环。
-
定理:$\text{ED} \Rightarrow \text{PID} \Rightarrow \text{UFD}$。
有限域
-
对域 $F$,使得 $n \times 1 = 0$ 的最小正整数 $n$ 称为域的特征,记为 $\operatorname{char}(F)$。特别地,如果不存在这样的正整数,则 $\operatorname{char}(F) = 0$。
-
域的特征要么是 $0$,$\Q$ 是最小的特征为 $0$ 的域;要么是素数 $p$,$\Z_p$ 是最小的特征为 $p$ 的域。$\Q$ 和 $\Z_p$ 统称素域。
-
定理:对域 $F$,多项式环 $F[x]$ 是主理想整环。
关键:取 $F[x]$ 的非平凡理想 $I$ 中次数最小的非零多项式 $g(x)$,则 $I = (g(x))$。 -
定理:对域 $F$,$F[x]/(f(x))$ 是域当且仅当 $f(x)$ 是 $F[x]$ 中的不可约多项式,且有 $|F[x]/(f(x))| = |F|^{\deg f}$。
关键:$f(x)$ 可约可推出 $F[x]/(f(x))$ 非整环,故必要性成立。由 Bézout 定理可找到非零元的逆元,故充分性成立。$F[x]/(f(x))$ 的每个等价类都可唯一地用一个次数小于 $\deg f$ 的多项式作为代表元,故等式成立。 -
定理:存在且在同构意义下仅存在唯一阶为 $p^n$ 的有限域,其中 $p$ 为素数,$n \in \N$;不存在其他阶的有限域。
Information Theory
Entropy
Definition 1 (Entropy).
$$
H(X)= \mathbb E\left(\log \frac{1}{P(X)}\right) = \sum_{x \in \mathcal X} P(x)\log \frac{1}{P(x)}.
$$
Example (Bernoulli and Geometric distribution).
- Let $X \sim \operatorname{Bernoulli}(p)$, with $P(1) = p$ and $P(0) = 1-p$. Then,
$$
h(p) \triangleq H(X) = p\log\frac 1p + (1-p) \log \frac 1{1-p}.
$$ -
Let $X$ be geometrically distributed, with $P(i) = p(1-p)^i, i = 0,1,\cdots$. Then,
$$
H(X) = \mathbb E\left(\log \frac 1{p(1-p)^X}\right) = \log \frac 1p + \mathbb E(X) \log \frac 1{1-p} = \log \frac 1p + \left(\frac 1p – 1\right) \log \frac 1{1-p} = \frac{h(p)}p.
$$
Definition 2 (Joint entropy).
$$
H(X^n)= H(X_1,X_2,\cdots,X_n)=\mathbb E\left(\log \frac{1}{P(X_1,X_2,\cdots,X_n)}\right) = \sum_{{x_1,x_2,\cdots,x_n} \in \mathcal X} P(x_1,x_2,\cdots,x_n)\log \frac{1}{P(x_1,x_2,\cdots,x_n)}.
$$
Definition 3 (Conditional entropy).
$$
H(X|Y)= \mathbb E\left(\log \frac{1}{P(X|Y)}\right) = \sum_{{x,y} \in \mathcal X} P(x,y)\log \frac{1}{P(x|y)}.
$$
Theorem 4 (Jensen’s inequality). Let $f$ be a convex function. Then,
$$
f(\mathbb E(X)) \le \mathbb E(f(X)).
$$
Theorem 5 (Properties of entropy).
- Positivity:
$$
H(X) \ge 0,
$$
with equality iff $X$ is a constant. -
Uniform distribution maximizes entropy: For finite $\mathcal X$, $H(X) \le \log |\mathcal X|$, with equality iff $X$ is uniform on $\mathcal X$.
Proof. Notice that $x \mapsto \log x$ is concave. Then apply Jensen’s inequality,
$$
H(X)= \mathbb E\left(\log \frac{1}{P(X)}\right) \le \log\mathbb E \left(\frac{1}{P(X)}\right) = \log |\mathcal X|.
$$ -
Conditioning reduces entropy: $H(X|Y) \le H(X)$, with equality iff $X$ and $Y$ are independent.
Proof. Notice that $x \mapsto x \log \frac 1x$ is concave. Then apply Jensen’s inequality,
$$
H(X|Y) = \sum_{x \in \mathcal X} \mathbb E_Y \left(P(x|Y) \log \frac{1}{P(x|Y)}\right) \le \sum_{x \in \mathcal X} P(x) \log \frac{1}{P(x)} = H(x).
$$ -
Chain rule:
$$
H(X,Y) = H(X) + H(Y|X) \le H(X) + H(Y); \quad
H(X^n) = \sum_{i=1}^n H(X_i|X^{i-1}) \le \sum_{i=1}^nH(X_i).
$$
Proof.
$$
H(X,Y) = \mathbb E\left(\log \frac{1}{P(X,Y)}\right) = \mathbb E\left(\log \frac{1}{P(X)P(Y|X)}\right) = \mathbb E\left(\log \frac{1}{P(X)}\right) + \mathbb E\left(\log \frac{1}{P(Y|X)}\right) = H(X) +H(Y|X).
$$
Divergence (Relative entropy)
Definition 1 (Kullback-Leibler (KL) Divergence).
$$
D(P | Q)=\sum_{x \in \mathcal{X}} P(x) \log \frac{P(x)}{Q(x)}= \mathbb E_{X\sim P(X)}\left(\log \frac{P(X)}{Q(X)}\right)= \mathbb E_{X\sim Q(X)}\left(\frac{P(X)}{Q(X)}\log \frac{P(X)}{Q(X)}\right).
$$
Example (Binary divergence). Consider $P = \operatorname{Bernoulli}(p)$ and $Q = \operatorname{Bernoulli}(q)$. Then,
$$
d(p|q) \triangleq D(P | Q) = p \log \frac pq + (1-p) \log \frac{1-p}{1-q}.
$$
Theorem 2 (Entropy vs Divergence). For finite $\mathcal X$,
$$
H(P) = \log |\mathcal X| – D(P|U_{\mathcal X}),
$$
where $U_{\mathcal X}$ is the uniform distribution on $\mathcal X$.
Proof.
$$
D(P|U_{\mathcal X}) = \mathbb E_{X\sim P(X)}\left(\log \frac{P(X)}{U_{\mathcal X}(X)}\right) = \mathbb E_{X\sim P(X)}\left(\log \frac{1}{U_{\mathcal X}(X)}\right) – \mathbb E_{X\sim P(X)}\left(\log \frac{1}{P(X)}\right) = \log|\mathcal X| – H(P).
$$
Definition 3 (Conditional divergence).
$$
D(P_{Y|X}|Q_{Y|X}|P_X) = \mathbb E_{X \sim P_X(X)}(D(P_{Y|X}|Q_{Y|X})) = \sum_{x \in \mathcal X}P_X(x)D(P_{Y|x}|Q_{Y|x}).
$$
Theorem 4 (Properties of divergence).
- Information inequality:
$$
D(P|Q) \ge 0,
$$
with equality iff $P = Q$.
Proof. Notice that $x \mapsto x \log x$ is convex. Then apply Jensen’s inequality,
$$
D(P | Q)=\mathbb E_{X\sim Q(X)}\left(\frac{P(X)}{Q(X)}\log \frac{P(X)}{Q(X)}\right) \ge 1 \log 1 = 0.
$$ -
Chain rule:
$$
D(P_{X,Y}|Q_{X,Y}) = D(P_{Y|X}|Q_{Y|X}|P_X) + D(P_X|Q_X); \quad D(P_{X^n}| Q_{X^n}) = \sum_{i=1}^n D(P_{X_i|X^{i-1}}|Q_{X_i|X^{i-1}}|P_{X^{i-1}}).
$$
Proof.
$$
D(P_{X, Y} | Q_{X, Y})
=\mathbb{E}\left(\log \frac{P_{X, Y}(X, Y)}{Q_{X, Y}(X, Y)}\right)
=\mathbb{E}\left(\log \frac{P_{Y|X}(Y|X)}{Q_{Y|X}(Y|X)}\right)+\mathbb{E}\left(\log \frac{P_X(X)}{Q_X(X)}\right)
= D(P_{Y|X}|Q_{Y|X}|P_X) + D(P_X|Q_X).
$$ -
Conditional divergence can be expressed unconditionally:
$$
D(P_{Y|X}|Q_{Y|X}|P_X) = D(P_XP_{Y|X}|P_XQ_{Y|X}).
$$
Proof. Apply chain rule to $P_X = Q_X$. -
Monotonicity:
$$
D(P_{X,Y}| Q_{X,Y}) \ge D(P_X|Q_X).
$$ -
Tensorization: Consider chain rule in the special case of $Q_{X^n} = \prod_{i=1}^n Q_{X_i}$,
$$
D(P_{X^n}| Q_{X^n}) = D(P_{X^n}| Q_{X_1}Q_{X_2}\cdots Q_{X_n})
= D(P_{X^n}| P_{X_1}P_{X_2}\cdots P_{X_n}) + \sum_{i=1}^n D(P_{X_i} | Q_{X_i}) \ge \sum_{i=1}^n D(P_{X_i} | Q_{X_i}),
$$
with equality iff $P_{X^n} = \prod_{i=1}^n P_{X_i}$. -
Conditioning increases divergence: Let $P_Y = P_{Y|X} \circ P_X$ and $Q_Y = Q_{Y|X} \circ P_X$. Then,
$$
D(P_Y|Q_Y) \le D(P_{Y|X} |Q_{Y|X}|P_X),
$$
with equality iff $D(P_{X|Y} |Q_{X|Y}|P_Y) = 0$.
Proof.
$$
\begin{aligned}
D(P_{X, Y} | Q_{X, Y}) & =D(P_{Y | X} | Q_{Y | X} | P_X)+\underbrace{D(P_X | P_X)}{=0} \
& =D(P{X | Y} | Q_{X | Y} | P_Y)+D(P_Y | Q_Y) .
\end{aligned}
$$ -
Data-Processing Inequality (DPI) for KL divergence. Let $P_Y = P_{Y|X} \circ P_X$ and $Q_Y = P_{Y|X} \circ Q_X$. Then,
$$
D(P_Y| Q_Y) \le D(P_X | Q_X),
$$
with equality iff $D(P_{X|Y}| Q_{X|Y}|P_Y) = 0$.
Proof.
$$
\begin{aligned}
D(P_{X, Y} | Q_{X, Y}) & =\underbrace{D(P_{Y | X} | Q_{Y | X} | P_X)}{=0}+D(P_X | Q_X) \
& =D(P{X | Y} | Q_{X | Y} | P_Y)+D(P_Y | Q_Y) .
\end{aligned}
$$
Mutual information
Definition 1 (Mutual information).
$$
I(X;Y) = D(P_{X,Y}|P_XP_Y).
$$
Theorem 2 (Properties of mutual information).
- Mutual information as conditional divergence:
$$
I(X;Y) = D(P_{Y|X}|P_Y|P_X).
$$ -
Symmetry:
$$
I(X;Y)=I(Y;X).
$$ -
Positivity:
$$
I(X;Y)\ge 0,
$$
with equality iff $X \perp !!!! \perp Y$. -
More data, more information:
$$
I(X,Y;Z) \ge I(X;Z).
$$
Theorem 3 (Mutual information and entropy).
$$
I(X;Y) = H(X) – H(X|Y)=H(X)+H(Y)-H(X,Y).
$$
Definition 4 (Conditional mutual information).
$$
I(X;Y|Z) = D(P_{X,Y|Z}|P_{X|Z}P_{Y|Z}|P_Z)
$$
Theorem 5 (Further properties of mutual information).
- Positivity:
$$
I(X;Z|Y) \ge 0,
$$
with equality iff $X \to Y \to Z$. -
Chain rule:
$$
I(X,Y;Z) = I(X;Z)+I(Y;Z|X); \quad
I(X^n;Y) = \sum_{i=1}^nI(X_i;Y|X^{i-1}).
$$ -
DPI for mutual information: Let $X \to Y \to Z$. Then,
$$
I(X;Z) \le I(X;Y),
$$
with equality iff $X \to Z \to Y$.
Probability Theory
Chernoff bounds
Chebyshev’s and Markov’s Inequality
Theorem 1 (Chebyshev’s Inequality). Let $X$ be a random variable. Then $\forall a>0$,
$$
\mathbb P(|X-\mathbb E(X)| \ge a) \le \frac{\mathbb D(X)}{a^2}.
$$
Theorem 2 (Markov’s Inequality). Let $X$ be a non-negative random variable. Then $\forall a>0$,
$$
\mathbb P(X \ge a) \le \frac{\mathbb E(X)}{a}.
$$
Proof.
$$
\mathbb E(X) = \sum_{x \ge a} p(x)\cdot x + \sum_{0 \le x < a} p(x)\cdot x \ge \sum_{x \ge a} p(x)\cdot x \ge a\cdot \sum_{x \ge a} p(x) = a\cdot \mathbb P(X \ge a).
$$
Proof of Theorem 1. Apply Markov’s Inequality to $(X – \mathbb E(X))^2$. Notice that
$$
\mathbb D(X) = \mathbb E((X – \mathbb E(X))^2).
$$
Remark. Markov’s and Chebyshev’s Inequality are essentially tight for a general random variable.
Deviation of a sum on independent random variables
Theorem 3. Let $X_1,X_2,\cdots,X_n$ be independent random variables with $\mathbb E(X_i) = \mu_i$ and $\mathbb D(X_i) = \sigma_i^2$. Then $\forall a>0$,
$$
\mathbb P\left(\left|\sum_{i=1}^n X_i – \sum_{i=1}^n \mu_i\right| \ge a\right) \le \frac{\sum_{i=1}^n \sigma_i^2}{a^2}.
$$
In particular, for identically distributed random variables with expectation $\mu$ and variance $\sigma^2$,
$$
\mathbb{P}\left(\left|\frac{\sum_{i=1}^n X_i}{n}-\mu\right| \geq \epsilon\right) \leq \frac{\sigma^2}{n \epsilon^2}.
$$
Proof. Apply Chebyshev’s Inequality to $\sum_{i=1}^n X_i$. Notice that
$$
\mathbb D\left(\sum_{i=1}^n X_i\right) = \sum_{i=1}^n \mathbb D(X_i).
$$
Remark. Theorem 3 is tight when all the variables are just guaranteed to be pairwise independent.
Chernoff Bound
Theorem 4 (Chernoff Bound of independent Bernoulli trials). Let $X = \sum_{i=1}^n X_i$, where $X_i=1$ with probability $p_i$ and $X_i = 0$ with probability $1-p_i$, and all $X_i$ are independent. Let $\mu = \mathbb E(X) = \sum_{i=1}^n p_i$. Then,
- Upper Tail: $\forall \delta > 0$,
$$
\mathbb P(X \ge (1+\delta)\mu) \le e^{-\mu\delta^2/(2+\delta)};
$$ -
Lower Tail: $\forall \delta \in (0,1)$,
$$
\mathbb P(X \le (1-\delta)\mu) \le e^{-\mu\delta^2/2}.
$$
Corollary 5. $\forall \delta \in (0,1)$,
$$
\mathbb P(|X – \mu| \ge \delta\mu) \le 2e^{-\mu\delta^2/3}.
$$
Example (coin tossing). Suppose we have a fair coin. Repeatedly toss the coin, and let $S_n$ be the number of heads from the first $n$ tosses.
Theorem 3 tells us that
$$
\mathbb{P}(|S_n/n-1/2| \geq \epsilon) \leq \frac{1}{4n \epsilon^2}.
$$
Taking $\epsilon = 1/4$, we obtain $\mathbb{P}(|S_n/n-1/2| \geq 1/4) \leq 4/n$.
But Corollary 5 tells us that
$$
\mathbb P(|S_n – n/2| \ge \delta n/2) \le 2e^{-n\delta^2/6}.
$$
Taking $\delta = 1/2$, we obtain $\mathbb{P}(|S_n/n-1/2| \geq 1/4) \leq 2e^{-n/24}$, which is a massive improvement.
Discrete Fourier transform (DFT)
Definition.
$\Z_N$:
$$
\mathcal F:X_k = \frac1N \sum_{n=0}^{N-1}e^{-i 2\pi kn/N}x_n = \frac1N \sum_{n=0}^{N-1}\omega_{N}^{-kn}x_n, \quad
\mathcal F^{-1}:x_n = \sum_{k=0}^{N-1} e^{i2\pi kn/N}X_k = \sum_{k=0}^{N-1} \omega_{N}^{kn}X_k.
$$
$(\Z_2)^n$:
$$
\mathcal F : X_x = \frac{1}{2^n} \sum_{a} (-1)^{\operatorname{bitcount}(x \and a)}x_a, \quad
\mathcal F^{-1} : x_a =\sum_{x} (-1)^{\operatorname{bitcount}(x \and a)}X_x.
$$