Countable sets

前面有提到正整數可以用來作為有限集的原型，我們會把所有正整數的集合稱為 可數無限集（countably infinite sets）。

Def.

A set A is infinite if not finite.

Def.

A set A is countably infinite if

$$\exists f: A \rightarrow \mathbb{N}, f \enspace is \enspace bijective.$$

ex.

像是整數本身就是 countably infinite，$f: \mathbb{Z} \rightarrow \mathbb{N}$

$$f(n) = \begin{cases} 2n & n\gt 0 \ -2n+1 & n \le 0 \end{cases}$$

ex.

$\mathbb{N} \times \mathbb{N}$ 也是 countably infinite，那要如何證明呢？

我們需要證明 $f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$，由於 $\mathbb{N} \times \mathbb{N}$ 是在座標系的第1象限上的格子點，我們先把他向下圖一樣定一個順序，下圖的順序也包含 0，但是在我們的例子中不包含 0，但概念是一樣的。

我們希望像這樣把 $\mathbb{N}$ 一個一個擺到 $\mathbb{N} \times \mathbb{N}$，這樣我們就可以確認兩者的對應關係了，那要怎麼做呢？

我們先定個函數 $g(x, y) = (x + y - 1 , y)$，這會把每串黑色箭頭都擺直。

接著可以用另一個函數 $h(x , y) = \frac{1}{2}(x - 1)x + y$ 幫我們對映到數字。

對映關係會看起來像這樣：

$(1, 1) \rightarrow (1, 1) \rightarrow 1$

$(2, 1) \rightarrow (2, 1) \rightarrow 2$

$(1, 2) \rightarrow (2, 2) \rightarrow 3$

$(3, 1) \rightarrow (3, 1) \rightarrow 4$

$(2, 2) \rightarrow (3, 2) \rightarrow 5$

如此對映起來之後，再證明這兩個函數的組合是雙射的，就可以證明 $\mathbb{N} \times \mathbb{N}$ 是 countably infinite。

所以我們就可以給可數下個定義：

Def.

A set A is countable if it is finite or countably infinite.

A set A is uncountable if it is not countable.

那如果我們每次都要證明一個集合是不是可數的就會比較麻煩，以下有些等價的敘述：

Theroem

A is a nonempty set.

1. A is countable
2. $\exists f: \mathbb{N} \rightarrow A$, f is surjective
3. $\exists g: A \rightarrow \mathbb{N}$, g is injective

我們有其他定理：

Theroem

$$C \subseteq \mathbb{N}, C \enspace is \enspace infinite, then \enspace C \enspace is \enspace countably \enspace infinite.$$

跟其他結論：

Corollary

A subset of a countable set is countable.

Corollary

$\mathbb{N} \times \mathbb{N}$ is countably infinite.

Theroem

A countable union of countable sets is countable.

看到這邊大家不知道有沒有跟我一樣的疑問，為什麼會有 countable union 這樣的敘述呢？

如果有個集合 $A_n$ 是可數的，$f_n$ is surjective，$f_n: \mathbb{N} \rightarrow A_n$，我們可以選另一個函數 $g$ is surjective，$g: \mathbb{N} \rightarrow J$，使得

$$h: \mathbb{N} \times \mathbb{N} \rightarrow \bigcup_{n \in J} A_n$$

所以我們把 countable union 看成在 $n \in J$ 的 $J$，$h$ 可以看成 $f_n$ 跟 $g$ 的合成函數 $h(k, m) = f_{g(k)}(m)$，如此一來，我們已經知道 surjective 函數的合成還是 surjective，而 $\mathbb{N} \times \mathbb{N}$ 也是 countable，這樣我們就可以證明 $\bigcup_{n \in J} A_n$ 是 countable。

Theroem

A finite product of countable sets is countable.

也就是說，$A_1 \times A_2 \times … \times A_n$ 是 countable。

Theroem

$$X = \{ 0, 1 \}, then \enspace X^\omega \enspace is \enspace uncountable.$$

這邊描述了一個特例，以下是比較廣義的敘述：

Theroem

$A$ is a set,

$$\nexists \enspace injective \enspace f: \mathcal{P}(A) \rightarrow A$$

$$\nexists \enspace surjective \enspace g: A \rightarrow \mathcal{P}(A)$$

這代表著一個集合的冪集是 uncountable set，無論集合裏面長什麼樣子。