基礎集合論

我們不得不承認幾個事實。

  1. 人的數量是有限的。
  2. 人的壽命是有限的。
  3. 人一生能寫下的符號是有限的。

但是公元前的人類就已知曉,數有無限多歐幾里得早在約公元前 300 年就已證明質數有無限多個。舉凡牲畜的計數、土地丈量,以至現代複雜到沒人搞得懂的華爾街經濟,人類以有限的精力、時間以及手指操縱(或被操縱於)於無窮的數。世界上唯獨人類能藉由有限的符號去理解無窮,實屬神奇。例如給定球的初速、質量、彈力係數等條件,算出球彈跳的距離。在古典力學中,球彈跳了無限多次!

集合論可以視為一種絕對神學。
Rudy Rucker

集合論是重大的進步,因為幾乎所有的數學實體都可以用集合表達,並有著直覺、迷人的公理化系統。如果懷疑某個數學論述正不正確,我們可以把它轉化為集合論;而如果在集合論中得以證明,則我們可以認定該數學論述是正確的。此外,因為集合論中的變數是集合,所以可以用一階邏輯表達。

雖然樸素集合論可以用非正式的、直覺的方式學習,甚至在小學中就可以用文氏圖說明。但是它會造成羅素悖論布拉利-福爾蒂悖論。所以現代數學作品都直接或間接奠基於公理集合論,其中以 ZFC 集合論較為著名。本站的數學就以 ZFC 集合論為基礎。

ZFC 集合論

ZF 集合論有七條公理,合選擇公理共八條。這裡作為微積分的輔助課程,暫時不強調邏輯符號,先以自然語言敘述公理本身或它的重要推論。以下的鏈結指向 Metamath 中形式化的定義及證明。

外延公理
若二個集合有相同的元素,則它們相等。
替代公理
這是個很強的公理。它可以推論出一個集合在函數下的像仍是集合。它也可以推論出幾條比較弱的定理。
冪集公理
一個集合的冪集仍是集合。至此我們才能推出配對公理,因為我們這時才能確定集合可以有兩個成員
聯集公理
一個集合的聯集仍是集合
正規公理
A 不是空集且不含 x,則存在一個集合 x 使得 (xA) = ∅。這是條不太直觀的公理。實際上,它否定的意味比肯定還要濃厚。從它可以推論出集合必不是自己的成員
無窮公理
無窮序數 ω 是個集合。
選擇公理
一個集合有選擇函數。
從無限多雙襪子中每雙挑一隻襪子需要選擇公理,但[挑]鞋子就免了。

[在英文中 ABA 都稱作 union。台灣多譯作聯集,大陸多譯作并集,其中的簡化。]

在這個公理系統中,分類公理、空集空理與配對公理實際上是定理,而不是公理。因為它們是在其他公理成立的基礎下證明出來的。此處稱它們為公理是因為過往它們曾作為公理,名稱就約定俗成流傳下來了。

集合可以等於其他集合,可以包含其他集合,也可以是其他集合的成員。例如實數的集合的成員當然就是所有的實數。一個特定的實數像是 2 也是個集合,但不是我們很熟悉的樣子——這需要非常複雜的集合建構,像是內含一部機械讓它能依據實數的法則運轉。開平方根是一個包含無限個序對的集合;每一對的第一個成員是一個非負實數,而第二個成員是它的平方根。

為了敘述及證明的方便,我們會把一些符合特定條件的集合打包 (class)。

類的抽象化 (class abstraction)

假設 φ 是個句子,則我們把所有滿足 φ 所構成的類記做

{xφ}

習慣上我們以大寫拉丁字母表達類的變數。Metamath 把它塗成紫色,暗示了它兼具集合和句子的性質。

所有集合都可以想成是一個類。假設我們接受直接把集合變數 x 也當成類的變數,則我們可以證明

x = {yyx}

其中 xy 相異。

我們沒說類一定可以是其他類的成員。事實上,有些類不可以是其他類的成員。這是為了避免一些已知的悖論。

ZFC 的公理並不提及,所以也未對進行公理化,但是我們使用它就像使用句子一樣正當。我們說明類和句子可以互化。我們有

(A = {xφ} ↔ ∀x(xAφ))

因此對於類的變數 A,當我們找到句子 φ 使得 A = {xφ} 時,

  1. xAφ 可以互換,
  2. A{xφ} 也可以互換。

因為類和句子可以互化,所以類的替代就像句子的替代一樣簡單——直接代換,不像集合的代換受到一階邏輯的捆綁。仍然要注意數學的宇宙是集合的宇宙。在 ZFC 集合論中,集合受一階邏輯的宰制。

宇類 (universal class)

所有集合都是宇類的成員。

V = {xx = x}

我們用 V 而不是 U 是因為 U 長得太像聯集的符號。

爾後我們可以用 A ∈ V 來表達 A 是集合。要驗證這個寫法,首先我們可以證明集合是集合,即 x ∈ V;再進行類與句子的互化證成A 是集合則有個集合是 A,即 (A ∈ V ↔ ∃x x = A),其中 A 不含 x

在集合成員少的時候,我們習慣用枚舉的方式來表達集合。所以首先我們來定義單元集

單元集

{A} = {xx = A}

我們可以驗證 {xx = A} = {yy = A} ,其中 A 不含 xy

單元集是集合

只需要外延、冪集、分類三個公理就能證明單元集是個集合

{A} ∈ V

接下來要定義無序對就容易多了。

無序對

{A, B} = ({A} ∪ {B})

配對公理

{x, y} ∈ V

在一些書籍中,配對公理被視為另一個公理。在此我們可以用外延、替代、冪集三個公理來證明它,使它成為多餘的公理。

無序對是集合

{A, B} ∈ V

如果 A, B 皆為集合,則此無序對由配對公理保證是集合;否則此無序對退化為單元集,仍是集合。

序對的定義對於非本科生就不那麼直觀了。現在最流行的定義是 Kuratowski 的作法。

序對

A, B⟩ =

我們可以驗證 (⟨A, B⟩ = ⟨C, D⟩ ↔ (A = CB = D)),其中 A, B, D 是集合。注意我們採用 Kuratowski 序對,C 不必是集合。

序對是集合

A, B⟩ ∈ V

因為我們用無序對來定義序對,此定理是顯然的。

關係

關係的中綴表達式

這是當代數學界用來表達關係的方式。關係是由序對組成的集合。

(ARB ↔ ⟨A, B⟩ ∈ R)

集合論是怎麼看待 3 < 5 這個稀鬆平常的恆真句呢?其實 3, 5, < 都是集合,其中 ⟨3, 5⟩ ∈ <。

序對類的抽象化

這是語法糖,讓我們可以直觀地定義想要的關係。

{⟨x, y⟩ ∣ φ} = {z ∣ ∃xy(z = ⟨x, y⟩ ∧ φ)}

其中 xz 相異,yz 相異,φ 不含 z

恆等關係

I = {⟨x, y⟩ ∣ x = y}

其中 xy 相異。

加上 xy 相異這項限制是為了讓定義更弱,而使得定理更強。我們可以證明無此限制的版本

笛卡兒積

笛卡兒積是遍取兩類中所有成員一一配出的序對所構成的類。

(A × B) = {⟨x, y⟩ ∣ (xAyB)}

其中 xz 相異,也不出現於 AB

關係

關係就是序對組成的集合。

(Rel AA ⊆ (V × V))

反關係

A = {⟨x, y⟩ ∣ yAx}

其中 xy 相異,也不出現於 A

複合

(AB) = {⟨x, y⟩ ∣ ∃z(xBzzAy)}

其中 x, y, z 兩兩相異,皆不出現於 AB

定義域

定義域是關係中所有序對成員的第一員構成的類。

dom A = {x ∣ ∃y xAy}

其中 xy 相異,也不出現於 A

值域

值域是反關係的定義域。

ran A = dom A

限制

限制是定義域縮小後的新關係。

(AB) = (A ∩ (B × V))

雖然數學上,限制通常只用在函數上,但其實也可以用於關係。例如 (< ↾ ℝ+) 就是侷限於正實數的小於關係。

是限制的值域。

(AB) = ran (AB)

雖然數學上,像通常只用在函數上,但其實也可以用於關係。例如 (< ↾ 2) 就是所有大於 2 的數所構成的類。

此外,我們不需要定義新符號來表達前像。我們可以寫 (AB),畢竟前像就是反關係的像。

函數

函數

函數滿足以下幾點:

  • 函數是關係
  • 函數複合其反關係,為恆等關係的子集。

(Fun A ↔ (Rel A ∧ (AA) ⊆ I))

如果我們說 AB 上的函數,其實就是指 A 的定義域是 B

(A Fn B ↔ (Fun A ∧ dom A = B))

如果我們說 FAB 的映射,其實就是指 FA 上的函數,陪域 (codomain) 是 B。注意值域是陪域的子集。陪域不一定要等於值域。

(F:A–→B ↔ (F Fn A ∧ ran FB))

什麼叫做函數複合其反關係,為恆等關係的子集呢?其實就是禁止一對多的關聯啦!

函數值

Metamath 定義函數值 時還沒引入確定描述詞,所以直接使用聯集

(FA) = ∪{x ∣ (F “ {A}) = {x}}

這樣子的設計使得當像 (F “ {A}) 不是單元集時,函數值 (FA) 被定義為空集。

在一般文獻中,函數值常寫作 F(A),甚至在特殊狀況下寫作 F A。Metamath 力求無歧義的語言,故採用皮亞諾的左單引號註記。

算子

我們往往把算子視為語言中基本的部份,甚至在許多程式語言中也是如此,但其實它可以定義成序對的函數值。注意與關係的不同,算子的語法加上了括弧;關係回傳的是完構式,而算子回傳的是類。

(AFB) = (F ‘⟨A, B⟩)

巢狀序對類的抽象化

這是語法糖,讓我們可以直觀地定義想要的算子。

{⟨⟨x, y⟩, z⟩ ∣ φ} = {w ∣ ∃xyz(w = ⟨x, y⟩ ∧ φ)}

其中 wx, y, z 分別相異,φ 不含 z

映射

這是語法糖,讓我們可以直觀地定義想要的函數。

(xAB) = {⟨x, y⟩ ∣ (xAy = B)}

其中 xy 相異,AB 都不含 y

二元映射

這是語法糖,讓我們可以直觀地定義想要的算子。

(xA, yBC) = {⟨⟨x, y⟩, z⟩ ∣ ((xAyB) ∧ z = C)}

其中 zx, y 分別相異,A, B, C 都不含 z

函數是連結輸入值的集合與可能輸出的集合的關係,其中每個輸入都對應著恰好一個輸出。例如把複數 x 連結到 x2 的關係,即 (x ∈ ℂ ↦ (x↑2)),就是一個函數。函數 F 對輸入 A 的輸出記做 (FA)。以 F = (x ∈ ℂ ↦ (x↑2)) 為例,(F ‘-3) = 9,即 -3F9,即 ⟨-3, 9⟩ ∈ F。輸入的變數有時也稱作函數的參數。

算子映射

f R = (f ∈ V, g ∈ V ↦ (x ∈ (dom f ∩ dom g) ↦ ((fx)R(gx))))

其中 f, g, x 兩兩相異且不出現於 R

在文獻中可能會寫 (x ∈ ℂ ↦ (x↑2)) + (x ∈ ℂ ↦ (3 · x)) = (x ∈ ℂ ↦ ((x↑2) + (3 · x))),但聰明的你應該發現這個加號跟複數的加號不是同一個類。在 Metamath 嚴謹的語言中,應該是

(x ∈ ℂ ↦ (x↑2)) ∘f + (x ∈ ℂ ↦ (3 · x)) = (x ∈ ℂ ↦ ((x↑2) + (3 · x)))

關係映射

r R = {⟨f, g⟩ ∣ ∀x ∈ (dom f ∩ dom g)(fx)R(gx)}

其中 f, g, x 兩兩相異且不出現於 R

序數

我們採用馮·諾伊曼的定義,也就是當代數學界最流行的方式。此外,我們偏好嚴格排序,以類比 ∈ 之於序數。

傳遞類

傳遞類的聯集是自己的子集。

(Tr A ↔ ∪AA)

傳遞類得名於其成員間的成員謂詞有傳遞性,也就是當 xyyA 時,xA

Epsilon 關係

Epsilon 關係 在語法上可以當成 ∈ 使用,但只適用於集合間。畢竟關係是個類,而 ∈ 是謂詞。

E = {⟨x, y⟩ ∣ xy}

其中 xy 相異。

偏序關係

偏序關係具有反自反性與傳遞性。

(R Po A ↔ ∀xAyAzAxRx ∧ ((xRyyRz) → xRz)))

其中 x, y, z 兩兩相異,皆不出現於 RA

全序關係

全序關係是具有三一性的偏序關係。

(R Or A ↔ (R Po A ∧ ∀xAyA (xRyx = yyRx)))

其中 xy 相異,也不出現於 RA

良基關係

A 上的良基關係A 的非空子集中有最小元。

(R Fr A ↔ ∀x((xAx ≠ ∅) → ∃yxzx ¬ zRy))

其中 x, y, z 兩兩相異,皆不出現於 RA

良序關係

良序關係是良基關係,也是全序關係。

(R We A ↔ (R Fr AR Or A))

序數

序數是傳遞類,且被 epsilon 關係良序。

(Ord A ↔ (Tr A ∧ E We A))

序數的類

序數的類由所有序數集合構成。

On = {x ∣ Ord x}

本節僅作為現代數學結構的驚鴻一瞥。爾後我們將以當代文獻中較鬆散的文法為主,較容易書寫,也不必採用形式邏輯來證明,以加速教材開發與減少篇幅。

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *