無限集與可數集

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

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

      • 定義函數 f:ZN f: \mathbb{Z} \rightarrow \mathbb{N} .
      • nN,f(n)={n/2n is even,(n1)/2n is odd. \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×N N \times N 與自然數 N \mathbb{N} 等價。

      • 定義函數: f:N×NN f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} .
      • (m,n)N×N, f(m,n)=(m+n2)(m+n1)/2+m \forall (m,n) \in \mathbb{N} \times \mathbb{N},\ f(m,n) = (m+n-2)(m+n-1)/2 + m .
    • E.g. 實數集 R \mathbb{R} (1,1) (-1, 1) 等價。

      • 定義函數 f(x)=x(1+x f(x) = \frac{x}{(1+ |x|}g(x)=2/πtan1x g(x) = 2/\pi \tan^{-1}x 都是一對一且映成的函數。
    • E.g. a,bR, a<b \forall a, b \in \mathbb{R},\ a < b ,則 (a,b) (a,b) (0,1) (0,1) 等價。

      • 定義函數 f(x)=(xa)/(ba) f(x) = (x-a)/(b-a) 即可。
      • 同上, [a,b],[a,b),(a,b] [a,b], [a,b), (a,b] 均與 (0,1) (0,1) 等價。
      • 所有實數上的有限區間都兩兩等價。
    • E.g. 區間 [0,1] [0,1] 與集合 [0,1]×[0,1] [0,1] \times [0,1] 等價。

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

      • Proof: 只需證明由 N \mathbb{N} C C 的每個函數都不是映成函數即可。
      • 令函數 f:NC f: \mathbb{N} \rightarrow C , 則 mN{amn}n=1 \forall m \in \mathbb{N} \exists \lbrace a_{mn} \rbrace_{n=1}^{\infty} 為由0與2所成的數列,使得 f(m)=n=1amn3n f(m) = \sum_{n=1}^{\infty} \frac{a_{mn}}{3^n}.
      • 定義一數列 {bn} \lbrace b_n \rbrace nN, bn=2amn \forall n \in \mathbb{N}, \ b_n = 2 - a_{mn}
      • nN, bn=0 or 2 \forall n \in \mathbb{N},\ b_n = 0 \text{ or } 2 .
      • x=n=1(bn/3n) \therefore x = \sum_{n=1}^{\infty} (b_n / 3^n) 為Cantor集合 C C 中的元素。
      • 然而 nN, amnbn \forall n \in \mathbb{N}, \ a_{mn} \neq b_n ,所以 xf(n) x \neq f(n) ,即 xC x \in C x x 不是函數 f f 值域的元素(QED)。
    • E.g. 對任意集合 S S S S 與其冪集合(power set) P(S) P(S) 不等價。

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

有限集與無限集

  • kN \forall k \in \mathbb{N} , 定義 Nk={1,2,,k} N_k = \{ 1,2, \cdots, k\} .
    • 定義:無限集合(infinite set)
    • S S 為一集合。
    • 若存在正整數 kNSNk k \in \mathbb{N} \ni S \sim N_k,則稱SS為有限集合(finite set),此時 S S k k 個元素,記為 S=k |S| = k .
    • 空集合 ϕ \phi 定義為有限集合。
    • S S 不是有限集合,則稱 S S 為無限集合 (infinite set)
    • 根據定義,若 S S 為非空有限集合,且 SNk S \sim \mathbb{N}_k ,則必存在一個函數 f:NkSS={f(1),f(2),,f(k)} f: \mathbb{N}_k \rightarrow S \ni S = \{ f(1), f(2), \cdots, f(k) \} .
  • Theorem:有限集的子合必定是有限集</

  • Theorem: 若 S S 為有限集,則 S S 不會與其任何真子集等價。

    • 此定理在無限集合時不成立。
    • Theorem:自然數集合的性質
    • k,lN,kl k,l \in \mathbb{N}, k \neq l ,則 Nk \mathbb{N}_k Nl \mathbb{N}_l 不等價。
    • N \mathbb{N} 為無限集,因此 N \mathbb{N} 與任何 Nk \mathbb{N}_k 都不等價。

無限集合的充要條件

    • Theorem:無限集合的充要條件之一
    • 集合 S S 為無限集合的充要條件是存在一對一函數 f:NSf: \mathbb{N} \rightarrow S .
    • Theorem:無限集合的充要條件之二
    • 集合 S S 為無限集合的充要條件是 S S 與其某個真子集等價。

可數集合與不可數集合

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

代數數與超越數

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

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

Schroder-Bernstein定理

    Theorem
  1. 三集合 A,B,C A,B,C 滿足 ABC and ACAC A \supset B \supset C \text{ and } A \sim C \Rightarrow A \sim C.
  2. A,b A,b 為兩集合,若 A ABB 間存在一對一函數,且由 BBAA 也存在一對一函數,則AB A \sim B

results matching ""

    No results matching ""