論集合 - Uwni'Space

閱讀本文需備初等數學基礎、並略知邏輯與集合論．

ZFC 公理

若夫集合者、聚同屬之物也．

命題 1.

（内涵公理）

設 $𝜑$ 為一元謂辭

\exists 𝐴 \forall 𝑥 (𝑥 \in 𝐴 \leftrightarrow 𝜑 (𝑥))

(1)

然則、適 $𝜑$ 者皆見於 $𝐴$ 、 $𝐴$ 之所有悉適 $𝜑$ 也．記

𝐴 = {𝑥 | 𝜑 (𝑥)}

(2)

查察下例

例 1.

（Russell's 悖論）

設

𝑋 = {集合未嘗言及於本文者}

(3)

則 $𝑋 \notin 𝑋$ 、無己之集也．聚此屬以為一集

𝐴 = {𝑥 | 𝑥 \notin 𝑥}

(4)

則此集有己乎？ $𝐴 \in 𝐴 \leftrightarrow 𝐴 \notin 𝐴$ 故悖論也．

是以宜畧為限．

命題 2.

（分離公理模式）

設 $𝜑$ 為一元謂辭

\forall 𝐴 \exists 𝐵 \forall 𝑢 (𝑢 \in 𝐵 \leftrightarrow 𝑢 \in 𝐴 \land 𝜑 (𝑢))

(5)

內涵公理許擬集以任意謂詞、致生悖論．而依分離公理則止得分自既有之母集 $𝐵$ 也．依然設 $𝜑 (𝑢) = 𝑢 \notin 𝑢$ 、凡集合 $𝐴$ 、子集 $𝑅_{𝐴} = {𝑥 \in 𝐴 | 𝑥 \notin 𝑥}$ 集也．以排中律或 $𝑅_{𝐴} \in 𝑅_{𝐴}$ 或 $𝑅_{𝐴} \notin 𝑅_{𝐴}$ ．代入分離公理得： $𝑅_{𝐴} \in 𝑅_{𝐴} \leftrightarrow (𝑅_{𝐴} \in 𝐴 \land 𝑅_{𝐴} \notin 𝑅_{𝐴})$ 、若 $𝑅_{𝐴} \in 𝑅_{𝐴}$ 則 $𝑅_{𝐴} \notin 𝑅_{𝐴}$ 、此似反也、非反也； $𝑅_{𝐴} \notin 𝐴$ 故也．如是、凡集合常有子集之外乎己者、所謂莫有万全之集合也．

命題 3.

（外延公理）

\forall 𝐴 \forall 𝐵 (𝐴 = 𝐵 \leftrightarrow (\forall 𝑥, 𝑥 \in 𝐴 \leftrightarrow 𝑥 \in 𝐵))

(6)

外延公理謂集之相等以其元之相等爲準也．

集合代數

設 $𝐴$ 、 $𝐵$ 皆集也．納 $𝐴$ 及 $𝐵$ 之所有為一集、曰 $𝐴$ 與 $𝐵$ 之并集、記 $𝐴 \cup 𝐵$ ．

𝐴 \cup 𝐵 = {𝑥 | 𝑥 \in 𝐴 \lor 𝑥 \in 𝐵}

(7)

擇 $𝐴$ 及 $𝐵$ 之共有為一集、曰 $𝐴$ 與 $𝐵$ 之交集、記 $𝐴 \cap 𝐵$ ．

𝐴 \cap 𝐵 = {𝑥 | 𝑥 \in 𝐴 \land 𝑥 \in 𝐵}

(8)

$𝐴$ 之所有之不見於 $𝐵$ 者、曰 $𝐴$ 與 $𝐵$ 之差集、記 $𝐴 ∖ 𝐵$ ．

𝐴 ∖ 𝐵 = {𝑥 | 𝑥 \in 𝐴 \land 𝑥 \notin 𝐵}

(9)

子集與空集

設 $𝐴$ 集也．若分 $𝐴$ 為一新集 $𝐵$ 、曰 $𝐴$ 之子集、記 $𝐵 \subseteq 𝐴$ ．然則凡 $𝑏 \in 𝐵$ 者悉見於 $𝐴$ 也．

𝐵 \subseteq 𝐴 ≔ (\forall 𝑏 \in 𝐵) 𝑏 \in 𝐴

(10)

若 $𝐵 \subseteq 𝐴$ 且 $𝐵 = 𝐴$ 、則曰 $𝐵$ 為 $𝐴$ 之真子集、記 $𝐵 \subset 𝐴$ ．

集合無所有者曰空集、記 $\emptyset$ 、又 ${}$ ．凡集、 $\emptyset$ 皆其子集也．

證.

設

𝐴

集也．欲證

\emptyset \subseteq 𝐴

、即證

\forall 𝑥 (𝑥 \in \emptyset \to 𝑥 \in 𝐴)

．蓋

\emptyset

無元也、故前項為假而命題空真矣． ∎

集族

集合之集曰集族．凡集合 $𝑆$ 之子悉聚以為族、謂之冪集、記 $𝒫 (𝑆) ≔ {𝑥 | 𝑥 \subseteq 𝑆}$ ．譬若 $𝒫 {1, 2} = {{}, {1}, {2}, {1, 2}}$ ． $𝑆$ 子集之族曰子集族． $𝒫 (𝑆)$ 之子集也．

$ℱ$ 集族也．

⋃ ℱ ≔ ⋃_{𝐹 \in ℱ} 𝐹 ≔ {𝑥 | (\exists 𝐹 \in ℱ) 𝑥 \in 𝐹}

(11)

名曰 $ℱ$ 之一般並也． $ℱ$ 非空¹則謂

⋂ ℱ ≔ ⋂_{𝐹 \in ℱ} 𝐹 ≔ {𝑥 | (\forall 𝐹 \in ℱ) 𝑥 \in 𝐹}

(12)

曰 $ℱ$ 之一般交也．且較然易見

\begin{matrix} ⋃ {𝐴, 𝐵} = 𝐴 \cup 𝐵 \\ ⋂ {𝐴, 𝐵} = 𝐴 \cap 𝐵 \end{matrix}

(13)

若 $\forall 𝐴, 𝐵 \in ℱ, 𝐴 \neq 𝐵 \to 𝐴 \cap 𝐵 = \emptyset$ 則記 $⋃ ℱ$ 為 $⨆ ℱ$ ．曰不交並．

設 $ℱ \subseteq 𝒫 (𝑋)$ 、 $\emptyset \notin ℱ$ 、 $𝑋$ 之非空子集族也．

⨆ ℱ = 𝑋

(14)

則曰 $ℱ$ 為 $𝑋$ 之劃分．

元組與直積

夫有序對者、亦曰二元組、記 $(𝑎, 𝑏)$ ．所謂如下

(𝑎, 𝑏) ≔ {{𝑎}, {𝑎, 𝑏}}

(15)

遂

$(𝑏, 𝑎) = {{𝑏}, {𝑏, 𝑎}} \neq (𝑎, 𝑏)$
$(𝑎, 𝑎) = {{𝑎}, {𝑎, 𝑎}} = {{𝑎}, {𝑎}} = {{𝑎}} \neq {𝑎} = (𝑎)$

命題 4.

(𝑎_{1}, 𝑏_{1}) = (𝑎_{2}, 𝑏_{2}) \leftrightarrow 𝑎_{1} = 𝑎_{2} \land 𝑏_{1} = 𝑏_{2}

證.

(←) 較然可見．
(→) $𝑎_{1} = 𝑏_{1}$ 則

${{𝑎_{2}}, {𝑎_{2}, 𝑏_{2}}} = (𝑎_{2}, 𝑏_{2}) = (𝑎_{1}, 𝑏_{1}) = {{𝑎_{1}}}$
(16)

遂可見 ${𝑎_{2}} = {𝑎_{2}, 𝑏_{2}} = {𝑎_{1}} \to 𝑎_{2} = 𝑏_{2} = 𝑎_{1} = 𝑏_{1}$ ．

不然、 $𝑎_{1} \neq 𝑏_{1}$ 則

${{𝑎_{2}}, {𝑎_{2}, 𝑏_{2}}} = (𝑎_{2}, 𝑏_{2}) = (𝑎_{1}, 𝑏_{1}) = {{𝑎_{1}}, {𝑎_{1}, 𝑏_{1}}}$
(17)

䓁式右側集合有二元、左側亦宜然．遂 $𝑎_{2} \neq 𝑏_{2}$ ．而 ${𝑎_{2}} = {𝑎_{1}}$ , ${𝑎_{2}, 𝑏_{2}} = {𝑎_{1}, 𝑏_{1}}$ 可知矣．於是 $𝑎_{2} = 𝑎_{1}$ 且 $𝑏_{2} = 𝑏_{1}$ 也． ∎

若夫 $𝑎$ 所有于 $𝐴$ 、 $𝑏$ 所有于 $𝐵$ 者、遍聚二元組之集合謂之 $𝐴$ 與 $𝐵$ 之直積、記 $𝐴 \times 𝐵$ ．所謂如下

𝐴 \times 𝐵 ≔ {(𝑎, 𝑏) | 𝑎 \in 𝐴 \land 𝑏 \in 𝐵}

(18)

且可施及 $𝑛$ 集．

\begin{matrix} 𝐴_{1} \times \dots \times 𝐴_{𝑛} ≔ & {\begin{matrix} 𝐴_{1} & 若 𝑛 = 1 \\ (𝐴_{1} \times \dots \times 𝐴_{𝑛 - 1}) \times 𝐴_{𝑛} & 若 𝑛 > 1 \end{matrix} \end{matrix}

(19)

亦可記作 $\prod_{𝑖 = 1}^{𝑛} 𝐴_{𝑖}$ 、 $𝑛$ 維直積之元素稱為 $𝑛$ 元組．內層括弧可省、若

(𝑎_{1}, 𝑎_{2}, 𝑎_{3}, \dots, 𝑎_{𝑛}) ≔ (\dots ((𝑎_{1}, 𝑎_{2}), 𝑎_{3}), \dots, 𝑎_{𝑛})

(20)

關係

集合 $𝑅 \subseteq 𝐴 \times 𝐵$ 者、謂之 $𝐴$ 與 $𝐵$ 上之二元關係、畧以關係．若 $𝐴 = 𝐵$ 即 $𝑅 \subseteq 𝐴^{2}$ 則曰 $𝐴$ 上之關係． $(𝑎, 𝑏) \in 𝑅$ 則曰 $(𝑎, 𝑏)$ 適 $𝑅$ ．以中綴表達式記曰 $𝑎 𝑅 𝑏$ 、亦可記以前綴式並輔以括弧讀號、曰 $𝑅 (𝑎, 𝑏)$ ．

夫 $𝑅$ 之定義域者、

dom 𝑅 ≔ {𝑎 \in 𝐴 | (\exists 𝑏 \in 𝐵) 𝑎 𝑅 𝑏}

(21)

夫像域者、

im 𝑅 ≔ {𝑏 \in 𝐵 | (\exists 𝑎 \in 𝐴) 𝑎 𝑅 𝑏}

(22)

逆關係

𝑅^{- 1} ≔ {(𝑏, 𝑎) | (𝑎, 𝑏) \in 𝑅}

(23)

也．則 $dom 𝑅^{- 1} = im 𝑅$ 且 $im 𝑅^{- 1} = dom 𝑅$ ．二元關係 $𝑆$ 與 $𝑅$ 之複合謂以

𝑆 \circ 𝑅 ≔ {(𝑎, 𝑐) | \exists 𝑏 \in 𝐵, (𝑎, 𝑏) \in 𝑆 \land (𝑏, 𝑐) \in 𝑅}

(24)

例 2.

大學校園中、設

𝐴

為生集、

𝐵

為課程、

𝐶

為師集．則

𝑆 \subseteq 𝐴 \times 𝐵

為學生受業關係、

𝑅 \subseteq 𝐵 \times 𝐶

為教師受業關係．然則

𝑆 \circ 𝑅

為師生關係也．某生與某師有師生關係、則有某課師授而生受也．

䓁價關係

設 $\sim$ 爲集 $𝑆$ 上之二元關係．適三性如下列者謂 $𝑆$ 上之䓁價關係：

自反性： $(\forall 𝑠 \in 𝑆) 𝑠 \sim 𝑠$
對稱性： $(\forall 𝑠, 𝑡 \in 𝑆) 𝑠 \sim 𝑡 \to 𝑡 \sim 𝑠$
傳遞性： $(\forall 𝑠, 𝑡, 𝑢 \in 𝑆) 𝑠 \sim 𝑡 \land 𝑡 \sim 𝑢 \to 𝑠 \sim 𝑢$

設 $\sim$ 爲 $𝑆$ 上之䓁價關係、凡 $𝑠 \in 𝑆$ 、集合 ${[𝑠]}_{\sim} ≔ {𝑡 \in 𝑆 | 𝑠 \sim 𝑡}$ 名曰 $𝑠$ 之䓁價類． $𝑆$ 之䓁價類族曰商集、記 $𝑆 / \sim ≔ {{[𝑠]}_{\sim} | 𝑠 \in 𝑆}$ ．

命題 5.

𝑆

之䓁價關係與其劃分一一對應也

證.

設 $\sim$ 為䓁價關係之於 $𝑆$ ．商集 $𝑆 / \sim$ 為 $𝑆$ 之劃分也．證之如下

∎

恆䓁關係

記 $𝑆$ 上之恆䓁關係曰 ${id}_{𝑆}$

{id}_{𝑆} ≔ {(𝑠, 𝑠) | 𝑠 \in 𝑆}

(25)

若 $𝑆 = {♧, ♢, ♡}$ 、 ${id}_{𝑆} = {(♧, ♧), (♢, ♢), (♡, ♡)}$

恆䓁關係者、䓁價關係也．

偏序關係

$(𝑆, ⪯)$ 設以為結構之並以關係者、並有

自反性： $(\forall 𝑠 \in 𝑆) 𝑠 ⪯ 𝑠$
反對稱性： $(\forall 𝑠, 𝑡 \in 𝑆) 𝑠 ⪯ 𝑡 \land 𝑡 ⪯ 𝑠 \to 𝑠 = 𝑡$
傳遞性： $(\forall 𝑠, 𝑡, 𝑢 \in 𝑆) 𝑠 ⪯ 𝑡 \land 𝑡 ⪯ 𝑢 \to 𝑠 ⪯ 𝑢$

則 $⪯$ 名曰偏序關係．偏序關係之最小者、唯恆䓁關係也．不難證明之．

$id$ 適自反性、反對稱性、傳遞性、故爲偏序關係也．
凡 $(\forall 𝑠 \in 𝑆) id ∖ {(𝑠, 𝑠)}$ 之關係皆以有違自反性而非偏序關係也．故最小也
凡偏序關係必含 $id$ 也．可以歸謬法示其唯一也．

若夫偏序之匪䓁也、謂之嚴格偏序．記 $≺$ ． $𝑎 ≺ 𝑏 ≔ 𝑎 ⪯ 𝑏 \land 𝑎 \neq 𝑏$

最大與最小

$(𝑇, ⪯)$ 偏序之構也． $𝑠 \in 𝑇$ 、若夫

$\forall 𝑡 \in 𝑇, 𝑠 ⊀ 𝑡$ 、莫大於 $𝑠$ ． $𝑠$ 謂之極大．
$\forall 𝑡 \in 𝑇, 𝑡 ⊀ 𝑠$ 、莫小於 $𝑠$ ． $𝑠$ 謂之極小．
$\forall 𝑡 \in 𝑇, 𝑡 ⪯ 𝑠$ 、皆小於 $𝑠$ ． $𝑠$ 謂之最大、記 $\max 𝑇 = 𝑠$ ．
$\forall 𝑡 \in 𝑇, 𝑠 ⪯ 𝑡$ 、皆大於 $𝑠$ ． $𝑠$ 謂之最小、記 $\min 𝑇 = 𝑠$ ．

最大（小）者極大（小）也．

非空有窮偏序集者、偏序集之非空且有窮也．

極大（小）元常有．
最大（小）元不常有．若 $𝑇 = {♧, ♢, ♡}$ 、偏序關係 $⪯ = id$ ． $♧$ 孰與 $♢$ ？所以無最大（小）元者、不可比而已．

非空有窮全序集常有最大（小）元．請擬以歸納證明之

證.(非空有窮全序集

𝑆

有最大元)

$| 𝑆 | = 1$ 、 $𝑆$ 之元唯一、即最大最小元也．
$| 𝑆 | = 2$ 、設 $𝑆 = {𝑡_{1}, 𝑡_{2}}$ 、其最元得計算如下

$\max 𝑆 = {\begin{matrix} 𝑡_{1} if 𝑡_{2} ⪯ 𝑡_{1} \\ 𝑡_{2} if 𝑡_{1} ⪯ 𝑡_{2} \end{matrix}$
(26)
設 $| 𝑆 | = 𝑁$ 、 $𝑆$ 有最大元．察 $| 𝑆 | = 𝑁 + 1$ 、令 $𝑆^{'} = 𝑆 ∖ {𝑠}$ ．由前款知 $𝑆^{'}$ 有最大元 $𝑀^{'}$ ．然則 $\max 𝑆 = \max {𝑀^{'}, 𝑠}$ 、 $𝑆$ 之最大元也．

∎

集之界、不逾之境也．凡集 $𝑆 \subseteq 𝑇$ 之元 $𝑠$ 、其或 $𝑠 \leq 𝑀$ 者、則謂 $𝑀$ 爲 $𝑆$ 一上界．反之、若 $𝑀 \leq 𝑠$ 則曰下界．上下界並存、則謂之有界．界不必含於集也．上界之最小者、曰上確界、或曰最小上界、記 $\sup 𝑆$ ．下界之最大者、曰下確界、或曰最大下界、記 $\inf 𝑆$ ．

\sup 𝑆 = \min {𝑡 \in 𝑇 | 𝑠 \in 𝑆, 𝑠 \leq 𝑡}

(27)

\inf 𝑆 = \max {𝑡 \in 𝑇 | 𝑠 \in 𝑆, 𝑡 \leq 𝑠}

(28)

若夫上界與上確界、察其性質、凡有二項、一曰 $\sup 𝑆$ 乃 $𝑆$ 之上界也、二曰凡其上界莫小於 $\sup 𝑆$ 、最小之上界也．請問偏序集恆有上界乎？ 1．有窮集顯然恆有界、且 $\sup 𝑆 = \max 𝑆$ 而 $\inf 𝑆 = \min 𝑆$ 也．依序可列 $𝑆$ 之元,

全序關係

若改 $⪯$ 之自反性爲完全性、即悉適

完全性： $(\forall 𝑠, 𝑡 \in 𝑆) 𝑠 ⪯ 𝑡 \lor 𝑡 ⪯ 𝑠$
反對稱性： $(\forall 𝑠, 𝑡 \in 𝑆) 𝑠 ⪯ 𝑡 \land 𝑡 ⪯ 𝑠 \to 𝑠 = 𝑡$
傳遞性： $(\forall 𝑠, 𝑡, 𝑢 \in 𝑆) 𝑠 ⪯ 𝑡 \land 𝑡 ⪯ 𝑢 \to 𝑠 ⪯ 𝑢$

者、謂曰全序關係、或曰鏈．凡全序之關係、恆偏序也．請備述之．全序關係適反對稱性與傳遞性、並以完全性蘊含自反性即知其亦偏序也．

命題 6.

設 $(𝑋, ⪯)$ 為全序集．下列三命題䓁價也．

凡 $𝑋$ 之非空子集有上界者有上確界
凡 $𝑋$ 之非空子集有下界者有下確界
$𝐴$ , $𝐵$ 皆 $𝑋$ 之非空子集也．凡 $𝐴$ 中之 $𝑎$ 與 $𝐵$ 中之 $𝑏$ 使 $𝑎 ⪯ 𝑏$ 者． $𝑋$ 中必有一元 $𝑐$ 間於 $𝑎$ , $𝑏$ 、即 $\exists 𝑐 \in 𝑋, 𝑎 ⪯ 𝑐 ⪯ 𝑏$

證.

(1) ⇒ (2)：使 $𝐴$ 為 $𝑋$ 之非空子集也、且有下界．集 $𝐴$ 之下界以為 $𝐵 ≔ {𝑏 \in 𝑋 | 𝑏 ⪯ 𝑎, \forall 𝑎 \in 𝐴}$ 以 $𝐴$ 有下界知 $𝐵$ 之不空也．凡 $𝑎 \in 𝐴$ 皆為 $𝐵$ 上界也．故 $𝐵$ 有上確界也．假 $𝑚 ≔ \sup 𝐵$ , 而 $𝑚 ⪯ 𝑎$ 也（以上確界乃最小上界故耳）．故知、 $𝑚 \in 𝐵$ 而 $𝑚 = \max 𝐵$ ． $𝐴$ 下界之最大者也． $𝑚 = \inf 𝐴$ ．

(2) ⇒ (3): 設 $𝐴$ , $𝐵$ 皆 $𝑋$ 之非空子集也． $\forall 𝑎 \in 𝐴, \forall 𝑏 \in 𝐵, 𝑎 ⪯ 𝑏$ 也．故知 $𝐴$ 之元俱為 $𝐵$ 之下界也．由 (2) 知 $𝐵$ 有下確界、設以為 $𝑐 ≔ \inf 𝐵$ 、則 $𝑎 ⪯ 𝑐 ⪯ 𝑏$ 、即所求也．

(3) ⇒ (1)： ∎

映射

$𝑋$ , $𝑌$ 皆設以為集也．夫偏映射者、 $𝑋 \times 𝑌$ 上之二元關係 $𝑓$ 之

(𝑥, 𝑦) \in 𝑓 \land (𝑥, 𝑦^{'}) \in 𝑓 \to 𝑦 = 𝑦^{'}

(29)

者也．若夫定義域、像域、逆、複合之所謂、悉承自二元關係也．若定義域 $dom 𝑓 = 𝑋$ ²、則曰全映射、簡稱映射．記 $𝑓 : 𝑋 \to 𝑌$ 、 $𝑌$ 曰終域．若 $(𝑥, 𝑦) \in 𝑓$ 、記曰 $𝑓 (𝑥) = 𝑦$ 或 $𝑓 : 𝑥 \mapsto 𝑦$ ．若 $𝑌$ 為一數集、則 $𝑓$ 謂之函數．

限制與擴展

$𝑓 : 𝑋 \to 𝑌$ 為映射也、 $𝑆 \subseteq 𝑋$ 、集合

𝑓 [𝑆] ≔ {𝑓 (𝑠) | 𝑠 \in 𝑆}

(30)

名曰 $𝑓$ 於 $𝑆$ 之像集．

命題 7.

𝑓 [𝑆] \subseteq 𝑓 [𝑋] = im 𝑓

證.

一者較然可見．二者、即證

𝑓 [𝑋] \subseteq im 𝑓

及

𝑓 [𝑋] \supseteq im 𝑓

．其中

im 𝑓 = {𝑦 \in 𝑌 | (\exists 𝑥 \in 𝑋) 𝑓 (𝑥) = 𝑦}

承義自二元關係．
(

\subseteq

)

\forall 𝑦 \in 𝑓 [𝑋] = {𝑓 (𝑥) | 𝑥 \in 𝑋}

有

𝑥 \in 𝑋

遂使

𝑦 = 𝑓 (𝑥) \in 𝑌

．故

𝑦 \in im 𝑓

．
(

\supseteq

)

\forall 𝑦 \in im 𝑓

有

𝑥 \in 𝑋

遂使

𝑦 = 𝑓 (𝑥)

．是以

𝑦 \in 𝑓 [𝑋]

． ∎

定義函數 $𝑓$ 於 $𝑆$ 之限制 $𝑓 |_{𝑆} : 𝑆 \to 𝑌$ 、 $𝑓 |_{𝑆} (𝑠) ≔ 𝑓 (𝑠)$ ．於是 $im 𝑓 |_{𝑆} = 𝑓 [𝑆]$ ．

單滿性

$𝑓 : 𝑋 \to 𝑌$ 映射也．夫單射者、

𝑓 (𝑥) = 𝑓 (𝑥^{'}) \to 𝑥 = 𝑥^{'} .

(31)

為 $𝑓$ 之不同元有不同像也．夫滿射者、

\forall 𝑦 \in 𝑌, \exists 𝑥 \in 𝑋, 𝑓 (𝑥) = 𝑦 .

(32)

夫對射者、單射且滿射．

命題 8.

𝑓 : 𝑋 \to 𝑌 滿射 \leftrightarrow im 𝑓 = 𝑌

證.

( $\to$ ) 設 $𝑓$ 滿射也．欲證 $im 𝑓 = 𝑌$ 、即證 $im 𝑓 \subseteq 𝑌$ 且 $𝑌 \subseteq im 𝑓$ ．前者較然．及後者、蓋 $𝑓$ 滿射、故 $\forall 𝑦 \in 𝑌, \exists 𝑥 \in 𝑋, 𝑓 (𝑥) = 𝑏$ ．是以 $𝑦 \in im 𝑓 = {𝑓 (𝑥) | 𝑥 \in 𝑋}$ ．

( $\leftarrow$ ) 設 $im 𝑓 = 𝑌$ ．欲證 $𝑓$ 滿射也、即證 $\forall 𝑦 \in 𝑌, \exists 𝑥 \in 𝑋, 𝑓 (𝑥) = 𝑏$ ．蓋 $im 𝑓 = 𝑌$ 、則 $\forall 𝑦 \in 𝑌, 𝑦 \in im 𝑓$ ．是以 $\forall 𝑦 \in 𝑌, \exists 𝑥 \in 𝑋, 𝑓 (𝑥) = 𝑏$ ． ∎

是故、函數之單射否、滿射否、對射否、需論以定義域與終域．如函數 $𝑓 : 𝑥 \mapsto 𝑥^{2}$ 之於下列集合中．

$𝑥 \mapsto 𝑥^{2}$	單	滿
$ℝ \to ℝ$	$⊥$	$⊥$
$ℝ \to ℝ_{\geq 0}$	$⊥$	$⊤$
$ℝ_{\geq 0} \to ℝ$	$⊤$	$⊥$
$ℝ_{\geq 0} \to ℝ_{\geq 0}$	$⊤$	$⊤$

單射乎、滿射乎、各不同也．

逆映射

$𝑓 : 𝑋 \to 𝑌$ 對射也．設 $𝑦 = 𝑓 (𝑥) = 𝑓 (𝑥^{'})$ 即有 $(𝑥, 𝑦) \in 𝑓 \land (𝑥^{'}, 𝑦) \in 𝑓$ ．單射故 $𝑥 = 𝑥^{'}$ ．考慮其逆關係 $𝑓^{- 1} \subseteq 𝑌 \times 𝑋$ ：

(𝑦, 𝑥) \in 𝑓^{- 1} \land (𝑦, 𝑥^{'}) \in 𝑓^{- 1} \to 𝑥 = 𝑥^{'}

(33)

滿射故

\forall 𝑦 \in 𝑌, \exists 𝑥 \in 𝑋, (𝑦, 𝑥) \in 𝑓^{- 1}

(34)

即 $𝑌 = dom 𝑓^{- 1}$ ．是故 $𝑓^{- 1}$ 映射也．即對射之逆關係必爲映射．曰 $𝑓$ 之逆映射．

命題 9.

逆映射者對射也．

映射 $𝑔 : 𝑌 \to 𝑋$ 使 $𝑔 \circ 𝑓 = {id}_{𝑋}$ 者、曰 $𝑓$ 之左逆映射．
映射 $𝑔 : 𝑌 \to 𝑋$ 使 $𝑓 \circ 𝑔 = {id}_{𝑌}$ 者、曰 $𝑓$ 之右逆映射．

命題 10.

𝑓^{- 1}

左逆且右逆也．

證.

設 $𝑦 = 𝑓 (𝑥)$ 即 $(𝑥, 𝑦) \in 𝑓$ 、有 $(𝑦, 𝑥) \in 𝑓^{- 1}$ 、即 $𝑥 = 𝑓^{- 1} (𝑦)$ ．

先證 $𝑓^{- 1}$ 左逆．即 $𝑥 = 𝑓^{- 1} (𝑦) = 𝑓^{- 1} (𝑓 (𝑥))$ ．
次證 $𝑓^{- 1}$ 右逆．即 $𝑦 = 𝑓 (𝑥) = 𝑓 (𝑓^{- 1} (𝑦))$

∎

命題 11.

𝑓

有左逆映射則

𝑓

單射也．

證.

設

𝑔 : 𝑌 \to 𝑋

為

𝑓

之左逆映射也．欲證

𝑓

單射、即證

𝑓 (𝑥) = 𝑓 (𝑥^{'}) \to 𝑥 = 𝑥^{'}

．

𝑓 (𝑥) = 𝑓 (𝑥^{'})

然則

𝑔 (𝑓 (𝑥)) = 𝑔 (𝑓 (𝑥^{'}))

．以

𝑔

為

𝑓

之左逆映射知

𝑥 = 𝑥^{'}

． ∎

勢

孟子曰「權、然後知輕重；度、然後知長短．物皆然．」計集 $𝑆$ 其元众寡曰勢、記以 $| 𝑆 |$ ． $𝑆$ , $𝑇$ 集合也、若有對射 $𝑓 : 𝑆 \to 𝑇$ 、則曰二集䓁勢、記曰 $𝑆 ≅ 𝑇$ ．蓋以 $𝑆$ 度 $𝑇$ 而無虛盈、則勢相若也．

多使自然数為籌、比之多少, $\exists 𝑛 \in ℕ$ 可使 $𝑆$ 與 $ℕ_{< 𝑛} ≔ {0, 1, 2, \dots, 𝑛 - 1}$ 對射、然則謂 $𝑆$ 有窮集、勢 $𝑛$ 、記 $| 𝑆 | = 𝑛$ ．若有集 $𝑆 = {♧, ♢, ♡, ♤}$ 、計以一、二、三、四乃知其勢 $4$ ．有對射

\begin{matrix} 𝑓 : & 𝑆 \to ℕ_{< 4} \\ ♧ \mapsto 0, ♢ \mapsto 1, ♡ \mapsto 2, ♤ \mapsto 3 \end{matrix}

(35)

故也．

若夫莫能以自然数數者、謂之無窮集．如分數集、實數集䓁． $| ℕ |$ 定為 $א_{0}$ ．集合與自然數集勢䓁者、謂曰可數集、否則曰不可數集．如分數集爲可數集、實數集爲不可數集．有窮集之勢自然數、且 $| \emptyset | = 0$ ．無窮集者、雖不可勝數、猶可較也．集可使其元對射於自然數者、若盡數自然數之勢然．

例 3.

（自然數之䓁勢）

以下集合可數無窮:

【 $ℕ_{*}$ —— 正自然數】

易可驗證 $𝑓 : ℕ \to ℕ_{*}, 𝑛 \mapsto 𝑛 + 1$ 對射、故 $| ℕ_{*} | = א_{0}$ ．
【 $ℕ^{𝑛}$ —— 自然數組】

Cantor 折線法．列 $ℕ^{2}$ 所有為無窮矩陣、後沿折線以自然數編號、得對射 $ℕ \to ℕ^{2}$ 也．

于是凡自然數 $𝑛$ 、 $ℕ^{𝑛}$ 皆可數也．若 $(𝑎, 𝑏, 𝑐) \in ℕ^{3}$ 、對應 $(𝑎, (𝑏, 𝑐)) \in ℕ \times ℕ^{2}$ 也．以此類推．
【 $2 ℕ$ —— 偶數】

$𝑓 (𝑛) = 2 𝑛$ 者 $ℕ \to 2 ℕ$ 之對射也．奇數亦然．進一步 $ℕ / 𝑛 ℕ$ 之任意非空子集可數無窮也．
【 $ℤ$ —— 整數】

整數集也．設 $𝑓 : ℤ \to ℕ$

$𝑓 (𝑛) = {\begin{matrix} - 2 𝑛 - 1 & 若 𝑛 < 0 \\ 2 𝑛 & 若 𝑛 \geq 0 \end{matrix}$
(36)

是映正數悉於偶數而負數悉映於奇數也．
【 $ℚ$ —— 分數】

分數集也．依其所謂、 $ℚ = {𝑝 / 𝑞 | 𝑝, 𝑞 \in ℤ, 𝑞 \neq 0}$ 故而可列下表．

依上圖折線、可編號所有真分數．

命題 12.

（Schroder-Bernstein 定理）

$𝑆$ , $𝑇$ 皆集也．

| 𝑆 | \leq | 𝑇 | \land | 𝑇 | \leq | 𝑆 | \to | 𝑆 | = | 𝑇 |

(37)

證.

設 $𝑓 : 𝑆 \to 𝑇$ 與 $𝑔 : 𝑇 \to 𝑆$ 皆單射也．欲證 $| 𝑆 | = | 𝑇 |$ 、即證有對射 $ℎ : 𝑆 \to 𝑇$ 也．設

𝑆_{𝑛} ≔ {\begin{matrix} 𝑆 ∖ 𝑔 [𝑇] & 若 𝑛 = 0 \\ 𝑔 \circ 𝑓 [𝑆_{𝑛 - 1}] & 若 𝑛 > 0 \end{matrix}

(38)

$𝑆_{0}$ 之元莫有 $𝑔$ 之像也．而 $𝑆_{1}$ , $𝑆_{2}$ … 之屬、俱可緣溯至 $𝑆_{0}$ ．故集 $𝑆$ 之元之源自 $𝑆$ 者設以為 $𝒮_{𝑆} ≔ ⋃_{𝑛 \in ℕ} 𝑆_{𝑛}$ ．設 $𝒯_{𝑆} ≔ 𝑓 [𝒮_{𝑆}]$ 、 $𝑇$ 之元之源自 $𝑆$ 者也． $𝒮_{𝑆}$ , $𝒮_{𝑇}$ 不相交．蓋 $𝑠 \in 𝒮_{𝑆}$ 源自 $𝑆$ 而非 $𝑇$ 故也．

設

ℎ : 𝑆 \to 𝑇 = {\begin{matrix} 𝑓 & 若 𝑠 \in 𝒮_{𝑆} \\ 𝑔^{- 1} & 若 𝑠 \in 𝑆 ∖ 𝒮_{𝑆} \end{matrix}

(39)

則 $ℎ$ 對射也．何故？

$𝑓$ 單射而 $𝑓 |_{𝒮_{𝑆}}$ 自然也．反之、 $𝑓 |_{𝒮_{𝑆}} : 𝒮_{𝑆} \to 𝒯_{𝑆}$ 滿射也．以 $𝒯_{𝑆} = 𝑓 [𝒮_{𝑆}] = im 𝑓 |_{𝒮_{𝑆}}$ 較然可知．於是 $𝑓 |_{𝒮_{𝑆}}$ 對射也．
同理以知 $𝑔 |_{𝑇 ∖ 𝒯_{𝑇}}$ 單射．而

$𝑔 [𝑇 ∖ 𝒯_{𝑆}] = 𝑆 ∖ 𝒮_{𝑆}$
(40)

然則可以知 $𝑔 |_{𝑇 ∖ 𝒯_{𝑇}} : 𝑇 ∖ 𝒯_{𝑇} \to 𝑆 ∖ 𝒮_{𝑆}$ 滿射也．所以然者、蓋
- 凡 $𝑠 \in 𝑆 ∖ 𝒮_{𝑆}$ 者、 $𝑠 \notin 𝑆_{0}$ ．是以 $𝑠 \in 𝑔 [𝑇] \to (\exists 𝑡 \in 𝑇) 𝑔 (𝑡) = 𝑠$ ．是唯需證 $𝑡 \notin 𝒯_{𝑆}$ ．若 $𝑡 \in 𝒯_{𝑆}$ 、則 $(\exists 𝑠^{'} \in 𝒮_{𝑆}) 𝑓 (𝑠^{'}) = 𝑡$ ．則 $𝑠 = 𝑔 (𝑡) = 𝑔 (𝑓 (𝑠^{'}))$ 即 $(\exists 𝑛 \in ℕ_{+}) 𝑠 \in 𝑆_{𝑛} \subseteq 𝒮_{𝑆}$ ．謬也．故 $𝑡 \notin 𝒯_{𝑆} \to 𝑡 \in 𝑇 ∖ 𝒯_{𝑆} \to 𝑠 = 𝑔 (𝑡) \in 𝑔 [𝑇 ∖ 𝒯_{𝑆}]$ ．
- 反之、凡 $𝑠 \in 𝑔 [𝑇 ∖ 𝒯_{𝑆}]$ 、則 $\exists 𝑡 \in 𝑇 ∖ 𝒯_{𝑆}, 𝑔 (𝑡) = 𝑠$ ．是唯需證 $𝑠 \notin 𝒮_{𝑆}$ ．若 $𝑠 \in 𝒮_{𝑆}$ 、則 $(\exists 𝑛 \in ℕ_{+}) 𝑠 \in 𝑆_{𝑛}$ ．繼而 $(\exists 𝑠^{'} \in 𝒮_{𝑆}) 𝑔 (𝑓 (𝑠^{'})) = 𝑠$ 、因 $𝑔$ 單射、 $𝑡 = 𝑓 (𝑠^{'}) \in 𝒯_{𝑆}$ ．謬也．故 $𝑠 \in 𝑆 ∖ 𝒮_{𝑆}$ ．

是以 $ℎ$ 對射也．所證如是． ∎

命題 13.

（Cantor's 定理）

$𝑆$ 集也．

| 𝑆 | < | 𝒫 (𝑆) |

(41)

證.

$𝑓 : 𝑆 \to 𝒫 (𝑆)$ 以為映射．欲證 $𝑓$ 非對射也、蓋則 $| 𝑆 | \leq | 𝒫 (𝑆) |$ ．設

𝑇 ≔ {𝑠 \in 𝑆 | 𝑠 \notin 𝑓 (𝑠)}

(42)

則 $𝑇 \subseteq 𝑆$ 故 $𝑇 \in 𝒫 (𝑆)$ ．欲證 $𝑇$ 非 $𝑓$ 之像也、蓋則 $𝑓$ 非對射也．假 $\exists 𝑡 \in 𝑆, 𝑓 (𝑡) = 𝑇$ ．則

若 $𝑡 \in 𝑇$ 、則 $𝑡 \notin 𝑓 (𝑡) = 𝑇$ ．謬也．
若 $𝑡 \notin 𝑇$ 、則 $𝑡 \in 𝑓 (𝑡) = 𝑇$ ．謬也．

所證如是． ∎

可數集 $𝑆$ 之冪集 $𝒫 (𝑆)$ 尤勢 $2^{| 𝑆 |}$ 也、請以歸納法證明之: $| 𝒫 (\emptyset) | = | {\emptyset} | = 1$ ,若設以 $| 𝒫 (𝑆) | = 2^{| 𝑆 |}$ , 既添新元 $𝑥$ 於 $𝑆$ 、其冪集必含原 $𝒫 (𝑆)$ 所有． $𝒫 (𝑆 \cup {𝑥})$ 之所添乃 $𝑥$ 與原 $𝒫 (𝑆)$ 所有之併也．

𝒫 (𝑆 \cup {𝑥}) = 𝒫 (𝑆) ⊔ {𝑌 \cup {𝑥} | 𝑌 \in 𝒫 (𝑆)}

(43)

是以

\begin{matrix} 2^{| 𝑆 \cup {𝑥} |} & = | 𝒫 (𝑆 \cup {𝑥}) | \\ = | 𝒫 (𝑆) | + | {𝑌 \cup {𝑥} | 𝑌 \in 𝒫 (𝑆)} | \\ = 2^{| 𝑆 |} + 2^{| 𝑆 |} = 2^{| 𝑆 | + 1} \end{matrix}

(44)

所證如是．

數列

命題 14.

有序列

{𝑎_{𝑛}}

單調遞減而

{𝑏_{𝑛}}

單調遞增者、且

𝑎_{𝑛} \geq 𝑏_{𝑛}

．

\forall 𝑖, 𝑗 \in ℕ, 𝑎_{𝑖} \geq 𝑏_{𝑗}

意即、

𝑎_{𝑛}

皆

𝑏_{𝑛}

之上界也、

𝑏_{𝑛}

皆

𝑎_{𝑛}

之下界也．

證.

設 $𝑖, 𝑗 \in ℕ$ 、不失一般性、分三種情況討論：

$𝑖 = 𝑗$ ：由題設知 $𝑎_{𝑖} \geq 𝑏_{𝑖}$ 、故 $𝑎_{𝑖} \geq 𝑏_{𝑗}$ ．
$𝑖 < 𝑗$ ：因 ${𝑎_{𝑛}}$ 單調遞減、故 $𝑎_{𝑖} \geq 𝑎_{𝑗}$ ．因 ${𝑏_{𝑛}}$ 單調遞增、故 $𝑏_{𝑗} \geq 𝑏_{𝑖}$ ．由題設 $𝑎_{𝑗} \geq 𝑏_{𝑗}$ 、結合上述不䓁式： $𝑎_{𝑖} \geq 𝑎_{𝑗} \geq 𝑏_{𝑗}$
$𝑖 > 𝑗$ ：因 ${𝑎_{𝑛}}$ 單調遞減、故 $𝑎_{𝑗} \geq 𝑎_{𝑖}$ ．因 ${𝑏_{𝑛}}$ 單調遞增、故 $𝑏_{𝑖} \geq 𝑏_{𝑗}$ ．由題設 $𝑎_{𝑖} \geq 𝑏_{𝑖}$ 、結合上述不䓁式： $𝑎_{𝑖} \geq 𝑏_{𝑖} \geq 𝑏_{𝑗}$

綜上所述、 $\forall 𝑖, 𝑗 \in ℕ$ 、恆有 $𝑎_{𝑖} \geq 𝑏_{𝑗}$ ．

因此、任意 $𝑎_{𝑖}$ 皆為序列 ${𝑏_{𝑛}}$ 之上界、任意 $𝑏_{𝑗}$ 皆為序列 ${𝑎_{𝑛}}$ 之下界． ∎