可数集和不可数集

大家好，欢迎来到IT知识分享网。

有限集和无限集

后继集

设$S$是任一集合，称 S + = S ∪ { S } S^+ = S\cup \left\{ S\right\} S+=S∪{
S}为$S$的后继集

自然数集

自然数集$\mathbb{N}$的归纳定义是：
（1）$\varnothing \in \mathbb{N}$
（2）若$n\in \mathbb{N}$，则$n^{+}\in \mathbb{N}$
（3）若$S\in \mathbb{N}$，且满足
1.$\varnothing \in S$；
2. 若$n\in S$，则$n^{+}\in S$；

则$S=\mathbb{N}$

由定义，每个自然数$n$，都有$n\in n^{+}$和$n\subseteq n^{+}$，利用这一性质可在$\mathbb{N}$上引进大小次序关系

若$m,n\in \mathbb{N}$使$m\in n$则称$m$小于$n$（或$n$大于$m$），记为$m<n$（或$n>m$）
我们将$\mathbb{N}$的前$n$个自然数的集合记为 N n = { 0 , 1 , 2 , ⋯   , n − 1 } \mathbb{N}_n = \left\{0, 1, 2,\cdots, n -1\right\} Nn​={
0,1,2,⋯,n−1}

设$A$和$B$使任意集合，若存在从$A$到$B$的双射，则称$A$与$B$是等势的，记为$A\sim B$；
若$A$与$B$不等势，则记为$A\nsim B$

例子：$\mathbb{N}\sim \mathbb{I}$
作$f:\mathbb{N}\to \mathbb{I}$，
$$f\left(x\right)=\{\begin{array}{ll}-\frac{x+1}{2},& \text{x is odd}\\ \frac{x}{2},& otherwise\end{array}$$
容易验证$f$双射

若有$n\in \mathbb{N}$，使得${\mathbb{N}}_n\sim A$,则称$A$是有限集，且称其基数为$n$，记为$\left|A\right|=n$;
若$A$不是有限集，则称$A$是无限集

例子： 自然数是无限集合

证明：假设$\mathbb{N}$是有限集，则有$n\in \mathbb{N}$，使得存在双射
$$f:{\mathbb{N}}_n\to \mathbb{N}$$
取 k = max ⁡ { f ( i ) ∣ i ∈ N n } + 1 k = \max\left\{f\left(i\right)|i \in \mathbb{N}_n\right\} + 1 k=max{
f(i)∣i∈Nn​}+1
则$k\in \mathbb{N}$，并且不存在$x\in {\mathbb{N}}_n$，使得$f\left(x\right)=k$，即$f$不是满射的，矛盾

定理1： 任何有限集都不能与它的真子集等势

定理2：
设$A$是有限集，$B$是无限集，$C$是任意集合
（1）若$C\subseteq A$，则$C$是有限集
（2）若$B\subseteq C$，则$C$是无限集合

可数集与不可数集

设$A$是任意集合。若$\mathbb{N}\sim A$，则称$A$是可数无限集，并称$A$的基数为${\aleph }_0$（阿列夫零），记为$\left|A\right|={\aleph }_0$
有限集和可数无限集称为可数集或可列集；非可数的集合称为不可数集

若$A$是可数集，则存在双射$f:{\mathbf{N}}_n\to A$或者$f:\mathbf{N}\to A$，因此$A$中的元素可无重复排列为$f\left(0\right),f\left(1\right),\cdots ,f\left(n-1\right)$或者$f\left(0\right),f\left(1\right),f\left(2\right),\cdots$，反之，若$A$中的元素能无重复地排列称$a_0,a_1,\cdots ,a_{n-1}$或者$a_0,a_1,a_2,\cdots$，则存在双射
$$f:{\mathbb{N}}_n\to A,f\left(i\right)=a_i$$
或者
$$f:\mathbb{N}\to A,f\left(i\right)=a_i$$
由此可见，$A$是可数集当且仅当$A$中所有元素可排列成一个无重复的序列，可以证明，“无重复”这一条件是可以省去的，也就是说，要证明一个集合是可数，只要证明该集合中的所有元素能够排成一个序列即可

例子1： $\mathbb{N}\times \mathbb{N}$是可数集
证明：

$$\begin{array}{ccccccc}⟨0,0⟩& & ⟨0,1⟩& & ⟨0,2⟩& & \cdots \\ & \swarrow & & \swarrow & & \swarrow & \\ ⟨1,0⟩& & ⟨1,1⟩& & ⟨1,2⟩& & \cdots \\ & \swarrow & & \swarrow & & & \\ ⟨2,0⟩& & ⟨2,1⟩& & ⟨2,2⟩& & \cdots \\ & \swarrow & & & & & \\ ⋮& & ⋮& & ⋮& & \end{array}$$

$f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$
$$f\left(m,n\right)=\frac{\left(m+n\right)\left(m+n+1\right)}{2}+m$$

定理1： 可数集的任何子集都是可数集
定理2： 可数个可数集的并集是可数集

定理3 若$A$和$B$是可数集，则$A\times B$是可数集
证明：因为$A$和$B$是可数集，不妨设 A = { a 0 , a 1 , ⋯   } A = \left\{a_0,a_1,\cdots\right\} A={
a0​,a1​,⋯}和 B = { b 0 , b 1 , ⋯   } B = \left\{b_0,b_1,\cdots\right\} B={
b0​,b1​,⋯}
（若是有限集则重复最后一个元素，那么$A\times B$中所有元素可排列为）

$$\begin{array}{ccccccc}⟨a_0,b_0⟩& & ⟨a_0,b_1⟩& & ⟨a_0,b_2⟩& & \cdots \\ & \swarrow & & \swarrow & & \swarrow & \\ ⟨a_1,b_0⟩& & ⟨a_1,b_1⟩& & ⟨a_1,b_2⟩& & \cdots \\ & \swarrow & & \swarrow & & & \\ ⟨a_2,b_0⟩& & ⟨a_2,b_1⟩& & ⟨a_2,b_2⟩& & \cdots \\ & \swarrow & & & & & \\ ⋮& & ⋮& & ⋮& & \end{array}$$
按上面的方式，可将$A\times B$的所有元素排列成一个序列，故$A\times B$是可数的

同理可证若$A$是可数集，则$A^n$也是可数集

定理4： 实数集合的子集$\left[0,1\right]$不是可数无限集合
证明：设$f:\mathbb{N}\to \left[0,1\right]$我们把$f$的值顺序排列为十进制小数：
$$\begin{array}{rl}f\left(0\right)& =0.x_{00}{x}_{01}{x}_{02}\cdots ,\\ f\left(1\right)& =0.x_{10}{x}_{11}{x}_{12}\cdots ,\\ \cdots & \end{array}$$
其中$0\le x_{ij}\le 9\left(i,j\in \mathbb{N}\right)$
构造$y=0.y_0{y}_1{y}_2\cdots$
$$y_i=\{\begin{array}{ll}1,& x_{ii}\ne 1\\ 2,& x_{ii}=1\end{array}$$
$y\in \left[0,1\right]$但是$y\notin f\left(\mathbb{N}\right)$
$f$不满射

这个方法叫康托对角线法

$\left\{0,\frac{1}{1},\frac{1}{2},\frac{1}{3},\cdots \right\}\subseteq \left[0,1\right]$可见不是有限集

设$A$是任意集合，若$\left[0,1\right]\sim A$,则称$A$的基数为$\aleph$，并称$A$是具有连续统势的集合，记为$\left|A\right|=\aleph$

定理5 设$A,B,C$和$D$是任意集合，$A\sim B,C\sim D,A\cap C=B\cap D=\varnothing$，则$A\cup C\sim B\cup D$

证明：由于$A\sim B,C\sim D$，存在双射$f_1:A\to B$和$f_2:C\to D$
令
$$\begin{gathered} f:A\cup C\to B\cup D \\ f\left(x\right)=\{\begin{array}{ll}{f}_1\left(x\right),& x\in A\\ f_2\left(x\right),& x\in C\end{array} \end{gathered}$$
因为$A\cap C=\varnothing$,所以$f$是一个函数，下面证明$f$双射
（1）f是满射，对任意的$y\in B\cup D$,则有$y\in B\vee y\in D$
若$y\in B$，因为$f_1$满射，所以有$x\in A$使$y=f_1\left(x\right)$，即$x\in A\cup C$，使$y=f_1\left(x\right)=f\left(x\right)$
若$y\in D$，同理
故$f$满射

（2）f单射。对任意的$x_1,x_2\in A\cup C$，若$f\left(x_1\right)=f\left(x_2\right)$，那么
若$f\left(x_1\right)=f\left(x_2\right)\in B$,则因为$f\left(A\right)=B,f\left(C\right)=D,B\cap D=\varnothing$, 有$x_1,x_2\in A$
所以$f\left(x_1\right)=f_1\left(x_1\right),f\left(x_2\right)=f_1\left(x_2\right)$,即$f_1\left(x_1\right)=f_1\left(x_2\right)$
又因为$f_1$单射，$x_1=x_2$

若$f\left(x_1\right)=f\left(x_2\right)\in D$，同理可证$x_1=x_2$
$f$单射

所以$A\cup C\sim B\cup D$

课后习题

1.设$A$和$B$是无限集，$C$是有限集，下列集合是否一定为无限集合？为什么？
（1）$A\cap B$
（2）$A-B$
（3）$A\cup C$
（4）$A-C$
解：
（1）不一定
${\mathbb{E}}_v\cap {\mathbb{O}}_v=\varnothing$
(2)不一定
$A-A=\varnothing$
(3)一定
(4)一定

4.设$A$是可数无限集，$B$是有限集。求下列集合的基数，并证明你的结论
（1）$A\cup B$
（2）$A-B$

因此$\left|A\right|=\left|A\cup B\right|={\aleph }_0$
(2)
设 A = { a 0 , a 1 , ⋯   } A=\left\{a_0, a_1,\cdots\right\} A={
a0​,a1​,⋯}
不妨假设 A − B = { a u 0 , a u 1 , ⋯   } A-B=\left\{a_{u_0},a_{u_1},\cdots\right\} A−B={
au0​​,au1​​,⋯}

构造双射函数$f:A\to A\cup B$
$$f\left(a_i\right)=a_{u_i}$$
因此$\left|A\right|=\left|A-B\right|={\aleph }_0$