集合論/可數性

命題（有限全序集的可數並是可數的）:

令 $(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$