集合与图论学习笔记03

定义

定义 3.1 函数

设 $A$ 和 $B$ 是两个任意集合，$f$ 是从 $A$ 到 $B$ 的二元关系。若 $f$ 具有如下性质：

$f$ 的定义域 $\text{Dom } f = A$;
如果 $(a, b), (a, b') \in f$，则 $b = b'$。

则称关系 $f$ 是从 $A$ 到 $B$ 的函数，记为 $f: A \rightarrow B$；并称 $b$ 为 $a$ 的象，$a$ 为 $b$ 的原象，记为 $b=f(a)$。$f$ 的值域记为 $R_f$。也可以称 $f$ 是从 $A$ 到 $B$ 的映射

定义 3.2 象与原象

设 $f: A \rightarrow B$，$A_1 \subseteq A$，$B_1 \subseteq B$

定义 $f(A_1) = \{ f(a) \mid a \in A_1 \}$，称为 $A_1$ 在 $f$ 下的象

$f^{-1}(B_1) = \{ a \in A \mid f(a) \in B_1 \}$，称为 $B_1$ 在 $f$ 下的原象

定义 3.3 满射单射与双射

设函数 $f: A \rightarrow B$，若 $R_f = B$，则称 $f$ 为满射
设函数 $f: A \rightarrow B$，若 $\forall a_1, a_2 \in A$，$a_1 \neq a_2$ 有 $f(a_1) \neq f(a_2)$，则称 $f$ 为单射（或内射）
设函数 $f: A \rightarrow B$，若 $f$ 既是满射，又是单射，则称 $f$ 为双射（一一对应）

定义 3.4 函数相等

设函数 $f: A \rightarrow B$，$g: A \rightarrow B$，若对于任意的 $a \in A$，有 $f(a) = g(a)$，则称 $f$ 和 $g$ 相等，记为 $f = g$

定义 3.5 逆函数

设函数 $f: A \rightarrow B$ 是双射，$f$ 的逆关系称为 $f$ 的逆函数，记为 $f^{-1}: B \rightarrow A$。若 $f(a) = b$，则 $f^{-1}(b) = a$

函数的逆关系不一定是函数

下面证明，如果 $f$ 是 $A$ 到 $B$ 的双射，它的逆函数 $f^{-1}$ 也是双射

证明：点击查看证明

先证明 $f^{-1} $ 是 $B$ 到 $A$ 的函数

$f$ 是一个满射，故 $R_{f}=B$ 则 $\text{Dom } f^{-1}=B$

设 $(a, b), (a, b') \in f^{-1}$

则 $(b,a),(b',a)\in f$ ，由于 $f$ 为单射，$b=b'$，则 $f^{-1}$ 是函数

再证明 $f^{-1}$ 是双射

首先证明 $f^{-1}: B \rightarrow A$ 是满射，即证明对任意 $a \in A$，存在 $b \in B$，使得 $f^{-1}(b) = a$

设 $f = \{(a, b) \mid a \in A, b \in B, f(a) = b\}$，$f^{-1} = \{(b, a) \mid (a, b) \in f\}$

对于每一个 $a \in A$，必定存在 $b \in B$，使 $(a, b) \in f$

从而对每一个 $a \in A$，都有 $(b, a) \in f^{-1}$，即 $f^{-1}(b) = a$

所以 $f^{-1}: B \rightarrow A$ 是满射

再证明 $f^{-1}: B \rightarrow A$ 是单射，即证明对于任意的 $b_1, b_2 \in B$

当 $b_1 \neq b_2$ 时，$f^{-1}(b_1) \neq f^{-1}(b_2)$。若 $f^{-1}(b_1) = a$，$f^{-1}(b_2) = a$，则 $f(a) = b_1$，$f(a) = b_2$

又因为 $f: A \rightarrow B$ 是函数，所以 $b_1 = b_2$

所以 $f^{-1}: B \rightarrow A$ 是单射

显然 $(f^{-1})^{-1}=f$

定义 3.6 复合函数

设函数 $g: A \rightarrow B$，$f: B \rightarrow C$，称复合关系 $g \circ f$ 为从 $A$ 到 $C$ 的复合函数，记为 $g \circ f: A \rightarrow C$，且 $\forall a \in A$，有 $(g \circ f)(a) = f(g(a))$

注意复合函数与复合关系的记法不同，复合函数采用函数习惯记法，要将变元放在函数记号的右侧，即$(f \circ g)(a)= f(g(a))$。所以用记号 $f \circ g$，而不用 $g \circ f$

我们证明复合关系 $g \circ f$ 是函数即

$g: A \rightarrow B$，$f: B \rightarrow C$，则从 $A$ 到 $C$ 的复合关系 $g \circ f$ 是从 $A$ 到 $C$ 的函数

证明：点击查看证明

首先要证明在 $A$ 中的任一元素，都有 $C$ 中的元素与之对应

$\forall a\in A$，$\exists b\in B$，使得 $(a, b) \in g$

对于 $b$，$\exists c\in C$，使得 $(b, c) \in f$

有复合关系定义 $(a, c) \in g \circ f$

然后再证明对 $A$ 中的每个元素，都只对应 $C$ 中的一个元素

$\forall a\in A$，若有 $x, y \in C$，使得 $(a, x) \in g \circ f$，$(a, y) \in g \circ f$

根据复合关系定义，$\exists b_{1}\in B$，使得 $(a, b_{1}) \in g$，$(b_{1}, x) \in f$

$\exists b_{2}\in B$，使得 $(a, b_{2}) \in g$，$(b_{2}, x) \in f$

$b_{1}, b_{2} \in B$，$(a, b_{1}) \in g$，$(a, b_{2}) \in g$，并且 $g$ 是函数，则 $b_{1}=b_{2}$

由于 $x, y \in C$，$(b_{1}, x) \in f$，$(b_{1}, y) \in f$，而 $f$ 是函数，所以 $x = y$

所以从 $A$ 到 $C$ 的复合关系 $g \circ f$ 是函数

容易知道 $(f \circ g)^{-1}=g^{-1}\circ f^{-1}$

定义 3.7 恒等函数

设函数 $f:A→A$，若对所有的 $a\in A$，$f(a)=a$ 成立，则称 $f$ 为 $A$ 上的恒等函数，记为 $I_{A}$

容易知道 $f\circ f^{-1}=I_{A}$ $f^{-1}\circ f=I_{B}$

定义 3.8 等势与基数

$A, B$ 是任意两个集合，若存在一个双射 $f: A \to B$，则称 $A$ 和 $B$ 对等（或等势），记为 $A \sim B$，或称 $A$ 和 $B$ 的基数相同

$A$ 的基数记为 $\bar{A}$，或者 $|A|$，$A$ 和 $B$ 的基数相同记为 $\bar{A} = \bar{B}$ 或者 $|A| = |B|$

定义 3.9 有限集和无限集

设 $A$ 为一个集合，若 $A$ 为空集或与集合 $\{0, 1, 2, \cdots, n-1\}$ 的基数相同，则称 $A$ 为有限集，且 $|A| = n \in \mathbb{N}$

若集合 $A$ 不是有限集，则称 $A$ 为无限集

无限集必和它的一个真子集对等

证明：点击查看证明

设无限集$A$ ，取出一列元素 $a_{1},a_{2},...,a_{n},...$

定义 $A$ 的真子集 $B=A-\{a_{1},a_{2},...,a_{n},...\}\cup\{a_{2},a_{4},...,a_{2n},...\}$

定义单射 $f:A\rightarrow B$ $f(x)={ \[\begin{matrix} a_{2i}\space x=a_{i} \\ x\space x\in A \end{matrix}\]

. $

如此可得 $A$ 与 $B$ 等势

凡不能与自身的任一真子集对等的集合为有限集

定义3.10 可列集

若存在从 $\mathbb{N}$ 到 $A$ 的双射，则称 $A$ 为可列无限集，简称可列集或可数集$|A| = \aleph_0$。

个集合是可列集的充要条件是它的元素可以排成一个无穷序列的形式

任何一个无限集必含有一个可列子集

证明：点击查看证明

设无限集 $A$，递归地选取 $a_{1},a_{2},...,a_{n}$

由于 $A$ 非空，选取 $a_{1}\in A$

假设已选取 $a_{1},a_{2},...,a_{n}$ 各不相同，考虑集合 $A-\{a_{1},a_{2},...,a_{n}\}$ 非空，可以继续选择 $a_{n+1}\in A-\{a_{1},a_{2},...,a_{n}\}$

根据上述选取，定义 $B=\{a_{1},a_{2},...,a_{n}...\}$

$f:\mathbb{N}\rightarrow B$ 为 $f(n)=a_{n}$ 容易知道 $f$ 是一个单射，所以 $B$ 是可列的

可列集的任何无限子集必为可列集

证明：点击查看证明

$A$ 可列，枚举 $A$ 为 $\{a_{1},a_{2},...,a_{n}...\}$，其中 $a_{n}=f(n)$

无限集 $B\subseteq A$，$\forall b\in B$ 有 $b=a_{i}$

定义集合 $S=\{n\in \mathbb{N}\mid a_{n}\in B\}$

由于 $B$ 无限，所以 $S$ 无限，由 $S$ 是 $N$ 子集，可以将 $S$ 按照自然数大小排序，容易得到一个双射，故 $S$ 是可列的，所以容易得到 $B$ 是可列的

可列集中加入有限个元素（或删去有限个元素），仍为可列集

证明：点击查看证明

枚举即可

有限个可列集之并仍为可列集

证明：点击查看证明

交叉枚举即可，如：

$\{a_{0},b_{0},a_{1},b_{1},...,a_{n},b_{n},...\}$

可列个可列集之并仍为可列集

证明：点击查看证明

不妨设可列个可列集为 $A_{1},A_{2},...$

$A_{1}=\{a_{11},a_{12},...\}$

$A_{2}=\{a_{21},a_{22},...\}$

$A_{3}=\{a_{31},a_{32},...\}$

…

按照对角线方法排列

每一斜线上两下标之和相同

$a_{11},a_{12},a_{21},a_{13},a_{22},a_{31},...$

则 $A$ 是可列的

设 $A$ 为有限集或可列集，$B$ 为任意无限集，则 $|A\cup B|=|B|$

证明：点击查看证明

取 $B$ 中一个可列子集 $S\subseteq B$ ，则 $S\cup (A-B)$ 也是可列的，所以存在双射 $f:S\rightarrow S\cup(A-B)$

由于 $(B-S)\cap(S\cup(A-B))=\emptyset$ 且 $(S\cup(A-B))=A\cup B$ 且 $(B-S)\cap S=\emptyset$ 且 $(B-S)\cup S=B$

定义映射 $g:(B-S)\cup S \rightarrow (B-S)\cup(S\cup(A-B))$

$g(x)={ \[\begin{matrix} x\space x\in B-S \\ f(x)\space x\in S \end{matrix}\]

. $

$f$ 是双射，所以 $g$ 是双射，所以 $|A\cup B|=|B|$

$(0,1)$ 是不可列集，基数记为 $\mathfrak{c}$ ，也记为 $\aleph$ ，$(0,1)$ 也称为连续统

证明：点击查看证明

使用反证法

假设 $(0,1)$ 是可列的，规定其中每一个实数唯一表示成一个尾数不为0的十进制无限小数

$a_{1} = 0.s_{11}s_{12}s_{13}...$

$a_{2}=0.s_{21}s_{22}s_{23}...$

$a_{3}=0.s_{31}s_{32}S_{33}...$

其中 $s_{ij}=0,1,..,9$

现在取一个十进制小数 $t=0.t_{1}t_{2}t_{3}...$

其中 $t_{i}=\left\{\begin{matrix} 1\space s_{ii}\ne 1 \\ 2\space s_{ii}=1 \end{matrix}\right.$

$t$ 满足，$t_{i}\ne 0,9$，$i=1,2,3,...,$ ，$t\in(0,1)$ 且 $t_{i}]\ne s_{ii}$故 $t\notin \{a_{1},a{2},...\}=(0,1)$ 矛盾！

所以 $(0,1) $ 不可列

设实数 $a < b$ 则 $(a,b),(a,b].[a,b),[a,b]$ 的基数都是 $c$

证明：点击查看证明

先证明 $|(0,1)|=|[0,1]|$

取一无限点列 $x_{n}=\frac{1}{n+1}$

$[0,1]$ 中点 $0$ 对应 $(0,1)$ 中点 $x_{1}$

$[0,1]$ 中点 $1$ 对应 $(0,1)$ 中点 $x_{2}$

$[0,1]$ 中点 $x_{1}$ 对应 $(0,1)$ 中点 $x_{3}$

$[0,1]$ 中点 $x_{2}$ 对应 $(0,1)$ 中点 $x_{4}$

…

其他点保持不变，这样的到一个一一对应，所以 $|(0,1)|=|[0,1]|$

再由无限集并有限集的并和无限集的基数相同知 $[0,1),(0,1]$ 的基数都和它们相等

这时构造映射 $f(x)=a+(b-a)x$ ，所以这四个区间的基数都是 $\aleph$

$\mathbb{Q}$ 的基数是 $\aleph_{0}$

证明：点击查看证明

任取 $q\in \mathbb{Q}$ 记 $q=\frac{b}{a}$

$a,b\in \mathbb{Z}$

取 $(a,b)$ 一一对应 $q$ 按照顺序枚举即可

$\mathbb{R},\mathbb{R-Q}$ 的基数都是 $\aleph$

证明：点击查看证明

先证 $\mathbb{R}$

构造双射 $f;(0,1)\rightarrow \mathbb{R}$ $f(x)=\text{tan} (\pi -x[\frac{\pi}{x}])$

故 $\mathbb{R}$ 基数是 $\aleph$

由无限集并上可列集的并和无限集的基数相同知道 $\mathbb{R}-\mathbb{Q}$ 的基数也是 $\aleph$

定义 3.11 基数序关系

若存在单射 $f: A \to B$，则称 $A$ 的基数小于等于 $B$ 的基数，记为 $|A| \leq |B|$

若 $|A| \leq |B|$ 且 $|B| \neq |A|$ 则称 $A$ 的基数小于 $B$ 的基数，记为 $|A| < |B|$

设 $A, B, C$ 是任意集合，那么
(1) 若 $A \subseteq B$，则 $|A| \leq |B|$。
(2) 若 $|A| \leq |B|$，$|B| \leq |C|$，则 $|A| \leq |C|$

（伯恩斯坦（F. Bernstein）定理） 若 $A$ 和 $B$ 是两个集合，且 $|A| \leq |B|$，$|B| \leq |A|$，则 $|A| = |B|$

证明：点击查看证明

记 $f:A\rightarrow B$ $g:B\rightarrow A$

定义映射 $T:\mathcal{P}(A)\rightarrow \mathcal{P}(A)$

任意 $X\subseteq A$ 有 $T(X)=A-g(B-(f(X)))$

若 $X\subseteq Y \subseteq A$

则 $f(X)\subseteq f(Y)$

则 $B-f(Y)\subseteq B-f(X)$

则 $g(B-f(Y))\subseteq g(B-f(X))$

则 $A-g(B-f(X))\subseteq A-g(B-f(Y))$

即 $T(X)\subseteq T(Y)$ 所以 $T$ 单调递增

记 $\mathcal{F}=\{X\subseteq A\mid X\subseteq T(X)\}$

记 $C=\bigcup_{X\in \mathcal{F}}X$

我们证明 $C\subseteq T(C)$

$\forall X\in \mathcal{F}$ 有 $X\subseteq T(C)$

由于 $X\subseteq C$ 知道 $T(X)\subseteq T(C)$

所以 $\forall X\in \mathcal{F}$ 有 $X\subseteq T(X)\subseteq T(C)$

$C$ 是所有 $X\in \mathcal{F}$ 的并，所以 $C\subseteq T(C)$

再证明 $T(C)\subseteq C$

已知 $C\subseteq T(C)$ 所以 $T(C)\subseteq T(T(C))$

所以 $T(C)\in \mathcal{F}$，由于 $C$ 是所有 $X\in \mathcal{F}$ 的并

所以 $T(C)\subseteq C$

所以 $C\subseteq T(C)$ 且 $T(C)\subseteq C$ 所以 $T(C)=C$

即 $C=A-g(B-f(C))$

所以 $A-C=g(B-f(C))$

$g$ 是单射，$B-f(C)$ 与 $A-C$ 通过 $g$ 一一对应

定义 $h:A\rightarrow B$

$h(x)=\left\{\begin{matrix} f(x)\space x\in C \\ g^{-1}(x)\space x\in A-C \end{matrix}\right.$

这里定义 $g^{-1}(x)$，如果 $x\in A-C$ ，那么 $x\in g(B-f(C))$

所以存在唯一 $y\in B-f(C)$ 使得 $g(y)=x$

下面证明 $h$ 是双射

先证明 $h$ 是单射

若 $x_{1},x_{2}\in C$ 则 $h(x_{1})=f(x_{1}),h(x_{2})=f(x_{2})$，$f$ 是单射得到结果

若 $x_{1},x_{2}\in A-C$ 则 $h(x_{1}=g^{-1}(x_{1})),h(x_{2}=g^{-1}(x_{2}))$ ，由 $g$ 单射得到结果

若 $x_{1}\in C,x_{2}\in A-C$ 则 $h(x_{1})=f(x_{1})\in f(C)$，$h(x_{2})\in B-f(C)$ 不可能相等

所以 $h$ 是单射

再证明 $h$ 是满射

对任意 $y\in B$

若 $y\in f(C)$ ，则存在 $x\in C$ 使得 $f(x)=y$ 所以 $h(x)=y$

若 $y\in B-f(C)$，则 $g(y)\in g(B-f(C))=A-C$，取 $x=g(y)\in A-C$ 则 $h(x)=g^{-1}(g(y))=y$

所以 $h$ 是满射

所以 $h$ 是双射

所以若 $|A| \leq |B|$，$|B| \leq |A|$，则 $|A| = |B|$ 即伯恩斯坦（F. Bernstein）定理成立

（蔡梅罗（Zermelo）定理）（三歧性） 设 $A$ 和 $B$ 是任意两个集合，那么 $|A| < |B|$，$|B| < |A|$，$|A| = |B|$ 三者中恰有一个成立

证明：点击查看证明

先给出良序集和序同构的定义

$S$ 是全序集，$\prec$ 是序关系，$S$ 的每一个非空子集都有一个关于 $\prec$ 的最小元

这里说明一个全序集是良序的当且仅当不存在一个无限下降链

假设存在无限下降链 $a_{1}\succ a_{2}\succ ...$ ，取集合 $X=\{a_{1},a_{2},...\}$ 可知 $X$ 没有最小元矛盾

假设全序集不是良序的，则存在非空子集 $X$ 没有最小元，从 $X$ 中任取 $a_{1}$，由于 $a_{1}$ 不是最小元，存在 $a_{2}\in X$ 使得 $a_{1} \succ a_{2}$，依此类推可以得到无限下降链

设 $(A,\prec_{A}),(B,\prec_{B})$ 是两个全序集，如果有一个双射 $f:A\rightarrow B$ 满足 $\forall x,y\in A$ ，有 $x\prec_{A}y$ 等价于 $f(x)\prec_{b}f(y)$，那么这个双射称为序同构，，也称 $A$ 和 $B$ 序同构，记作 $A\cong B$

先证明 良序定理：任何集合 $X$ 都可良序化，即存在一个关系 $\prec$ 使得 $(X,\prec)$ 是良序集

记 $\mathcal{P}_{0}(X)=\mathcal{P}(X)-\{\emptyset\}$ 表示 $X$ 的所有非空子集的集合

由选择公理，存在函数 $F:\mathcal{P}_{0}(X)\rightarrow X$ 使得 $F(S)\in S$ 对所有的 $S\in \mathcal{P}_{0}(X)$ 成立，简单来说， $F$ 就是从每个非空子集中选出一个元素

定义一个子集 $Y\subseteq X$ 是 $F-$链：

如果 $(Y,\prec)$ 是良序集，并且对于每个 $a\in Y$ 都有 $a=F(X-Y_{\prec a})$

这里的 $Y_{\prec a}=\{y\in Y\mid y \prec a\}$ 是 $Y$ 中在 $a$ 之前所有元素的集合

简单来说， $F-$ 链中每个元素 $a$ 都是由函数 $F$ 在还没有选取的集合 $X-Y_{\prec a}$ 中选出来的

容易知道 $F-$ 链的并还是 $F-$ 链

取 $M=\bigcup \{Y\subseteq X\mid Y是F-链\}$

下面证明 $M=X$

假设 $M\ne X$，则 $X-M\ne \emptyset$

取 $m=F(X-M)$ 定义 $M'=M\cup \{m\}$ ，在 $M'$ 上定义序：

保持 $M$ 的序，并且 $m$ 为最大元。

下面证明 $M'$ 是 $F-$ 链

$a\in M$ 有 $M'_{\prec a}=M_{\prec a}$ 所以 $a=F(X-M_{\prec a})=F(X-M'_{\prec a})$

$a=m$ 有 $M'_{\prec m}=M$ 所以 $m=F(X-M)=F(X-M'_{\prec m})$

所以 $M'$ 是 $F-$ 链

得到 $M'\subseteq M$ 所以 $M=X$

所以 $X$ 上有一个良序 $\prec$

再证明良序集基本引理

良序集不能与其真前段同构

设 $f:X\rightarrow X_{\prec b}$ 是同构，则 $x \succ f(x) \succ f(f(x)) \succ ...$ 是无限下降链，矛盾

再证明良序集比较定理

设 $(A,\prec_{A})$ 和 $(B,\prec_{B})$ 是良序集，则恰有以下的一个成立

$A\cong B$ （序同构）
$A\cong B_{\prec b}$ （对某个 $b\in B$，$A$ 序同构于 $B$ 的真前段）
$A_{\prec a}\cong B$ （对某个 $a\in A$，$B$ 序同构于 $A$ 的真前段）

定义集合 $f=\{(a,b)\in A\times B\mid A_{\prec a}\cong B_{\prec b}\}$

即 $f$ 由所有满足 $a$ 在 $A$ 中的前段与 $b$ 在 $B$ 中的前段同构的配对 $(a,b)$ 组成

下面证明 $f$ 是一个函数

设 $(x,y)\in f$ 且 $(x,y')\in f$ 则 $A_{\prec x}\cong B_{\prec y}$ 且 $A_{\prec x}\cong B_{\prec y'}$

所以 $B_{\prec y}\cong B_{\prec y'}$

由于 $B$ 是良序的，两个前段同构当且仅当 $y=y'$ 否则一个前段是真前段，良序集不能与真前段同构

所以 $f$ 是函数

同理可以证明 $f$ 是单射

下面证明 $\text{dom}(f)$ 是 $A$ 的初始段

设 $x\in \text{dom}(f)$ 即存在 $y \in B$ 使得 $A_{\prec x}\cong B_{\prec y}$

$\forall x'\prec_{A} x$ 有 $A_{\prec x'}$ 是 $A_{\prec x}$ 的真前段

由于 $A_{\prec x}\cong B_{\prec y}$ 在同构下 $A_{\prec x'}$ 对应 $B_{\prec y'}$ 其中 $y’$ 满足 $y'\prec_{B} y$

所以 $A_{\prec x'}\cong B_{\prec y'}$ 所以 $(x',y')\in f$ 即 $x'\in \text{dom}(f)$

所以 $\text{dom}(f)$ 是 $A$ 的初始段

同理可证 $\text{ran}(f)$ 是 $B$ 的初始段

根据 $f$ 定义容易得到 $f$ 和 $f^{-1}$ 都是保序的，所以 $f:\text{dom}(f)\rightarrow \text{ran}(f)$ 是序同构

令 $D=\text{dom}(f)$ $R=\text{ran}(f)$

我们只需要证明不可能出现 $D$ 是 $A$ 的真前段并且 $R$ 是 $B$ 的真前段的情况

假设 $D=A_{\prec a},R=B_{\prec b}$ 其中 $a\in A-D,b\in B-R$

那么 $A_{\prec a}\cong B_{\prec b}$ 则 $(a,b)\in f$ 则 $a\in D$ 矛盾

又由于良序集不能与真前段同构，知道其他三种情况是互斥的，所以必定是列出的三种情况之一

最后，证明三歧性

对任意 $A,B$，存在良序 $\prec_{A},\prec_{B}$

对良序集比较定理的第一种情况，显然 $|A|=|B|$

对第二种情况，存在单射 $A\rightarrow B$ 所以 $|A|\le |B|$

假设存在 $|B|\le |A|$

根据伯恩斯坦（F. Bernstein）定理有 $|A|=|B|$

所以存在双射 $h:B\rightarrow A$

又有 $A\cong B_{\prec b}$ 所以 $|B|=|B_{\prec b}|$

所以存在双射 $B\rightarrow B_{\prec b}$

这说明良序集和自己的真前段同构，矛盾！

所以 $|A|\le |B|$

第三种情况对称地成立

综上，蔡梅罗（Zermelo）定理成立

（康托尔（Contor）定理） 对于任何集合 $A$，必有 $|A| < |\mathcal{P}(A)|$

证明：点击查看证明

定义一个映射 $f:A \rightarrow \mathcal{P}(A)$ 有 $f(x)=\{x\}$

显然 $f$ 是一个单射

所以 $|A|\le |\mathcal{P}(A)|$

下面证明 $|A|\ne |\mathcal{P}(A)|$

假设不成立，则存在双射 $g:A\rightarrow \mathcal{P}(A)$

我们称 $a\in g(a)$ 的 $a$ 为 $A$ 的内部元素，否则为外部元素

设 $B$ 为 $A$ 的所有外部元素组成的集合，显然 $B\subseteq A$，所以 $B\in \mathcal{P}(A)$

由于 $g$ 是双射，则存在 $b\in A$ 使得 $g(b)=B$

如果 $b\in B$ 则 $b$ 是内部元素，与 $B$ 定义矛盾

如果 $b\notin B$ 则 $b\in g(b)=B$ 矛盾

所以 $g$ 不可能是一个双射

综上，康托尔（Contor）定理成立

设 $A$ 是有限集，则 $|A|<\aleph_{0} < \aleph$

证明：点击查看证明

容易知道 $|A|\le \aleph_{0}$

假设它们相等，那么存在一个双射 $f:A\rightarrow \mathbb{N}$

设 $|A|=n$ 在 $\mathbb{N}$ 中选 $n+1$ 个元素， $f$ 是双射，由抽屉原理知必存在 $f^{-1}(a_{i})=f^{-1}(a_{j})$ 矛盾！

所以 $|A| < \aleph_{0}$

$|\mathcal{P}(\mathbb{N})|=\aleph$ 即 $2^{\aleph_{0}}=\aleph$

证明：点击查看证明

设二进制小数的集合是 $B$

二进制有限小数集合 $A_{1}$ ，二进制无限小数集合 $A_{2}$

下面先证明 $A_{1}$ 是可列集，$A_{2}$ 的基数是 $\aleph$

容易知道任意一个二进制有限小数 $a=\frac{m}{2^{k}}$ 其中 $m\in \mathbb{Z},k\in \mathbb{N}$

容易构造双射 $f:A_{1}\rightarrow \mathbb{Z}\times \mathbb{N}$ 有 $f(a)=(m,k)$

容易知道 $\mathbb{Z}\times \mathbb{N}$ 是可列的，所以 $A_{1}$ 是可列的

对 $A_{2}$ 我们构造一个到 $(0,1]$ 的双射 $f$

$f(a)=\Sigma_{k=1}^{\infty} a_{k}\cdot 2^{-k}$

下面证明 $f$ 是单射

若 $a\ne b$ 则存在最小的 $n$ 使得 $a_{n}\ne b_{n}$

不妨设 $a_{n}=1,b_{n} = 0$

则 $f(a)-f(b)\ge 2^{-n}-\Sigma_{k=n+1}^{\infty}2^{-k}=2^{-n}-2^{-n}=0$

则 $a$ 在 $n$ 位后全为 $0$，$b$ 在 $n$ 位后全为 $1$ ，这与序列不最终全为 $1$ 矛盾！

所以 $f(a)=f(b)$

再证明 $f$ 是满射

对任意 $x\in(0,1]$ ，用二进制展开时，不选择包含无限后缀为 $1$ 的展开，这样每一个 $x$ 唯一对应一个 $a\in A_{2}$ ，且 $f(a)=x$

综上 $|A_{2}|=|(0,1]|=\aleph$

所以 $|B|=|A_{1}\cup A_{2}|=|A_{2}|=\aleph$

做一个映射 $g:\mathcal{P}(\mathbb{N})\rightarrow B$

对 $\mathbb{N}$ 的每一个子集 $S$，$f(S)=0.a_{1}a_{2}a_{3}...$

其中 $a_{i}=\left\{\begin{matrix} 1\space i\in S \\ 0\space i\notin S \end{matrix}\right.$

显然这是一个双射，因此 $|\mathcal{P}(\mathbb{N})|=\aleph$ 即 $2^{\aleph_{0}}=\aleph$

$A,B$ 是两个集合，记 $B^{A}=\{f\mid f: A\rightarrow B\}$

$|\mathbb{N}^{\mathbb{N}}|=|(0,1)|=\aleph$

即可列个 $ $ 做笛卡尔积的基数为 $\aleph$

证明：点击查看证明

先构造 $f:(0,1)\rightarrow \mathbb{N}^{\mathbb{N}}$

对 $x=0.x_{1}x_{2}x_{3}...\in(0,1)$

$f(x)=(x_{1},x_{2},x_{3},...)\in \mathbb{N}^\mathbb{N}$

再构造 $g:\mathbb{N}^{\mathbb{N}} \rightarrow (0,1)$

$\forall n_{1},n_{2},n_{3}...\in\mathbb{N}$

$g(n_{1},n_{2},n_{3}...)=0.n_{1}n_{2}n_{3}...\in (0,1)$

它们都显然是一个单射，所以 $|\mathbb{N}^{\mathbb{N}}|=|(0,1)|=\aleph$

$|\mathbb{R}|=|\mathbb{R}^{2}|=\aleph$

证明：点击查看证明

容易知道 $|\mathbb{R}|\le|\mathbb{R}^{2}|$

容易知道 $|\mathbb{R}^{2}|=|[0,1]^{2}|$

下面构造一个映射 $f:[0,1]\times [0,1] \rightarrow [0,1]$

对 $a,b$

$a=0.a_{1}a_{2}a_{3}...$，$b=0.b_{1}b_{2}b_{3}...$

构造 $f(a,b) =0.a_{1}b_{1}a_{2}b_{2}...\in [0,1]$

对 $a\ne b$，显然 $f(a)\ne f(b)$ 即 $f$ 是一个单射

所以 $|\mathbb{R}^{2}|=|[0,1]^{2}|\le |[0,1]|=|\mathbb{R}|$

所以 $|\mathbb{R}|=|\mathbb{R}^{2}|=\aleph$

$|\mathbb{R}|=|\mathbb{R}^{n}|=\aleph$

证明：点击查看证明

只需证 $|(0,1)|=|(0,1)^{n}|$

$f:(0,1)\rightarrow (0,1)^{n}$

构造 $f(x)=(x,x,...,x)$

$g:(0,1)^{n}\rightarrow (0,1)$

对 $\forall x_{1},x_{2},...,x_{n}\in(0,1)$

$x_{1}=0.x_{11}x_{12}x_{13}...$

$x_{2}=0.x_{21}x_{22}x_{23}...$

$...$

$x_{n}=0.x_{n1}x_{n2}x_{n3}...$

记 $y=0.x_{11}x_{12}x_{21}...$

$g(x_{1},x_{2},...x_{n})=y$ 即可

所以 $|\mathbb{R}|=|\mathbb{R}^{n}|=\aleph$

$|\mathbb{R}|=|\mathbb{R}^{\mathbb{N}}|=\aleph$

即可列个 $\mathbb{R}$ 做笛卡尔积的基数为 $\aleph$

证明：点击查看证明

只需证 $|(0,1)|=|(0,1)^{\mathbb{N}}|$

记 $\{0,1\}^{\mathbb{N}}$ 为二进制无限小数

有 $\mathbb{R}\cong \{0,1\}^{\mathbb{N}}$

则 $\mathbb{R}^{\mathbb{N}}\cong(\{0,1\}^{\mathbb{N}})^{\mathbb{N}}\cong\{0,1\}^{\mathbb{N\times N}} \cong \{0,1\}^{\mathbb{N}} \cong \mathbb{R}$

这里用到了 $\mathbb{N}\times \mathbb{N}\cong \mathbb{N}$

也就是 $|\mathbb{N}\times \mathbb{N}|=|\mathbb{N}|$

另外地

类似上面有限个的证法也是可以的

康托尔悖论

集合是由具有某些性质的元素所组成，因此也可以假设集合 $S$ 是由所有集合所组成

问：$S$ 与 $\mathcal{P}(S)$的基数哪一个基数更大

一方面由康托尔定理知 $|S| < |\mathcal{P}(S)|$

另一方面

又因为 $S$ 是所有集合所组成的集合，所以 $\mathcal{P}(S)\subseteq S$

则 $|\mathcal{P}(S)| \le |S|$ 矛盾！

ZFC 公理

外延公理

若两集合有相同元素，则两者相等

$A , B , [ x , (x A x B) A = B $

配对公理

$\forall x,y$ 存在集合 $\{x,y\}$ 其元素恰好是 $x$ 和 $y$

$\forall a \, \forall b \, \exists A \, \forall x \, [ x \in A \leftrightarrow (x = a \vee x = b)$

分离公理模式

设 $P$ 为一个关于集合的性质，以 $P(u)$ 表示集合 $u$ 满足性质 $P$，则对任意集合 $X$ 存在集合 $Y=\{u\in X\mid P(u)\}$

$A , p_1 p_n , B , x , [ x B (x A (x, p_1, , p_n)) $

并集公理

任意集合 $X$ 存在相应的并集 $\bigcup X:= \{u\mid \exists v\in X \text{s.t.}u\in v\}$

简单来说，就是存在一个并集 $Y=\bigcup X$ 使得 $Y$ 中的元素是所有 $X$ 中元素的元素，这里的 $X$ 可以看作若干个集合组成的集合，$Y$ 的概念就是这些集合的并

$\bigcup\{\{x,y\},\{z,w\}\}=\{x,y,z,w\}$

$ , U , x , [ x U A , (A x A) $

幂集公理

任意集合 $X$ 子集构成集合 $\mathcal{P}(X):=\{u\mid u\subset X\}$

$\forall A \, \exists P \, \forall B \, [ B \in P \leftrightarrow B \subseteq A$

无穷公理

存在无穷集

\[\exists I \, [ \exists e \, \forall x \, (x \notin e) \wedge e \in I \wedge \forall x \in I \, (x \cup \{x\} \in I) \]

替换公理模式

$F$ 是一个以集合 $X$ 为定义域的函数，则存在集合 $F(X)=\{F(X)\mid x\in X\}$

$A , p_1 p_n , [ (x A , ! y , (x, y, p_1, , p_n)) B , y , (y B x A , (x, y, p_1, , p_n)) $

正则公理

任意一个非空集合都含有一个对从属关系 $\in$ 极小的元素

$A , [ A x A , y x , (y A) $

选择公理

设集合 $X$ 的每个元素都非空，则存在函数 $g:X\rightarrow \bigcup X$ 使得 $\forall x\in X,g(x)\in x$ （这个函数称为选择函数）

$ , [ f: , A , (f(A) A) $

(´-ω-｀)

集合与图论学习笔记03

定义

定义 3.1 函数

定义 3.2 象与原象

定义 3.3 满射单射与双射

定义 3.4 函数相等

定义 3.5 逆函数

定义 3.6 复合函数

定义 3.7 恒等函数

定义 3.8 等势与基数

定义 3.9 有限集和无限集

定义3.10 可列集

定义 3.11 基数序关系

康托尔悖论

ZFC 公理

外延公理

配对公理

分离公理模式

并集公理

幂集公理

无穷公理

替换公理模式

正则公理

选择公理