語言背後的代數學（七）：數學結構

回顧

上文我們介紹了Henkin模型，以及它的環境模型條件和組合模型條件，

它們分別為合法的 項和 項，找到了對應的語義解釋。

然而這只是簡單類型化 演算 的其中一種解釋。

另一種常用的解釋方式，建立在範疇論基礎之上，稱為笛卡爾閉範疇。

為了理解這個概念，我們需要補充一些簡單的範疇論方面的內容。

1. 數學結構

範疇論的研究數學結構的形式化方法，

它不考慮具體的數學對象，而是考慮數學對象以及它們之間的聯繫。

學習範疇論最好的辦法，我認為不宜馬上從抽象的概念開始，

而是先回到具體的例子上面，找到相似性，理解概念被發明的動機。

因此，我們要先理解什麼是數學結構。

後文中，我們會首先介紹最常被提及的群結構，然後再介紹拓撲空間和CPO（完全偏序）。

有了這些例子之後，對抽象概念的理解是事半功倍的。

2. 群結構

群是一種滿足結合律的乘法結構，

但是它的運算對象，卻並不局限於整數，有理數甚至實數上。

因此，群論對概念採用了不同的定義方式，和初等代數有明顯的不同。

在初等代數中，我們研究的是具體的運算系統，

例如，我們會先介紹什麼是自然數，然後再介紹自然數上的四則運算。

群論則不然。

它會先抽象的定義滿足哪些條件的運算系統是群，

然後再去尋找（或證明）具體的運算系統滿足這些條件。

為此，我們先從條件最弱的半群開始，

逐漸增加約束條件，最終認識群結構是怎麼建立起來的。

半群

集合 和 上滿足結合律的二元運算 ，所形成的代數結構，叫做半群，記為 ，

半群運算 ，也常簡記為 。

好在我們第二篇中，對「什麼是代數」進行了嚴謹的定義，

因此，對這裡提到的「代數結構」應該並不陌生，很顯然半群是一個代數。

滿足半群條件的例子是非常多的，

例如，自然數集以及自然數上的乘法運算，構成了一個半群。

值得注意的是，集合和運算要放在一起考慮才行，

集合包含了運算對象，運算表明了運算對象之間的關係。

幺半群

設 是半群，元素 ，稱為半群 的幺元，如果 ， 。

可以證明，如果半群存在幺元，則必定是唯一的。

幺元常被記為 ，或者直接寫成 。

具有幺元的半群，稱為幺半群，記為 。

幺半群的例子，我們可以考慮字元串及其連接運算，在連接運算下，空串是幺元。

群

設 是幺半群，如果它的每個元素都可逆，我們就稱它為群。

所謂可逆指的是， ， ，使得 ，

其中 為 的幺元。

自然數集以及自然數上的乘法運算組成的代數結構，是半群，

如果把自然數 看做幺元，則構成了一個幺半群，但是它不是群。

因為，除了 之外，任何自然數都沒有逆元。

字元串及其連接運算，構成了一個幺半群，但也不是群，

因為，沒有任何兩個非空字元串連接在一起會得到空串。

下面我們來看一個群的例子。

如果我們把整數集（包含正負整數）看做運算對象的集合，

把整數集上的加法運算看做群定義中的二元運算，

整數 看做加法運算的幺元，則這樣的運算系統構成了一個群。

因為，每一個整數的相反數，都是它的逆元。

群同態

有了群之後，很自然的一步我們會考慮兩個群是否足夠相似，

這就需要我們找到兩個群之間的對應關係。

設 和 是兩個群，我們把映射 稱為群同態，如果 ，

都有 。

如果 是單射，則稱 為單同態，如果 是滿射，則稱 為滿同態。

如果 是雙射，則稱 為群同構，同構的兩個群，記為 。

小結

現在我們理解了半群，幺半群，群，群同態，這些概念放在一起，就是所謂的群結構。

結構一般所指的是一些運算規則，或者約束條件。

為了更好的理解數學結構，

下面我們來介紹另一個概念，它來自拓撲學，稱為拓撲空間。

3. 拓撲結構

拓撲學，被人們戲稱橡皮膜上的幾何學，它主要研究在連續變換下保持不變的幾何性質，

例如，連通性和緊緻性。

這裡我們先不展開，主要看一下在拓撲學中是怎麼建立數學結構的。

子集族

設 是一個非空集合， 是 的冪集（所有子集構成的集合），

把 的子集（即以 的一部分子集為成員的集合）稱為 的子集族。

拓撲空間

設 是一個非空集合， 的一個子集族 稱為 的一個拓撲，如果它滿足

（1） 和 都包含在 中

（2） 中任意多個成員的並集仍在 中

（3） 中有限多個成員的交集仍在 中

集合 和它的一個拓撲 一起稱為一個拓撲空間，記作 。

稱 中的成員為這個拓撲空間的開集。

從定義看出，給出集合的一個拓撲就是規定它的哪些子集是開集。

連續映射

設 和 都是拓撲空間， 是一個映射，

，如果對於包含 的每一個開集 ，必存在包含 的開集 ，

使得， ，則我們就說， 在 處連續。

如果映射 在任一點 都連續，則說 是連續映射。

同胚映射

如果 是雙射，並且 及其逆 都是連續的，

則稱 是一個同胚映射，簡稱同胚。

當存在 到 的同胚映射時，就稱 與 同胚，記作 。

值得注意的是，同胚映射中條件 連續不可忽視，

它不能從雙射和 的連續性推出來。

小結

以上我們介紹了拓撲空間，以及兩個拓撲空間之間的連續映射，

這和群以及兩個群之間的群同態是很相似的。

它們表現出了一種結構上的相似性，

範疇論正是看到這種相似性，於是跳出具體的運算系統，

例如，它可以考慮群結構與拓撲結構之間的關係。

接下來我們來介紹CPO（完全偏序）。

它在範疇論中，對於擺脫集合論的觀念束縛，幫助是很大的。

4. 完全偏序

在《遞歸函數》系列文章中，我們已經介紹過CPO（完全偏序）的概念了。

為了方便與本文中其他概念進行對比，我們再簡單的梳理一下。

二元關係

集合 和 上的二元關係 ，指的是它們笛卡爾積 的子集， 。

自反性，對稱性，反對稱性，傳遞性

一個二元關係 是自反的，如果 對於所有的 成立；

是對稱的，如果 就有 ，對於所有的 都成立；

是反對稱的，如果 且 ，則 是同一個元素，對於所有 都成立；

是傳遞的，如果 和 能推出 ，對於所有的 都成立。

偏序關係

等價關係是同時具有自反性，對稱性和傳遞性的關係。

偏序關係是具有自反性，反對稱性和傳遞性的關係。

等價關係的一個例子就是相等性，相等性關係 當且僅當 是同一個元素。

偏序關係，例如通常的序關係 ， 當且僅當 。

最小元與上確界

對於偏序集 ，以及它的一個子集 ，

如果存在 ，且對於任意的 ，有 ，則稱 為 的最小元。

對於偏序集 ，以及它的一個子集 ，

如果存在 ，（注意， 不一定在子集 中）

使得對於任意的 ， ，則稱 為 的上界，

如果 的所有上界存在最小元，則稱它為 最小上界，或上確界。

完全偏序集

偏序集 的非空子集 叫做有向子集，

當且僅當，對於 中的任意元素 ，存在 中的一個元素 ，有 且 。

如果一個偏序集 的每個有向子集 都有上確界（記為 ）

就稱它是一個有向完全偏序集，

此外，如果它還有最小元，就稱它是一個完全偏序集。

注意，完全偏序集並不是每一個子集都有上確界，而是它的每一個有向子集都有上確界。

連續函數

假設 與 是完全偏序集， 是集合上定義的一個函數，

對於任意的 ，如果 就有 ，我們就說 是單調的。

如果 是單調的，且對於任意有向子集 ，

有 ，就稱 是連續的。

小結

我們又重新回顧了完全偏序這一概念，

實際上，任意一個CPO（完全偏序），都構成了一個範疇，

而所有的群，也構成了一個範疇。

群範疇的對象是集合，而CPO（完全偏序）範疇的對象不一定是集合。

這對擺脫集合論來理解範疇是很關鍵的。

總結

本文介紹了三種數學結構，群結構，拓撲結構，以及CPO（完全偏序）。

作為例子，可以為後面學習範疇論打下紮實的基礎。

我們看到了這些數學結構之間的相似性，

從下一篇開始，我們要開始範疇論的學習之旅了。

---

參考

Category theory

離散數學教程

近世代數引論

基礎拓撲學講義

---

下一篇：語言背後的代數學（八）：範疇

推薦閱讀：