無限集與可數集
有限的集合直觀定義為若將該集合元素一個一個地數,必定可以將元素數盡。因此無限多個元素即無法經由一個一個地數來數盡所有的元素。
- 定義: 集合等價或基數相同。
- 為二集合。
- 若間存在一對一且映成的函數,則稱與等價(equivalent),或兩集合基數相同(have the same cardinal number),以表示。
- Theorem:等價關係的基本性質。
- 反身性(reflexive): .
- 對稱性(symmetric): .
- 遞移性(transitive): .
E.g. 整數集與自然數集等價。
- 定義函數 .
- . (QED)
- 雖然自然數集是整數集的子集合,但因兩者是無限集,且可以找到一對一且映成的函數,所以兩個集合大小相等。
E.g 與自然數 等價。
- 定義函數: .
- .
E.g. 實數集 與 等價。
- 定義函數 或 都是一對一且映成的函數。
E.g. ,則 與 等價。
- 定義函數 即可。
- 同上, 均與 等價。
- 所有實數上的有限區間都兩兩等價。
E.g. 區間 與集合 等價。
E.g. Cantor集合 與正整數集合 不等價。
- Proof: 只需證明由 至 的每個函數都不是映成函數即可。
- 令函數 , 則 為由0與2所成的數列,使得 .
- 定義一數列 為 。
- 則 .
- 為Cantor集合 中的元素。
- 然而 ,所以 ,即 但 不是函數 值域的元素(QED)。
E.g. 對任意集合 , 與其冪集合(power set) 不等價。
- Proof: 只須證明由 至 的所有函數都不會是映成函數即可。
- 令 函數 ,且集合 。
- 由定義可知 ,且 .
- 因為.
- 而對於中每個元素而言,。
- 所以 不屬於的值域(QED)。
有限集與無限集
- , 定義 .
- 定義:無限集合(infinite set)
- 令 為一集合。
- 若存在正整數 ,則稱為有限集合(finite set),此時 有 個元素,記為 .
- 空集合 定義為有限集合。
- 若不是有限集合,則稱 為無限集合 (infinite set)
- 根據定義,若 為非空有限集合,且 ,則必存在一個函數 .
- Theorem:有限集的子合必定是有限集</
- Theorem: 若 為有限集,則 不會與其任何真子集等價。
- 此定理在無限集合時不成立。
- Theorem:自然數集合的性質
- ,則 與 不等價。
- 為無限集,因此 與任何 都不等價。
無限集合的充要條件
- Theorem:無限集合的充要條件之一
- 集合 為無限集合的充要條件是存在一對一函數 .
- Theorem:無限集合的充要條件之二
- 集合 為無限集合的充要條件是 與其某個真子集等價。
可數集合與不可數集合
- 在無限集合間,元素的數量不完全相同,E.g. Cantor集合與自然數集合元素個數不同。
- 定義:可數與不可數集合
- 若集合 與正整數 等價時,則稱集合 為一個可數無限集 (countable infinite set).
- 若集合 是有限集或是可數無限集時,稱 為可數集( countable set).
- 若集合 不是可數集,則稱 為不可數集 (uncountable set).
- Theorem:可數集的子集必定是可數集。
- Theorem:可數個可數集合的聯集仍為可數集。
- i 為可數集,則 也是可數集。
- 有理數 為可數集合。
- Proof:
- 則 與整數集合 等價,因此 為可數集。
- 而有理數集合 ,所以也為可數集(QED)。
- Theorem:可數集
- 若 為可數集合,且 為映成函數,則 為可數集合。
Cantor集合與實數集 等價。
代數數與超越數
若一複數 為某個有理數方程式 的根,其中 為有理數,則 稱為代數數(algebraic number)。
- 代數數所形成的集合為可數集。
- 若一數不為代數數時,則稱為超越數(transcedental number),如 。
- Theorem
- 若 為不可數集,而 為可數集,則 與 等價。
- 此定理指出超越數(不可數)比代數數(可數)多。
Schroder-Bernstein定理
- Theorem
- 三集合 滿足 .
- 設 為兩集合,若 至間存在一對一函數,且由 至 也存在一對一函數,則