論集合【稿】 - Uwni'Space

閱讀本文需備初等數學基礎．

ZFC 公理

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

命題 1.

（内涵公理）

設 $𝜑$ 爲一元謂辭

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

(1)

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

𝐴 = {𝑥 | 𝜑 (𝑥)}

(2)

查察下例

例 1.

（Russell 悖論）

設

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

(3)

則 $𝑋 \notin 𝑋$ 、無己之集也．依內涵公理可聚此屬以爲一集

𝐴 = {𝑥 | 𝑥 \notin 𝑥}

(4)

則此集有己乎？ $𝐴 \in 𝐴 \leftrightarrow 𝐴 \notin 𝐴$ 、謬．故知

∄ 𝐴 \forall 𝑥 (𝑥 \in 𝐴 \leftrightarrow 𝑥 \notin 𝑥) .

(5)

乖乎內涵公理也．

是以内涵公理宜畧爲限．

命題 2.

（分離公理模式）

設 $𝜑$ 爲一元謂辭

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

(6)

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

命題 3.

（外延公理）

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

(7)

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

集合代數

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

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

(8)

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

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

(9)

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

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

(10)

子集與空集

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

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

(11)

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

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

證 .

使

𝐴

爲集．欲證

\emptyset \subseteq 𝐴

、證

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

而已．蓋

\emptyset

無元、故前項爲假而命題空真矣．

∎

集族

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

$ℱ$ 集族也．

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

(12)

名曰 $ℱ$ 之泛並． $ℱ$ 非空¹則謂

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

(13)

曰 $ℱ$ 之泛交．且較然易見

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

(14)

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

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

⨆ ℱ = 𝑋

(15)

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

元組與直積

夫有序對者、又名二元組、記 $(𝑎, 𝑏)$ ．所謂 (Kuratowski 1921) 如下

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

(16)

遂

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

$𝜋_{1} (𝑎, 𝑏) ≔ 𝑎$ 謂之第一影映、 $𝜋_{2} (𝑎, 𝑏) ≔ 𝑏$ 謂之第二影映．

命題 4.

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

證 .

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

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

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

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

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

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

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

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

(19)

例 2.

（六十甲子）

記稱大桡作甲子、隸首作數．二者既立、以比日表、以管万事．天地二甲子、十干十二支．數從甲子始、子母相求．十日十二辰、周六十日．設

(20)

請問

者六十甲子乎？非也．如「甲丑」弗在其中．干支相繼而得六十甲子故也．

$𝐴 \times 𝐴$ 得記爲 $𝐴^{2}$ ．至於三元組、可謂之以 $(𝑎_{1}, 𝑎_{2}, 𝑎_{3}) ≔ ((𝑎_{1}, 𝑎_{2}), 𝑎_{3})$ 、四元組 $(𝑎_{1}, 𝑎_{2}, 𝑎_{3}, 𝑎_{4}) ≔ ((𝑎_{1}, 𝑎_{2}, 𝑎_{3}), 𝑎_{4})$ 謂之如前、准此及 $𝑛$ 元組、得遞歸謂之

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

(20)

而有 $𝑛$ 維直積謂之如下

𝐴_{1} \times \dots \times 𝐴_{𝑛} ≔ {(𝑎_{1}, \dots, 𝑎_{𝑛}) | \underset{1 \leq 𝑖 \leq 𝑛}{⋀} 𝑎_{𝑖} \in 𝐴_{𝑖}}

(21)

𝐴^{𝑛} ≔ 𝐴^{𝑛 - 1} \times 𝐴

(22)

關係

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

謂 $𝑅$ 之定義域者

dom 𝑅 ≔ {𝑎 | \exists 𝑏 𝑅 (𝑎, 𝑏)}

(23)

謂 $𝑅$ 之像域者

i 𝑅 ≔ {𝑏 | \exists 𝑎 𝑅 (𝑎, 𝑏)}

(24)

謂 $𝑅$ 之逆關係者

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

(25)

則可得而見 $dom 𝑅^{- 1} = i 𝑅$ 及 $i 𝑅^{- 1} = dom 𝑅$ ．

謂二元關係 $𝑆$ 與 $𝑅$ 之複合者

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

(26)

例 3.

大學校內、設

𝐴

爲生集、

𝐵

爲課程、

𝐶

爲師集．則

𝑆 \subseteq 𝐴 \times 𝐵

爲學生受業關係、

𝑅 \subseteq 𝐵 \times 𝐶

爲教師受業關係．然則

𝑆 \circ 𝑅

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

命題 5.

（複合關係之結合律）

使 $𝑅 \subseteq 𝐴 \times 𝐵$ 、 $𝑆 \subseteq 𝐵 \times 𝐶$ 、 $𝑇 \subseteq 𝐶 \times 𝐷$ ．則

𝑇 \circ (𝑆 \circ 𝑅) = (𝑇 \circ 𝑆) \circ 𝑅

(27)

證 .

以示 $𝑇 \circ (𝑆 \circ 𝑅) \subseteq (𝑇 \circ 𝑆) \circ 𝑅$ 、凡 $(𝑎, 𝑑) \in 𝑇 \circ (𝑆 \circ 𝑅)$ 者、 $\exists 𝑐 \in 𝐶$

(𝑎, 𝑐) \in 𝑆 \circ 𝑅 \land (𝑐, 𝑑) \in 𝑇

(28)

$(𝑎, 𝑐) \in 𝑆 \circ 𝑅$ 是以 $\exists 𝑏 \in 𝐵$

(𝑎, 𝑏) \in 𝑅 \land (𝑏, 𝑐) \in 𝑆

(29)

以 $(𝑏, 𝑐) \in 𝑆 \land (𝑐, 𝑑) \in 𝑇$ 、知 $(𝑏, 𝑑) \in 𝑇 \circ 𝑆$ ．又以 $(𝑎, 𝑏) \in 𝑅$ 知 $(𝑎, 𝑑) \in (𝑇 \circ 𝑆) \circ 𝑅$ ．

反則可證 $𝑇 \circ (𝑆 \circ 𝑅) \supseteq (𝑇 \circ 𝑆) \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 𝑆}$ ．

命題 6.

\sim

爲相若關係之於

𝑆

．則商集

\frac{𝑆}{\sim}

爲

𝑆

之劃分．

證 .

設 $𝒮 ≔ \frac{𝑆}{\sim}$ ．將欲證 $𝒮$ 爲 $𝑆$ 之劃分、證以

曰 $\forall 𝑋 \in 𝒮, 𝑋 \neq \emptyset$ ：設 $𝑋 \in 𝒮$ 、則有 $𝑠 \in 𝑆$ 使 $𝑋 = {[𝑠]}_{\sim}$ ．以 $𝑠 \sim 𝑠$ 、知 $𝑠 \in {[𝑠]}_{\sim}$ 、故 $𝑋 \neq \emptyset$ ．
曰 $⋃ 𝒮 = 𝑆$ ：設 $𝑠 \in 𝑆$ ．以 $𝑠 \sim 𝑠$ 、知 $𝑠 \in {[𝑠]}_{\sim}$ ．以 ${[𝑠]}_{\sim} \in 𝒮$ 、知 $𝑠 \in ⋃ 𝒮$ ．反之、設 $𝑠 \in ⋃ 𝒮$ 、則有 $𝑋 \in 𝒮$ 使 $𝑠 \in 𝑋$ ．以 $𝑋$ 爲某相若類．故 $𝑠 \in 𝑆$ ．
曰 $\forall 𝑋, 𝑌 \in 𝒮, 𝑋 \neq 𝑌 \to 𝑋 \cap 𝑌 = \emptyset$ ：證其逆否．假令 $𝑋 \cap 𝑌 \neq \emptyset$ 、則有 $𝑢 \in 𝑆$ 使 $𝑢 \in 𝑋$ 且 $𝑢 \in 𝑌$ ．且 $\forall 𝑥 \in 𝑋 \forall 𝑦 \in 𝑌$ 、 $𝑥 \sim 𝑢 \sim 𝑦$ 、故而 $𝑥 \in 𝑌$ 且 $𝑦 \in 𝑋$ ．是以 $𝑋 = 𝑌$ ．

$∎$

命題 7.

設 $𝒮$ 爲 $𝑆$ 之劃分．有二元關係

\sim_{𝒮} = {(𝑥, 𝑦) \in 𝑆^{2} | \exists 𝐴 \in 𝒮, 𝑥 \in 𝐴 \land 𝑦 \in 𝐴}

(30)

則

$\sim_{𝒮}$ 爲相若關係．且 $\frac{𝑆}{\sim_{𝒮}} = 𝒮$
若 $\sim$ 爲相若關係且 $\frac{𝑆}{\sim} = 𝒮$ 、則 $\sim = \sim_{𝒮}$ ．

證 .

∎

是以二元關係與劃分一一對應也

恆等關係

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

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

(31)

若 $𝑆 = {♣︎, ♦︎, ♥︎}$ 、 ${id}_{𝑆} = {(♣︎, ♣︎), (♦︎, ♦︎), (♥︎, ♥︎)}$

恆等關係者、相若關係之最小者也．

命題 8.

使

𝑅 \subseteq 𝐴 \times 𝐵

爲二元關係．則

𝑅 \circ 𝑅^{- 1} = {id}_{𝐵}

證 .

$∎$

序關係

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

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

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

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

若夫偏序之匪等者、謂之固偏序．記 $≺$ ． $𝑎 ≺ 𝑏 ≔ 𝑎 ⪯ 𝑏 \land 𝑎 \neq 𝑏$ ．

若改偏序 $⪯$ 之自反性爲完全性 $(\forall 𝑠, 𝑡 \in 𝑆) 𝑠 ⪯ 𝑡 \lor 𝑡 ⪯ 𝑠$ 、則謂曰全序關係、又鎖．凡全序之關係、恆偏序也．請備述之．全序關係適反對稱性與傳遞性、並以完全性蘊含自反性即知其亦偏序也．

$(𝑇, ⪯)$ 偏序之構也． $𝑠 \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}$
(32)
設 $| 𝑆 | = 𝑁$ 、 $𝑆$ 有最大元．察 $| 𝑆 | = 𝑁 + 1$ 、令 $𝑆^{'} = 𝑆 ∖ {𝑠}$ ．由前款知 $𝑆^{'}$ 有最大元 $𝑀^{'}$ ．然則 $\max 𝑆 = \max {𝑀^{'}, 𝑠}$ 、 $𝑆$ 之最大元也．

$∎$

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

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

(33)

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

(34)

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

命題 9.

設 $(𝑋, ⪯)$ 爲全序集．下列三命題相若也．

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

證 .

將以 (1) $\Rightarrow$ (2) $\Rightarrow$ (3) $\Rightarrow$ (1) 次第證之．

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

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

(3 $\Rightarrow$ 1)： $∎$

映

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

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

(35)

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

例 4.

（映射例）

${(𝑥, 𝑦) \in 𝗥_{> 0}^{2} | 𝑦^{2} = 𝑥}$ ． $𝑦 = \sqrt{𝑥}$ 之上半支也．
$𝑋$ 上之恆等關係 ${id}_{𝑋}$ 、由其所謂、 ${id}_{𝑋} = {(𝑥, 𝑥) | 𝑥 \in 𝑋}$ 、於是 $(𝑥, 𝑦) \in {id}_{𝑋} \to 𝑥 = 𝑦$ 且 $(𝑥, 𝑦^{'}) \in {id}_{𝑋} \to 𝑥 = 𝑦^{'}$ 而 $𝑦 = 𝑥 = 𝑦^{'}$ 矣．乃知其偏映．又 $dom {id}_{𝑋} = 𝑋$ 、故知 ${id}_{𝑋}$ 爲映．遂稱 ${id}_{𝑋} : 𝑋 ∋ 𝑥 \mapsto 𝑥 \in 𝑋$ 恆等映射．

悉集 $𝑋$ 到 $𝑌$ 之函數于 $𝑌^{𝑋} ≔ {𝑓 | 𝑓 : 𝑋 \to 𝑌}$ ．

限制

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

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

(36)

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

命題 10.

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

證 .

一者較然可見．二者欲所證、

𝑓 [𝑋] \subseteq i 𝑓

及

𝑓 [𝑋] \supseteq i 𝑓

而已．其

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

承義自二元關係．
(

\subseteq

)

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

有

𝑥 \in 𝑋

遂使

𝑦 = 𝑓 (𝑥) \in 𝑌

．故

𝑦 \in i 𝑓

．
(

\supseteq

)

\forall 𝑦 \in i 𝑓

有

𝑥 \in 𝑋

遂使

𝑦 = 𝑓 (𝑥)

．是以

𝑦 \in 𝑓 [𝑋]

．

∎

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

單滿性

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

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

(37)

蓋 $𝑓$ 之元不同而像相違也．記 $𝑓 : 𝑋 ↣ 𝑌$ ．

夫滿映者、

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

(38)

蓋 $𝑌$ 之元悉 $𝑓$ 之像也．記 $𝑓 : 𝑋 ↠ 𝑌$ ．

夫對映者、單映且滿映．記 $𝑓 : 𝑋 ⤖ 𝑌$

命題 11.

(𝑓 : 𝑋 ↠ 𝑌) \leftrightarrow (i 𝑓 = 𝑌)

證 .

( $\to$ ) 使 $𝑓$ 滿映．欲證明 $i 𝑓 = 𝑌$ 、則以 $i 𝑓 \subseteq 𝑌 \land 𝑌 \subseteq i 𝑓$ 其證也．前者較然．及後者、以 $𝑓$ 滿映、 $\forall 𝑦 \in 𝑌, \exists 𝑥 \in 𝑋, 𝑓 (𝑥) = 𝑏$ ．是以 $𝑦 \in i 𝑓 = {𝑓 (𝑥) | 𝑥 \in 𝑋}$ ．

( $\leftarrow$ ) 使 $i 𝑓 = 𝑌$ 、欲證 $𝑓$ 滿映、則須證 $\forall 𝑦 \in 𝑌, \exists 𝑥 \in 𝑋, 𝑓 (𝑥) = 𝑏$ 而已．蓋 $i 𝑓 = 𝑌$ 、則 $\forall 𝑦 \in 𝑌, 𝑦 \in i 𝑓$ ．是以 $\forall 𝑦 \in 𝑌, \exists 𝑥 \in 𝑋, 𝑓 (𝑥) = 𝑏$ ． $∎$

是故、函數之單映否、滿映否、對映否、須復論及定義域與終域．如函數 $𝑓 : 𝑥 \mapsto 𝑥^{2}$ 之於下列各集合中單映滿映固不同也．

$𝑥 \mapsto 𝑥^{2}$	單	滿
$𝗥 \to 𝗥$
$𝗥 \to 𝗥_{\geq 0}$		○
$𝗥_{\geq 0} \to 𝗥_{\geq 0}$	○	○

例 5.

（單映與滿映）

恆等函數 ${id}_{𝑋}$ 對映也．

以 $\forall 𝑥, 𝑥^{'} \in 𝑋, 𝑥 = {id}_{𝑋} (𝑥) = {id}_{𝑋} (𝑥^{'}) = 𝑥^{'}$ 且 $i {id}_{𝑋} = 𝑋$ 故也．

複合與逆

映射者素二元關係也．映射之複合不亦映射乎？

命題 12.

（複合映射）

𝑓 \in 𝑌^{𝑋}, 𝑔 \in 𝑍^{𝑌}

則其複合關係

𝑔 \circ 𝑓 \in 𝑍^{𝑋}

．

證 .

使 $(𝑥, 𝑧) \in 𝑔 \circ 𝑓$ 、由複合關係之所謂、知 $\exists 𝑦 \in 𝑌$ 使 $(𝑥, 𝑦) \in 𝑓 \land (𝑦, 𝑧) \in 𝑔$ ．復使 $(𝑥, 𝑧^{'}) \in 𝑔 \circ 𝑓$ 、知 $\exists 𝑦^{'} \in 𝑌$ 使 $(𝑥, 𝑦^{'}) \in 𝑓 \land (𝑦^{'}, 𝑧^{'}) \in 𝑔$ ．以 $𝑓$ 映射而知 $𝑦 = 𝑦^{'}$ ．以 $𝑔$ 映射而知 $𝑧 = 𝑧^{'}$ ．

(𝑥, 𝑧) \in 𝑔 \circ 𝑓 \land (𝑥, 𝑧^{'}) \in 𝑔 \circ 𝑓 \to 𝑧 = 𝑧^{'}

(39)

乃知 $𝑔 \circ 𝑓$ 偏映．然後證及 $dom (𝑔 \circ 𝑓) = 𝑋$ ．

$𝑓 \in 𝑌^{𝑋}$ 故 $dom 𝑓 = 𝑋$ ． $\forall 𝑥 \in 𝑋, \exists 𝑦 \in 𝑌, (𝑥, 𝑦) \in 𝑓$ ．又以 $𝑔 \in 𝑍^{𝑌}$ 故 $dom 𝑔 = 𝑌$ ． $\exists 𝑧 \in 𝑍, (𝑦, 𝑧) \in 𝑔$ ．於是 $(𝑥, 𝑧) \in 𝑔 \circ 𝑓$ ．

\forall 𝑥 \in 𝑋, \exists 𝑧 \in 𝑍, (𝑥, 𝑧) \in 𝑔 \circ 𝑓

(40)

乃知 $dom (𝑔 \circ 𝑓) = 𝑋$ ． $∎$

蓋此其映射之複合關係所以映射矣．可以複合關係之結合律知複合映射之結合．

命題 13.

單（滿）映之複合亦單（滿）映也．

證 .

設 $𝑓 : 𝑋 \to 𝑌$ 、 $𝑔 : 𝑌 \to 𝑍$ ．

單映：設 $𝑥, 𝑥^{'} \in 𝑋$ 、若 $𝑔 (𝑓 (𝑥)) = 𝑔 (𝑓 (𝑥^{'}))$ 、則以 $𝑔$ 單映知 $𝑓 (𝑥) = 𝑓 (𝑥^{'})$ ．以 $𝑓$ 單映知 $𝑥 = 𝑥^{'}$ ．
滿映：設 $𝑧 \in 𝑍$ ．以 $𝑔$ 滿映知 $\exists 𝑦 \in 𝑌, 𝑔 (𝑦) = 𝑧$ ．以 $𝑓$ 滿映知 $\exists 𝑥 \in 𝑋, 𝑓 (𝑥) = 𝑦$ ．是以 $𝑔 (𝑓 (𝑥)) = 𝑧$ ．

$∎$

復知對映之複合亦對映也．

映射之複合映射也．至於映射之逆關係則不然．若映射 $𝑓 : 𝑋 \to 𝑌$ 其逆關係 $𝑓^{- 1}$ 成映則曰 $𝑓$ 可逆．然則 $𝑓^{- 1}$ 其名曰 $𝑓$ 之逆映．

命題 14.

𝑓^{- 1} \circ 𝑓^{- 1} = 𝑓

命題 15.

映

𝑓 : 𝑋 \to 𝑌

可逆

\leftrightarrow

𝑓

爲對映．

證 .

( $\leftarrow$ ) 使 $𝑓$ 單映、即 $𝑦 = 𝑓 (𝑥) = 𝑓 (𝑥^{'})$ 則 $𝑥 = 𝑥^{'}$ ．思惟其逆關係 $𝑓^{- 1} \subseteq 𝑌 \times 𝑋$ 、則

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

(41)

乃知 $𝑓^{- 1}$ 偏映．使 $𝑓$ 滿映則由命題 11 知 $𝑌 = i 𝑓 = dom 𝑓^{- 1}$ ． $𝑓$ 對映則 $𝑓^{- 1}$ 映也．

( $\to$ ) 使 $𝑓$ 可逆．然則 $𝑓^{- 1}$ 成映、 $\forall 𝑥, 𝑥^{'} \in 𝑋, \forall 𝑦 \in 𝑌$ 、 $(𝑦, 𝑥) \in 𝑓^{- 1} \land (𝑦, 𝑥^{'}) \in 𝑓^{- 1} \to 𝑥 = 𝑥^{'}$ 以逆關係之所謂、

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

(42)

乃知 $𝑓$ 單映也． $𝑌 = dom 𝑓^{- 1} = i 𝑓$ ．故知 $𝑓$ 滿映． $∎$

命題 16.

映

𝑔 : 𝑌 \to 𝑋

使

𝑔 \circ 𝑓 = {id}_{𝑋}

者、謂之

𝑓

之左逆映．使

𝑓 \circ 𝑔 = {id}_{𝑌}

者、謂之

𝑓

之右逆映．然則

𝑓

可逆

\leftrightarrow

𝑓^{- 1}

左逆且右逆．

證 .

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

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

$∎$

命題 17.

𝑓

有左逆映則

𝑓

單映也．

證 .

設

𝑔 : 𝑌 \to 𝑋

爲

𝑓

之左逆映也．欲證

𝑓

單映、證以

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

．

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

然則

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

．以

𝑔

爲

𝑓

之左逆映知

𝑥 = 𝑥^{'}

．

∎

指標與泛直積

設 $𝒜$ 爲非空集族． $𝑓 : 𝐼 ↠ 𝒜$ 滿映也．然則謂 $𝑓$ 爲 $𝒜$ 之指標映而 $𝐼$ 爲指標集． $(𝒜, 𝑓)$ 謂之指標族．蓋以指標集之元標記集族之元素．凡指標 $𝑖 \in 𝐼$ , 記其所指 $𝑓 (𝑖) \in 𝒜$ 爲 $𝐴_{𝑖}$ ．則以 $𝑓$ 滿映、 $𝒜 = {𝐴_{𝑖} | 𝑖 \in 𝐼}$ ．並可記 $𝒜 = {𝐴_{𝑖}}_{𝑖 \in 𝐼}$ ．指標類上之泛並與泛交謂之以

⋃_{𝑖 \in 𝐼} 𝐴_{𝑖} ≔ {𝑥 | \exists 𝑖 \in 𝐼, 𝑥 \in 𝐴_{𝑖}}

(43)

⋂_{𝑖 \in 𝐼} 𝐴_{𝑖} ≔ {𝑥 | \forall 𝑖 \in 𝐼, 𝑥 \in 𝐴_{𝑖}}

(44)

又若 $𝐼 = {1, \dots, 𝑛}$ 則可記泛並爲 $⋃_{𝑖 = 1}^{𝑛}$ 、或 $⋂_{1 \leq 𝑖 \leq 𝑛}$ ．泛交亦相類也．

命題 18.

$⋃_{𝑖 \in 𝐼} 𝐴_{𝑖} = ⋃ 𝒜$
(45)
$⋂_{𝑖 \in 𝐼} 𝐴_{𝑖} = ⋂ 𝒜$
(46)

證 .

$\forall 𝑥 \in ⋃ 𝒜, \exists 𝐴 \in 𝒜$ 遂使 $𝑥 \in 𝐴$ ．以 $𝑓$ 滿映、 $\exists 𝑖 \in 𝐼, 𝐴 = 𝑓 (𝑖) = 𝐴_{𝑖}$ 、使 $𝑥 \in 𝐴_{𝑖}$ 、遂 $𝑥 \in ⋃_{𝑖 \in 𝐼} 𝐴_{𝑖}$ ．反之、 $\forall 𝑥 \in ⋃_{𝑖 \in 𝐼} 𝐴_{𝑖}$ 、則 $\exists 𝑖 \in 𝐼, 𝑥 \in 𝐴_{𝑖} \in 𝒜$ ．於是 $𝑥 \in ⋃ 𝒜$ ．
盖相似．

$∎$

$𝑋$ 集合也、查映 $𝑓 : 𝗡_{\leq 𝑚}^{*} \to 𝐴$ ．例 $𝑋 = {♣︎, ♦︎, ♥︎, ♠︎}$ 、 $𝑚 = 2$ 、則 $𝑓 (1) = ♥︎, 𝑓 (2) = ♦︎$ 、 $𝑓$ 擇取 $𝑋$ 之二元也．夫 $𝑓$ 自變量不必爲自然數．設指標類 $𝒜 = {𝐴_{𝑖}}_{𝑖 \in 𝐼}$ 、於是所謂泛直積者

\prod_{𝑖 \in 𝐼} 𝐴_{𝑖} ≔ {𝑓 映也 | \forall 𝑖 \in 𝐼, 𝑓 (𝑖) \in 𝐴_{𝑖}}

(47)

凡指標 $𝑖 \in 𝐼$ 者、 $𝑓$ 之函數 $𝜋_{𝑖} (𝑓) ≔ 𝑓 (𝑖)$ 、 $𝜋_{𝑖} : \prod_{𝑖 \in 𝐼} 𝐴_{𝑖} \to 𝐴_{𝑖}$ 謂之第 $𝑖$ 影映．

例 6.

Date Picker 者、圖形控件所以擇年月日也．設指標集 $𝐼 = {年, 月, 日}$ 、指標族 $𝒜 = {𝐴_{𝑖}}_{𝑖 \in 𝐼}$ 、其中 $𝐴_{年} = {1970, \dots, 2026}$ 、 $𝐴_{月} = {一月, 二月, \dots, 十二月}$ 、 $𝐴_{日} = {1, 2, \dots, 31}$ ．

圖表 1 日期擇者

是以泛直積 $\prod_{𝑖 \in 𝐼} 𝐴_{𝑖}$ 之元 $𝑓$ 即爲所擇日期． $𝜋_{年} (𝑓)$ 所擇之年、 $𝜋_{月} (𝑓)$ 所擇之月、 $𝜋_{日} (𝑓)$ 所擇之日也．

注意 $\prod_{𝑖 = 1}^{𝑛} 𝐴_{𝑖}$ 相違於 $𝐴_{1} \times \dots \times 𝐴_{𝑛}$ ．前者指標集上映之集合、後者 $𝑛$ 元組之集合也．若比 $𝑛 = 2$ 、則泛直積 $\prod_{𝑖 = 1}^{2} 𝐴_{𝑖}$ 之元素 $𝑓 = {(1, 𝑎_{1}), (2, 𝑎_{2})}$ 相違於 $(𝑎_{1}, 𝑎_{2}) \in 𝐴_{1} \times 𝐴_{2}$ ．然其對偶而構同、相若關係不易故也．由是元組可示以離散映射．若夫元組之元皆數者、謂之數組．

勢

孟子曰「權、然後知輕重；度、然後知長短．物皆然．」計集 $𝑆$ 其元众寡曰勢、記以 $| 𝑆 |$ ． $𝑆$ , $𝑇$ 集合也、欲比其勢、以映量之．有 $𝑆 \to 𝑇$ 之單映、則 $𝑆$ 寡於 $𝑇$ ．曰 $𝑆$ 勢弱於 $𝑇$ 、或曰 $𝑇$ 勢強於 $𝑆$ 、記 $| 𝑆 | \leq | 𝑇 |$ ．若有對映 $𝑆 \to 𝑇$ 、則曰二集等勢、記曰 $| 𝑆 | = | 𝑇 |$ ．蓋以 $𝑆$ 度 $𝑇$ 而無盈虛、則勢相若． $| 𝑆 | \leq | 𝑇 | \land | 𝑆 | \neq | 𝑇 |$ 、則記曰 $| 𝑆 | < | 𝑇 |$ ．

多使自然数爲籌、比之多少、 $\exists 𝑛 \in 𝗡$ 可使 $𝑆$ 對映于 $𝗡_{< 𝑛} ≔ {0, 1, 2, \dots, 𝑛 - 1}$ 、然則謂 $𝑆$ 有窮、勢 $𝑛$ 、記 $| 𝑆 | = 𝑛$ ．若有集 $𝑆 = {♣︎, ♦︎, ♥︎, ♠︎}$ 、計以一、二、三、四乃知其勢 $4$ ．有對映

\begin{matrix} 𝑓 : & 𝑆 \to 𝗡_{< 4} \\ ♣︎ \mapsto 0, ♦︎ \mapsto 1, ♥︎ \mapsto 2, ♠︎ \mapsto 3 \end{matrix}

(48)

故也．是以有窮集者、必得以自然數指標其元．

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

例 7.

（自然數之等勢）

以下集合可數無窮:

【 $𝗡^{*}$ —— 正自然數】

易可驗證 $𝑓 : 𝗡 \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}$
(49)

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

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

由徑、凡真分數悉見舉也．

命題 19.

$א_{0}^{𝑛} = א_{0}$
(50)
$א_{0} \cdot 2^{א_{0}} = 2^{א_{0}}$
(51)
${(2^{א_{0}})}^{א_{0}} = 2^{א_{0}}$
(52)

命題 20.

（Schroder-Bernstein 定理）

$𝑆$ 、 $𝑇$ 集也．

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

(53)

證 .

設 $𝑓 : 𝑆 \to 𝑇$ 與 $𝑔 : 𝑇 \to 𝑆$ 皆單映也．欲證 $| 𝑆 | = | 𝑇 |$ 、以對映 $ℎ : 𝑆 \to 𝑇$ 之有、此則其證也．設

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

(54)

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

設

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

(55)

則 $ℎ$ 對映也．何故？

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

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

然則可以命題 11知 ${ 𝑔 |}_{𝑇 ∖ 𝒯_{𝑇}} : 𝑇 ∖ 𝒯_{𝑇} \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 𝑆 ∖ 𝒮_{𝑆}$ ．

是以 $ℎ$ 對映也． $∎$

命題 21.

（鴿籠原理）

設

𝑆

、

𝑇

集也．

| 𝑆 | > | 𝑇 |

、則無單映

𝑆 ↣ 𝑇

．

證 .

歸謬法．使

𝑆 ↣ 𝑇

．則

| 𝑆 | \leq | 𝑇 |

．謬也．

∎

命題 22.

（Cantor’s 定理）

$𝑆$ 集也．

| 𝑆 | < | 𝒫 (𝑆) |

(57)

證 .

$𝑆 ∋ 𝑥 \mapsto {𝑥} \in 𝒫 (𝑆)$ 單射．故知 $| 𝑆 | \leq | 𝒫 (𝑆) |$ ． $| 𝑆 | \neq | 𝒫 (𝑆) |$ 然則證遂．否則 $𝑓 : 𝑆 ↣ 𝒫 (𝑆)$ 或滿也．

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

(58)

欲證 $𝑇$ 不在 $i 𝑓$ 之中、而 $𝑓$ 非對映也．不然、使 $\exists 𝑡 \in 𝑆, 𝑓 (𝑡) = 𝑇$ ．則

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

$∎$

可數集 $𝑆$ 之冪集 $𝒫 (𝑆)$ 尤勢 $2^{| 𝑆 |}$ 也、請以歸納法示之: $| 𝒫 (\emptyset) | = | {\emptyset} | = 1$ ．使 $| 𝒫 (𝑆) | = 2^{| 𝑆 |}$ ．若添新元 $𝑥$ 於 $𝑆$ 以爲 $𝑆^{'} = 𝑆 \cup {𝑥}$ ．其冪集 $𝒫 (𝑆^{'})$ 猶守 $𝒫 (𝑆)$ 之固有． $𝒫 (𝑆^{'})$ 之新增者 ${𝑥}$ 併於 $𝒫 (𝑆)$ 之固有也．

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

(59)

是以

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

(60)

是其證也．

引據

KURATOWSKI, Casimir, 1921. Sur la notion de l'ordre dans la théorie des ensembles. Fundamenta mathematicae. Online. 1921. Vol. 2, no. 1, p. 161～171. DOI 10.4064/fm-2-1-161-171.
ZERMELO, E., 1908. Untersuchungen über die Grundlagen der Mengenlehre. I. Mathematische Annalen. Online. 1 六月 1908. Vol. 65, no. 2, p. 261～281. DOI 10.1007/BF01449999.