离散数学与结构 课程笔记

作者: xht37 分类: 笔记 发布时间: 2023-10-15 03:14

Visits: 5446

授课教师:刘天任

第一次学这些内容,难免有不严谨甚至错误之处,欢迎批评指正!

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.
$$

发表评论

电子邮件地址不会被公开。 必填项已用*标注