無限集與可數集

• 有限的集合直觀定義為若將該集合元素一個一個地數，必定可以將元素數盡。因此無限多個元素即無法經由一個一個地數來數盡所有的元素。

• 定義: 集合等價或基數相同。
  • $A,\ B$為二集合。
  • 若$A,\ B$間存在一對一且映成的函數$f: A \rightarrow B$，則稱$A$與$B$等價(equivalent)，或兩集合基數相同(have the same cardinal number)，以$A \sim B$表示。
• Theorem:等價關係的基本性質。
  • 反身性(reflexive): $\forall A,\ A \sim A$.
  • 對稱性(symmetric): $\forall A,\ B, \ A \sim B \Rightarrow B \sim A$.
  • 遞移性(transitive): $\forall A,\ B,\ C, \ A \sim B, \text{ and } B \sim C \Rightarrow A \sim C$.

  • E.g. 整數集$\mathbb{Z}$與自然數集$\mathbb{N}$等價。

    • 定義函數 $f: \mathbb{Z} \rightarrow \mathbb{N}$.
    • $\forall n \in \mathbb{N}, f(n) = \begin{cases} n/2 & n \text{ is even}, \\ -(n-1)/2 & n \text{ is odd}. \end{cases}$. (QED)
    • 雖然自然數集是整數集的子集合，但因兩者是無限集，且可以找到一對一且映成的函數，所以兩個集合大小相等。

  • E.g $N \times N$與自然數 $\mathbb{N}$等價。

    • 定義函數： $f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$.
    • $\forall (m,n) \in \mathbb{N} \times \mathbb{N},\ f(m,n) = (m+n-2)(m+n-1)/2 + m$.

  • E.g. 實數集 $\mathbb{R}$與 $(-1, 1)$等價。

    • 定義函數 $f(x) = \frac{x}{(1+ |x|}$ 或 $g(x) = 2/\pi \tan^{-1}x$ 都是一對一且映成的函數。

  • E.g. $\forall a, b \in \mathbb{R},\ a < b$，則 $(a,b)$與 $(0,1)$等價。

    • 定義函數 $f(x) = (x-a)/(b-a)$即可。
    • 同上， $[a,b], [a,b), (a,b]$均與 $(0,1)$等價。
    • 所有實數上的有限區間都兩兩等價。

  • E.g. 區間 $[0,1]$ 與集合 $[0,1] \times [0,1]$ 等價。

  • E.g. Cantor集合 $C$ 與正整數集合 $\mathbb{N}$ 不等價。

    • Proof: 只需證明由 $\mathbb{N}$ 至 $C$的每個函數都不是映成函數即可。
    • 令函數 $f: \mathbb{N} \rightarrow C$, 則 $\forall m \in \mathbb{N} \exists \lbrace a_{mn} \rbrace_{n=1}^{\infty}$為由0與2所成的數列，使得 $f(m) = \sum_{n=1}^{\infty} \frac{a_{mn}}{3^n}$.
    • 定義一數列 $\lbrace b_n \rbrace$為 $\forall n \in \mathbb{N}, \ b_n = 2 - a_{mn}$。
    • 則 $\forall n \in \mathbb{N},\ b_n = 0 \text{ or } 2$.
    • $\therefore x = \sum_{n=1}^{\infty} (b_n / 3^n)$為Cantor集合 $C$中的元素。
    • 然而 $\forall n \in \mathbb{N}, \ a_{mn} \neq b_n$，所以 $x \neq f(n)$，即 $x \in C$ 但 $x$不是函數 $f$值域的元素(QED)。

  • E.g. 對任意集合 $S$， $S$與其冪集合(power set) $P(S)$不等價。

    • Proof: 只須證明由 $S$至 $P(S)$ 的所有函數都不會是映成函數即可。
    • 令 函數 $f: S \rightarrow P(S)$，且集合 $Q = \{s \in S | s \notin f(s) \}$。
    • 由定義可知 $Q \subseteq S$，且 $Q \in P(S)$.
    • 因為$\forall s \in Q \text{ and } s \notin f(s) \Rightarrow Q \neq f(s)$.
    • 而對於$S-Q$中每個元素$q$而言，$q \notin Q \text{ and } q \in f(q) \Rightarrow Q \neq f(q)$。
    • 所以 $Q$不屬於$f$的值域(QED)。

有限集與無限集

• $\forall k \in \mathbb{N}$, 定義 $N_k = \{ 1,2, \cdots, k\}$.
• 定義：無限集合(infinite set)
  • 令 $S$為一集合。
  • 若存在正整數 $k \in \mathbb{N} \ni S \sim N_k$，則稱$S$為有限集合(finite set)，此時 $S$有 $k$個元素，記為 $|S| = k$.
  • 空集合 $\phi$ 定義為有限集合。
  • 若$S$不是有限集合，則稱 $S$為無限集合 (infinite set)
  • 根據定義，若 $S$為非空有限集合，且 $S \sim \mathbb{N}_k$，則必存在一個函數 $f: \mathbb{N}_k \rightarrow S \ni S = \{ f(1), f(2), \cdots, f(k) \}$.

• Theorem:有限集的子合必定是有限集</

• Theorem: 若 $S$為有限集，則 $S$不會與其任何真子集等價。
  • 此定理在無限集合時不成立。
• Theorem:自然數集合的性質
  • $k,l \in \mathbb{N}, k \neq l$，則 $\mathbb{N}_k$與 $\mathbb{N}_l$不等價。
  • $\mathbb{N}$為無限集，因此 $\mathbb{N}$與任何 $\mathbb{N}_k$都不等價。

無限集合的充要條件

• Theorem:無限集合的充要條件之一
  • 集合 $S$為無限集合的充要條件是存在一對一函數 $f: \mathbb{N} \rightarrow S$.

• Theorem:無限集合的充要條件之二
  • 集合 $S$為無限集合的充要條件是 $S$與其某個真子集等價。

可數集合與不可數集合

• 在無限集合間，元素的數量不完全相同，E.g. Cantor集合與自然數集合元素個數不同。
• 定義：可數與不可數集合
  • 若集合 $S$與正整數 $\mathbb{N}$等價時，則稱集合 $S$為一個可數無限集 (countable infinite set).
  • 若集合 $S$ 是有限集或是可數無限集時，稱 $S$為可數集( countable set).
  • 若集合 $S$不是可數集，則稱 $S$為不可數集 （uncountable set).
• Theorem:可數集的子集必定是可數集。
• Theorem:可數個可數集合的聯集仍為可數集。
  • i $\forall n \in \mathbb{N},\ S_n$為可數集，則 $\cup_{n=1}^{\infty} S_n$也是可數集。
  • 有理數 $\mathbb{Q}$為可數集合。
    • Proof: $\forall n \in \mathbb{N}, \ S_n = \{ m/n | m \in \mathbb{Z} \}$
    • 則 $S_n$與整數集合 $\mathbb{Z}$等價，因此 $S_n$為可數集。
    • 而有理數集合 $\mathbb{Q} = \cup_{n=1}^{\infty} S_n$，所以也為可數集(QED)。
• Theorem:可數集
  • 若 $A$ 為可數集合，且 $f: A \rightarrow B$為映成函數，則 $B$為可數集合。

代數數與超越數

• 若一複數 $a \in \mathbb{C}$為某個有理數方程式 $a_n x^n + a_{n-1}x^{n-1} + \cdots + a_0 = 0$的根，其中 $a_0, a_1, \cdots, a_n$為有理數，則 $a$稱為代數數(algebraic number)。

  • 代數數所形成的集合為可數集。
  • 若一數不為代數數時，則稱為超越數(transcedental number)，如 $\pi, e$。
• Theorem
  • 若 $A$為不可數集，而 $B$為可數集，則 $A-B$與 $A$等價。
  • 此定理指出超越數(不可數)比代數數(可數)多。

Schroder-Bernstein定理