数学基础系列：集合与数

作者: Boye0212 | 来源:发表于2021-05-25 00:30 被阅读0次

数学基础系列：集合与数
数学对象是否存在？（1）
目录 - 数学基础
高中数学（从集合到排列）
Java集合源码分析系列文章
数据结构之集合和映射
第16章集合类
C#集合与泛型
读书笔记-2019-01-25
如何让孩子理解什么是11？

本文旨在整理一些集合论中的基础概念与定理，主要出处见参考文献。

本文只列出特别简单的证明，略去复杂的证明。

1 集合论基础

首先，我们介绍Cartesian product（笛卡尔积、直积） $A\times B$ ，就是从 $A$ 中、 $B$ 中各取一个元素组成的有序数对。如果是 $n$ 个集合，它们的Cartesian product就是一个 $n$ -tuples：
$\times_{i=1}^n A_i = \{(a_1,\ldots,a_n):a_i\in A_i,i=1,\ldots,n\}$

所谓Relation（关系），是 $A\times A$ 的任一子集，就叫a relation $R$ on set $A$ 。如果 $(x,y)\in R$ ，则可写为 $xRy$ 。 $R$ 可能的性质有：

Reflexive（自反性）： $xRx$ ；
Symmetric（对称性）：若 $xRy$ 则必有 $yRx$ ；
Antisymmetric（反对称）：若 $xRy$ 且 $yRx$ ，则必有 $x=y$ ；
Transitive（传递性）：若 $xRy$ 且 $yRz$ ，则必有 $xRz$ 。

Equivalence relation（等价关系），就是自反、对称、传递的关系。

给定 $A$ 上的一个equivalence relation $R$ ，那么 $A$ 中的元素 $x$ 的equivalence class（等价类），就是集合 $E_x = \{y\in A:xRy\}$ 。若 $E_x$ 和 $E_y$ 是 $x$ 和 $y$ 的等价类，那么必有 $E_x\cap E_y=\empty$ 或 $E_x=E_y$ 。

自反、反对称、传递的relation，就叫partial ordering（偏序），可以用符号 $\geq$ 或 $\leq$ 表示。对于任意partial ordering，如果将其中的 $(x,x)$ 元素剔除，就变成了strict ordering，用符号 $\gt$ 或 $\lt$ 表示，这种relation不再是自反的和反对称的，但依旧有传递性。如果对于集合 $A$ ，每一对 $(x,y)\in A\times A$ 都满足 $x\lt y$ 、 $x\gt y$ 或 $x=y$ 这三种中的一种，那么称 $A$ 是linearly ordered。再进一步，定义集合 $A$ 的最小元素为 $a\in A$ ，它满足 $\forall x\in A, a\leq x$ （最大元素可类似定义），那么，如果linearly ordered $A$ 的每一个子集都有一个最小元素，则称 $A$ 是well-ordered。

一个mapping/transformation/function定义为 $T:X\mapsto Y$ ，这是一种将 $X$ 中的每个元素与 $Y$ 中唯一一个元素联系起来的规则。 $X$ 称为domain（定义域）， $Y$ 为codomain（到达域），集合 $G_T=\{(x,y):x\in X,y=T(x)\}\subseteq X\times Y$ 称为graph of $T$ 。集合 $T(A)=\{T(x):x\in A\}\subseteq Y$ 称为 $A$ 在 $T$ 下的image，对于 $B\subseteq Y$ ，集合 $T^{-1}(B)=\{x:T(x) \in B\}\subseteq X$ 称为 $B$ 在 $T$ 下的inverse image。集合 $T(X)$ 称为 $T$ 的range（值域），若 $T(X)=Y$ 则称该mapping为from $X$ onto $Y$ ，中文叫满射，否则是into $Y$ 。若每个 $y$ 都是唯一的 $x\in X$ 的image，则该mapping是one-to-one，或记为 $1$ - $1$ ，中文叫单射。

当 $X$ 中的每个元素与 $Y$ 中不一定唯一的元素对应起来的规则，称为correspendence， $T^{-1}$ 就是一个correspendence，但未必是mapping。若mapping是 $1$ - $1$ 且是onto的，则称该mapping为one-to-one correspendence。如果在 $X$ 和 $Y$ 上都定义了partial ordering，那么如果对于一个mapping， $T(x_1)\leq T(x_2)$ 当且仅当 $x_1\leq x_2$ ，就称该mapping为order-preserving。若 $X$ 是partial ordered，用 $\leq$ 表示，那么一个 $1$ - $1$ mapping可以induce（诱导）在codomain上的一个partial ordering。若这个mapping还是onto，那么 $X$ 上的linear ordering可以induce一个 $Y$ 上的linear ordering。

集合中的元素个数称为集合的cardinality或cardinal number（基数）。若 $A$ 与 $B$ 之间存在 $1$ - $1$ correspondence，那么两个集合equipotent（等势）。

2 可数集合

将正自然数集合 $N^+$ 的cardinal number记为 $\aleph$ 。如果一个无限集合中的元素，与 $N^+$ 中的元素存在 $1-1$ correspondence，那么称该集合为countable或denumerable（可数的）。

整数集 $Z$ 是可数的，因为对于任意 $n\in N^+$ ，让它对应于 $\lfloor n/2\rfloor (-1)^n\in Z$ 即可。

定理：有理数集 $Q$ 可数。

定理：The union of a countable collection of countable sets is a countable set.

注：Collection有的地方翻译为“搜集”，可理解为允许有重复元素的集合。

3 实数连续统

定理：实数集 $R$ 是不可数的。

记 $R$ 的cardinal number为 $c$ ，则有 $\aleph<c$ 。

定理：任意开区间不可数。

定理：任意开区间与 $R$ 是equipotent的。

对于开区间 $(a,b)$ ，将任意 $x\in R$ 映射为 $y=\dfrac{a+b}{2}+\dfrac{(b-a)x}{2(1+|x|)}$ 可证。

定理：实数平面 $R^2=R\times R$ 与 $R$ 是equipotent的。

定理：任意开区间都包含至少一个有理数。

对于开区间 $(a,b)$ ，不妨假设 $a\geq 0$ ，取 $q$ 为比 $1/(b-a)$ 大的最小整数，取 $p$ 为比 $qb$ 大的最小整数，则必有 $(p-1)/q \in (a,b)$ ，而 $(p-1)/q \in Q$ 。

推论：Every collection of disjoint open intervals is countable.

因为每个开区间都至少包含一个有理数，这些不相连的开区间的collection可用其中每个开区间中的任一有理数建立对应关系，而有理数集是可数的。

下面再介绍一些有关集合的定义。集合 $A\subset R$ 的supremum，如果存在，就是对于任意 $x\in A$ 都满足 $x\leq y$ 的最小的 $y$ ，可写为 $\sup A$ ；反之可定义集合 $A$ 的infimum，写为 $\inf A$ 。对于 $R$ 的某个子集，如果有上界，必有supremum，如果有下界，必有infimum。若定义extended real line $\bar R=R\cup \{-\infty,+\infty\}$ （即将无穷大也看作一个元素），那么所有集合都有supremum和infimum。另外记 $\bar R^+=R\cup\{+\infty\}$ 。

4 集合的序列

Monotone sequence（单调序列）就是non-decreasing（指 $\forall n, A_n\subseteq A_{n+1}$ ）或non-increasing指 $\forall n, A_{n}\supseteq A_{n+1}$ ）的序列，也有严格的单调序列，即将包含关系换成严格包含关系 $\subset$ 和 $\supset$ 。

序列的limit（极限） $A$ ，就是对于non-decreasing序列的 $A=\cup_{n=1}^{\infty}A_n$ ，或对于non-increasing序列的 $A=\cap_{n=1}^{\infty}A_n$ ，分别可写为 $A_n\uparrow A$ 和 $A_n\downarrow A$ ，或一般地， $\lim\limits_{n\to\infty}A_n = A$ ，或 $A_n\to A$ 。

对于任意集合序列 $\{A_n\}$ ，集合 $B_n=\cup_{m=n}^{\infty}A_m$ 必为non-increasing序列，因此 $B=\lim\limits_{n\to\infty}B_n$ 存在，称它为 $\{A_n\}$ 的superior limit，写为 $\limsup_n A_n$ 。反之，non-decreasing序列 $C_n=\cap_{m=n}^{\infty}A_m$ 的极限 $C$ ，就是 $\{A_n\}$ 的inferior limit，写为 $\liminf_n A_n$ 。正式定义为
$\begin{aligned} \limsup_n A_n = \cap_{n=1}^\infty (\cup_{m=n}^\infty A_m)\\ \liminf_n A_n = \cup_{n=1}^\infty (\cap_{m=n}^\infty A_m) \end{aligned}$
由De Morgan' s laws， $\liminf_n A_n = \left(\limsup_n A_n^c \right)^c$ 。

$\limsup_n A_n$ 其实就是infinitely many（无穷多）个 $A_n$ 中都含有的元素的集合， $\liminf_n A_n$ 就是all but a finite number（除有限）个 $A_n$ 外，其他 $A_n$ 中都含有的元素的集合。

以上概念提供了一种集合序列的收敛准则： $\liminf_n A_n\subseteq \limsup_n A_n$ ，若两个集合不相等，则说明 $\{A_n\}$ 不收敛。

5 子集的类

所有 $X$ 的子集的集合成为 $X$ 的power set（幂集），记为 $2^X$ 。对于一个countable set，认为它的power set有 $2^\aleph$ 个元素。

定理： $2^\aleph = c$ 。

接下来，要研究的是给定集合的子集的一些性质。Power set一般对研究的问题来说会显得太大了，以下的一系列定义，目的是要定义出 $2^X$ 的某个子集，使得该子集对于研究的问题来说足够大，而其性质又让我们可以容易地处理。一般方法是，先选出一些已知性质的集合，组成一个基本的collection，再用一些特定操作，创造出新的集合加入其中。

定义 Ring（环）：由集合 $X$ 的子集组成的非空类（nonempty class） $\mathscr{R}$ ，若满足如下性质则为ring：

$\empty\in\mathscr{R}$ ；
若 $A\in\mathscr{R}$ 且 $B\in\mathscr{R}$ ，则 $A\cup B\in \mathscr{R}$ ， $A\cap B\in \mathscr{R}$ ， $A- B\in \mathscr{R}$ 。

Ring对于union、intersection、difference的操作是closed（闭的）。但ring中不一定含有全集 $X$ 自身，若加入 $X$ ，就成了field（或algebra）定义：

定义 Field（域）：由 $X$ 的子集组成的class $\mathscr{F}$ ，若满足如下性质则为field：

$X\in\mathscr{F}$ ；
若 $A\in\mathscr{F}$ ，则 $A^c\in\mathscr{F}$ ；
若 $A\in\mathscr{F}$ 且 $B\in\mathscr{F}$ ，则 $A\cup B\in \mathscr{F}$ 。

如果给定了一个collection $\mathscr{C}$ ，将它理解为“种子”，去生成field，那么称最小的含有 $\mathscr{C}$ 的field为field generated by $\mathscr{C}$ 。

Ring和field的概念在概率论中应用起来还是会有些限制，因此引入以下定义：

定义 Semi-ring：由集合 $X$ 的子集组成的非空类（nonempty class） $\mathscr{S}$ ，若满足如下性质则为semi-ring：

$\empty\in\mathscr{S}$ ；
若 $A\in\mathscr{S}$ 且 $B\in\mathscr{S}$ ，则 $A\cap B\in \mathscr{S}$ ；
若 $A\in\mathscr{S}$ 、 $B\in\mathscr{S}$ 且 $A \subseteq B$ ，则 $\exist n\lt \infty$ ，使得 $B-A=\cup_{j=1}^{n} C_j$ ，其中 $C_j\in\mathscr{S}$ 且对于 $j\neq j'$ 来说 $C_j\cap C_{j'}=\empty$ 。

其中的第三个性质，简单来说就是 $\mathscr{S}$ 中任意两个集合的的差，可以分解为有限个 $\mathscr{S}$ 中集合的union。

再在semi-ring中加入 $X$ 自身，就变成了semi-algebra。

6 Sigma fields

上一节说到field对complement和finite union的操作是closed，我们接着将它的finite union操作扩展到极限处，这就有了如下概念。

定义 $\sigma$ -field（sigma-algebra）：由 $X$ 的子集组成的class $\mathscr{F}$ ，若满足如下性质则为sigma-field：

$X\in\mathscr{F}$ ；
若 $A\in\mathscr{F}$ ，则 $A^c\in\mathscr{F}$ ；
若 $\{A_n,n\in N^+\}$ 为 $\mathscr{F}$ 中的集合的序列，则 $\cup_{n=1}^{\infty} A_n\in \mathscr{F}$ 。

$\sigma$ -field对于complement和countable union是closed。若给定一个collection $\mathscr{C}$ ，所有含有 $\mathscr{C}$ 的 $\sigma$ -field的交集，就叫 $\sigma$ -field generated by $\mathscr{C}$ ，可记为 $\sigma(\mathscr{C})$ 。

定理：若 $\mathscr{C}$ 是一个finite collection，则 $\sigma(\mathscr{C})$ 也是finite，否则 $\sigma(\mathscr{C})$ 总是uncountable。

若取 $X=R$ ， $\mathscr{C}=\{(-\infty,r]: r\in Q\}$ ，则 $\sigma(\mathscr{C})$ 就叫Borel field of $R$ ，一般可记为 $\mathscr{B}$ 。许多不同的collection都可以生成出 $\mathscr{B}$ 。若给定一个实区间 $I$ ，则 $\mathscr{B}_I = \{B\cap I: B\in\mathscr{B}\}$ 称为the restnctlon of $\mathscr{B}$ to $I$ ，或Borel field on $I$ 。事实上， $\mathscr{B}_I$ 可由 $\mathscr{C}=\{(-\infty,r]\cap I: r\in Q\}$ 生成。

对于两个 $\sigma$ -field的union不一定是 $\sigma$ -field，将最小的包含了两个 $\sigma$ -field $\mathscr{F}$ 和 $\mathscr{G}$ 中所有元素的 $\sigma$ -field记为 $\mathscr{F}\vee\mathscr{G}$ 。但对于两个 $\sigma$ -field的intersection $\mathscr{F}\cap\mathscr{G}=\{A:A\in \mathscr{F} \quad\text{and} \quad A \in\mathscr{G}\}$ ，它必定是 $\sigma$ -field，为了统一符号，可以写为 $\mathscr{F}\wedge\mathscr{G}$ ，它就是保证元素同时属于 $\mathscr{F}$ 和 $\mathscr{G}$ 的最大的 $\sigma$ -field。这两个概念都可以推广到可数多个的情形。

概率论和测度论中，大量的工作都是在证明某个class of sets是 $\sigma$ -field。对于证明来说， $\sigma$ -field定义中的三条性质，前两条都很容易验证，但最后一条要验证却很困难。为此我们定义一种monotone class（单调类） $\mathscr{M}$ ，它也是由一些集合组成：若 $\{A_n\}$ 是monotone sequence，有极限 $A$ ，且 $\forall n, A_n\in\mathscr{M}$ ，则 $A\in \mathscr{M}$ ，称这样的 $\mathscr{M}$ 为monotone class。利用它和下面的定理，可以方便地证明一些class是 $\sigma$ -field。

定理： $\mathscr{F}$ 是 $\sigma$ -field，当且仅当 $\mathscr{F}$ 是field且它是一个monotone class。

利用这个定理，在考虑一个class是不是 $\sigma$ -field时，我们只需要考虑monotone sequences的极限是否属于它即可。

另一个常用的技巧是Dynkin's $\pi$ - $\lambda$ Theorem。对此需要先介绍两个概念做铺垫。

定义 $\pi$ -system：有一个class $\mathscr{P}$ ，若 $A\in\mathscr{P}$ 且 $B\in\mathscr{P}$ ，则 $A\cap B \in \mathscr{P}$ ，那么 $\mathscr{P}$ 就是 $\pi$ -system。

定义 $\lambda$ -system：有一个class $\mathscr{L}$ ，若它满足以下性质，那么 $\mathscr{L}$ 就是 $\lambda$ -system：

$X\in \mathscr{L}$ ；
若 $A\in\mathscr{L}$ 、 $B\in\mathscr{L}$ 且 $B\subseteq A$ ，则 $A-B\in\mathscr{L}$ ；
若 $\{A_n\in\mathscr{L}\}$ 是non-decreasing sequence，且 $A_n\uparrow A$ ，则 $A\in\mathscr{L}$ 。

前两个条件说的是 $\lambda$ -system对于complement是closed。并且由于第二条意味着 $\forall n, B_n=A_{n+1}-A_n\in\mathscr{L}$ ，所以第三条也说明了， $\mathscr{L}$ 中的disjoint sets的countable union依然在 $\mathscr{L}$ 中。利用这点，有以下定理。

定理：一个class $\mathscr{L}$ 是 $\lambda$ -system，当且仅当：

$X\in \mathscr{L}$ ；
若 $B\in\mathscr{L}$ ，则 $B^c\in\mathscr{L}$ ；
若 $\{A_n\in\mathscr{L}\}$ 是disjoint sequence，则 $\cup_n A_n\in\mathscr{L}$ 。

$\sigma$ -field必定是 $\lambda$ -system，同时是 $\pi$ -system和 $\lambda$ -system的class必定是 $\sigma$ -field。

下面的定理用到了这些定义。

定理 Dynkin's $\pi$ - $\lambda$ Theorem：若 $\mathscr{P}$ 是一个 $\pi$ -system， $\mathscr{L}$ 是一个 $\lambda$ -system，且 $\mathscr{P}\subseteq \mathscr{L}$ ，则 $\sigma(\mathscr{P})\subseteq \mathscr{L}$ 。