无限集合

定义

直观定义

不是有限集合的集合，即由无限个元素组成的集合，称为无限集合，简称无限集

用于证明的定义

给定 $\mathbf N_k=\{0,1,2,\cdots,k-1\},\ k\in\mathbf Z$，对于集合 $A$，若对任意 $k\in\mathbf Z$ 都不存在双射函数 $f:\mathbf N_k\rightarrow A$，则称 $A$ 是无限集

类别

可数集

与自然数集 $\mathbf N$ 等势的集合称为可数无限集，简称可数集
如：整数集 $\mathbf Z$ 是可数集

因为可构造双射函数

$$f:\mathbf N\rightarrow \mathbf N,\ f(x)=\begin{cases}\frac{x}{2},&x 为偶数\\ -\frac{x+1}{2},&x 为奇数 \end{cases}$$

可数集和有限集统称为至多可数集

关于可数集有如下定理：

1. 可数集的任意无限子集是可数集
2. $A$ 为可数无限集 $\Leftrightarrow$ 存在 $A$ 的枚举

   证明：

   1. $A$ 为可数无限集 $\Rightarrow$ 存在 $A$ 的枚举
      $\because$ $A$ 为可数无限集
      $\therefore$ 存在双射函数 $f:\mathbf N\rightarrow A$
      $f$ 即为 $A$ 的枚举，得证
   2. $A$ 为可数无限集 $\Leftarrow$ 存在 $A$ 的枚举
      $\because$ 存在 $A$ 的枚举，而 $A$ 为无限集
      $\therefore$ 存在满射函数 $f:\mathbf N\rightarrow A$
      下面是通过 $f$ 构造双射函数 $g$ 的算法

3. 可数个可数集的并是可数集

不可数集

与自然数集 $\mathbf N$ 不等势的集合称为不可数无限集，简称不可数集
如：实数集的子集 $(0,1)$ 为不可数集

用反证法证明
假设 $(0,1)\sim\mathbf N$
则存在双射函数 $f:\mathbf N\rightarrow (0,1)$
$f(0),f(1),\cdots,f(n)\in(0,1),\cdots$ 可表示为：

$$\begin{aligned} &f(0)=0.x_{00}x_{01}x_{02}x_{03}\cdots\\ &f(1)=0.x_{10}x_{11}x_{12}x_{13}\cdots\\ &f(2)=0.x_{20}x_{21}x_{22}x_{23}\cdots\\ &~~~~~~~~~~\vdots \end{aligned}$$

构造 $y=0.y_0y_1y_2y_3\cdots$，其中 $y_i\neq x_{ii}$
显然 $y\in(0,1)$，但 $\forall n\in\mathbf N,\ y\neq f(n)$
因此函数 $f$ 不是满射函数，不可能是双射函数，与假设相矛盾

大小（基数或势）

若无限集是可数集，则其大小为阿列夫零，记作 $\aleph_0$
如：正整数集 $\mathbf Z$ 的大小 $|\mathbf Z|=\aleph_0$

若无限集是不可数集，则其大小为阿列夫，记作 $\aleph$
如：实数集的子集 $(0,1)$ 的大小 $|(0,1)|=\aleph$

无限集存在与其等势的真子集

$A$ 是任意无限集，从 $A$ 拿出一系列元素 $\{a_0,a_1,\cdots, a_n,\cdots\}$ 后剩余元素的集合 $B=A-\{a_0,a_1,\cdots, a_n,\cdots\}$ 也是无限集，则 $A=B\cup\{a_0,a_1,\cdots, a_n,\cdots\}$
取 $C=B\cup\{a_1,\cdots, a_n,\cdots\}$（没有 $a_0$），显然 $C$ 是 $A$ 的真子集
可构造双射函数

$$f:A\rightarrow C,\ \begin{cases} f(x)=x,&x\in B\\ f(a_i)=f(a_{i+1}),&x\in\{a_0,a_1,\cdots, a_n,\cdots\} \end{cases}$$

因此 $C\sim A$

参考

[1] 离散数学西安电子科技大学出版社第二版
[2] 维基百科无限集合