集合论/可数性

命题（有限全序集的可数并是可数的）:

令 $(S_{n},\leq _{n})_{n\in \mathbb {N} }$ 是有限全序集的集合。则 $\cup _{n\in \mathbb {N} }S_{n}$ 是可数的或有限的。

证明：为了便于记号，定义 $T:=\cup _{n\in \mathbb {N} }S_{n}$。首先，我们断言我们可以假设 $S_{n}$ 是不相交的。事实上，如果 $S_{n}$ 不相交，定义一个新的集合族如下：令 $S'_{1}:=S_{1}$，一旦 $S'_{1},\ldots ,S'_{n}$ 被定义，令 $S'_{n+1}:=S_{n+1}\setminus \cup _{k\leq n}S_{k}$。现在从 $(S_{n})_{n\in \mathbb {N} }$ 中删除所有空集。要么只有有限个集合留下来，并且并集是有限的，要么留下了可数个集合，这样我们就有了一个可数个不相交非空有限集的族。注意，每个 $S_{n}$ 上的全序产生了 $S_{n}$ 元素的编号，因此我们可以写 $S_{n}=\{s_{n,1},\ldots ,s_{n,k_{n}}\}$ 我们定义一个双射 $f:T\to \mathbb {N}$ 如下

$f(s_{n,j}):=\sum _{l=1}^{n-1}|S_{l}|+j$.

这是单射的，因为如果 $f(s_{n,j})=f(s_{n',j'})$，则

$\sum _{l=1}^{n-1}|S_{l}|+j=\sum _{l=1}^{n'-1}|S_{l}|+j'$;

例如，如果我们有$n<n'$，那么请注意$j\leq |S_{n}|$，因此我们必须有$j'=0$，这是一个矛盾，因此$n=n'$，因此$j=j'$，所以$s_{n,j}=s_{n',j'}$。此外，它是满射的，因为只要$m\in \mathbb {N}$，选择最大$n$，使得

$\sum _{l=1}^{n}|S_{l}|<m$

然后

$j:=m-\sum _{l=1}^{n}|S_{l}|$;

注意$j\leq |S_{n}|$，否则我们将得到$n$最大性的矛盾。因此，我们有一个双射。$\Box$

命题（有限集的可数并集是可数的当且仅当可数有限选择公理成立）:

当且仅当每个有限集的可数并集$\cup _{n\in \mathbb {N} }S_{n}$最多是可数的时，可数有限选择公理才成立。

证明： 利用可数有限选择公理，在每个 $S_{n}$ 上选择一个全序，并利用 可数个有限全序集的并集是可数的。对于另一个方向，令 $(S_{n})_{n\in \mathbb {N} }$ 为非空有限集的序列，并选择 $\cup _{n\in \mathbb {N} }S_{n}$ 的一个编号（它也可能是有穷的，但如果那样，也可以选择一个编号）。然后定义序列 $(x_{n})_{n\in \mathbb {N} }$ 如下：$x_{n}$ 将是 $S_{n}$ 中具有最小编号的元素。那么 $(x_{n})_{n\in \mathbb {N} }$ 是可数有限选择公理所要求的序列。 $\Box$

命题（自然数的有限子集的集合是可数的）:

令 $S:=\{T\subseteq \mathbb {N} |T{\text{ finite }}\}$。则 $S$ 是可数的。

证明： 我们写

$S=\bigcup _{n\in \mathbb {N} _{0}}S_{n}$，Failed to parse (unknown function "\middle"): {\displaystyle S_n := \left\{T \subseteq \mathbb N \middle| |T| = n\}} 。

每个 $S_{n}$ 都有一个 全序，即 Order Theory/Lexicographic order#词典序，它是全序的。因此，我们可以应用 可数个有限全序集的并集是可数的 的事实。 $\Box$