集合论相关定理

定义($⪯$${\preceq}$). 设$A$$A$和$B$$B$是两个集合，

$A$$A$的势小于等于$B$$B$($A⪯B)$$A{\preceq}B)$当且仅当存在一个单射$f:A\to B$$f:A{\rightarrow}B$.

$A$$A$的势小于$B$$B$($A\prec B$$A{\prec}B$)当且仅当$A⪯B$$A{\preceq}B$且$A\nsim B$$A{\nsim}B$.

例如：若$A=\{a,b,c,d\}$$A=\{a,b,c,d\}$, $B=\{1,2,3,4,5\}$$B=\{1,2,3,4,5\}$, 则$A⪯B)$$A{\preceq}B)$. 因为存在一个单射：$a\to 1$$a{\rightarrow}1$, $b\to 3$$b{\rightarrow}3$, $c\to 4$$c{\rightarrow}4$, $d\to 5$$d{\rightarrow}5$.

同时，$A\prec B$$A{\prec}B$也成立，因为$A\nsim B$$A{\nsim}B$.

此外，$A\prec N$$A{\prec}N$、$B\prec N$$B{\prec}N$都成立。

定理: $A$$A$是一个集合,$P(A)$$P(A)$是$A$$A$的幂集,则: $A\prec P(A)$$A{\prec}P(A)$.

证明: 首先，因为$A\subseteq P(A)$$A{\subseteq}P(A)$，所以存在一个$A\to P(A)$$A{\rightarrow}P(A)$的单射，即$A\to A$$A{\rightarrow}A$. 所以$A⪯P(A)$$A{\preceq}P(A)$.

下面证明对于给定的任意集合$A$$A$,无法找到满射函数$f:A\to P(A)$$f:A{\rightarrow}P(A)$. 如果存在一个$A$$A$的子集，它不是$A$$A$中某元素的像，命题便可得证。

通过对角化方法来构造: $B=\{x\in A:x\notin f(x)\}.$$B=\left\{\,x\in A : x\not\in f(x)\,\right\}.$

就是说,对于所有的$A$$A$中元素$x$$x$,$x\in B$$x{\in}B$当且仅当$x\notin f(x)$$x{\notin}f(x)$.

显然，$B$$B$包含于$P(A)$$P(A)$.

对于所有$x$$x$,集合$B$$B$与$f(x)$$f(x)$不可能是相等,因为$B$$B$由$A$$A$中元素不包含在$f(A)$$f(A)$里的所有元素构成。

考虑$x\in A$$x{\in}A$, 要么$x\in f(x)$$x{\in}f(x)$，要么$x\notin f(x)$$x{\notin}f(x)$.

前一种情况, $f(x)$$f(x)$不能等于$B$$B$,因为$x\in f(x)$$x{\in}f(x)$(假设)并且$x\notin B$$x{\notin}B$($B$$B$的定义).

后一种情况, $f(x)$$f(x)$也不能等于$B$$B$,因为$x\notin f(x)$$x{\notin}f(x)$(假设)并且$x\in B$$x{\in}B$($B$$B$的定义).

总之, $f(x)$$f(x)$不能等于$B$$B$. 而前面$B$$B$包含于$P(A)$$P(A)$, 所以$P(A)$$P(A)$的势比$A$$A$大, 即$A\prec P(A)$$A{\prec}P(A)$.

康托定理: $N\nsim P(N)$$N{\nsim}P(N)$.

可以看作前面已证定理的特例。

定理:（Cantor-Bernstein）$A$$A$和$B$$B$都是任意集合,如果: $A⪯B$$A{\preceq}B$,$B⪯A$$B{\preceq}A$, 则有:$A\sim B$$A{\sim}B$.

证明: 略。

定理: $N\sim Q$$N{\sim}Q$

证明: 可以定义一个单射$f:N\to Q$$f:N{\rightarrow}Q$,其中$f(n)=n$$f(n)=n$，因此$N⪯Q$$N{\preceq}Q$.

然后定义函数$g:Q\to N$$g:Q{\rightarrow}N$. $g(0)=0$$g(0)=0$. 当$q(\in Q)\ne 0$$q({\in}Q){\neq}0$时，令$q=\frac{\mu a}{b}$$q=\frac{{\mu}a}{b}$,其中$\mu =\pm 1$${\mu}={\pm}1$, $a>0$$a>0$, $b>0$$b>0$, $gcd(a,b)=1$$gcd(a,b)=1$.

$g(q)=2^{\mu +1}{3}^a{5}^b$$g(q)=2^{\mu+1}3^a5^b$ 是一个单射函数, 所以$N⪯Q$$N{\preceq}Q$.

综上，可得$N\sim Q$$N{\sim}Q$.

定理: $(0,1)\sim R$$(0,1){\sim}R$

证明: 存在一个一一映射$f:(0,1)\to R$$f:(0,1){\rightarrow}R$: $f(x)=tg(\pi x-\frac{\pi }{2}).$$f(x)=tg({\pi}x-\frac{\pi}{2}).$ 因此$(0,1)$$(0,1)$与$R$$R$等势，即$(0,1)\sim R$$(0,1){\sim}R$.

定理: $R\sim P(N)$$R{\sim}P(N)$.

证明: 根据刚才的定理,本定理等同于$(0,1)\sim P(N)$$(0,1){\sim}P(N)$. 不难发现$k\in (0,1)$$k{\in}(0,1)$都有完全不同的十进制展开形式： $k=0.k_1{k}_2{k}_3\cdots$$k=0.k_1k_2k_3\cdots$,其中$0\le k_n<9$$0{\le}k_n<9$.

定义一个函数$f:(0,1)\to P(N)$$f:(0,1){\rightarrow}P(N)$: $f(r)=p_1^{(k_1+1)}{p}_2^{(k_2+1)}{p}_3^{(k_3+1)}\cdots$$f(r)=p_1^{(k_1+1)}p_2^{(k_2+1)}p_3^{(k_3+1)}\cdots$ 其中,$p_1$$p_1$,$p_2$$p_2$,$\cdots$$\cdots$是从小往大排的素数。 不难验证，这是一个单射函数，所以$(0,1)⪯P(N)$$(0,1){\preceq}P(N)$.

然后，再定义一个$g:P(N)\to (0,1)$$g : P(N){\rightarrow}(0,1)$. 对于任意$S\subset N$$S{\subset}N$,$g(S)=0.S_0{S}_1{S}_2\cdots$$g(S)=0.S_0S_1S_2\cdots$,这里的下标$n$$n$如果属于$S$$S$,那么$S_n$$S_n$取3,否则取5. 不难验证,$g$$g$也是一个单向函数,所以$P(N)⪯(0,1)$$P(N){\preceq}(0,1)$.

综上,可得$R\sim P(N)$$R{\sim}P(N)$.

定理: 如果$S\subseteq N$$S{\subseteq}N$,那么或者$S$$S$是有限集,或者$S\sim N$$S{\sim}N$.

简单证明: 若$S$$S$是无限的,列出$S$$S$的元素$S_0$$S_0$, $S_1$$S_1$, $S_2$$S_2$, $\cdots$$\cdots$，本身就是$N$$N$到$S$$S$的单射。

定义:（Cantor）

(1)自然数集合$N$$N$的势记作${\mathrm{\aleph }}_0$$\aleph_{0}$(阿列夫$0$$0$).

(2)实数集合$R$$R$的势记作${\mathrm{\aleph }}_1$$\aleph_{1}$(阿列夫$1$$1$).

定理: ${\mathrm{\aleph }}_0+{\mathrm{\aleph }}_0={\mathrm{\aleph }}_0$$\aleph_{0}+\aleph_{0}=\aleph_{0}$

定理: ${\mathrm{\aleph }}_0\times {\mathrm{\aleph }}_0={\mathrm{\aleph }}_0$$\aleph_{0}\times\aleph_{0}=\aleph_{0}$

接下来,将不加证明地列出一些集合论相关的公理或定理。

选择公理（Axiom of Choice）: 设$F$$F$​是一个以非空集合为元素的集合，那么存在一个函数$f$$f$​使得$f(A)\in A$$f(A){\in}A$​对于每一个$A\in F$$A{\in}F$​. 称$f$$f$​是$F$$F$​的选择函数。

良序定理（Well-ordering Theorem）: 自然数集的每个非空子集都有一个最小元素,即自然数在普通的大小关系下构成一个良序集。

良序定理等价于选择公理,又称策梅洛定理（Zarmelo's Theorem）.

佐恩引理（Zorn's Lemma）: $A$$A$和$B$$B$是任意集合,要么$A⪯B$$A{\preceq}B$,要么$B⪯A$$B{\preceq}A$.

佐恩引理是良序定理的基础。

连续统假设（Continuum Hypothesis）: 如果$S\subseteq R$$S{\subseteq}R$,那么$S$$S$是可数的,要么$S\sim R$$S{\sim}R$.

定理（Gödel, Cohen）: 如果关于集合的公理是一致的，不可能通过这些公理来证明或证否连续统假设。