給定一組物件，可以基於多種標準來排序它們（取決於物件本身）——大小、重量、年齡、字母順序等。
然而，我們目前不關心可以用來排序物件的標準，而是關心定義序的關係的本質。這其中也有幾種類型。
在數學上，序作為一種結構（類似於么半群）由兩個部分組成。
序是一組元素，以及這些元素之間的一個二元關係，表示為 $≤$（「大於或等於」），它遵循特定的定律。
我們像往常一樣表示集合的元素，如下所示。
二元關係是兩個元素之間的關係，通常用箭頭表示。
至於定律，則取決於序的類型。
讓我們從一個例子開始——你認為最直接的序類型是線性序，也就是其中每個物件都相對於其他所有物件都有其位置。在這種情況下，排序標準是完全確定的，在哪個元素排在哪個元素之前方面沒有歧義。例如，顏色的排序，按其光波長度排序（或按它們在彩虹中出現的順序）。
使用集合論，我們可以將這種序以及任何其他序表示為序的基礎集合與其自身的笛卡爾積的子集（即序的元素對的集合）。
在程式設計中，序是通過提供一個函數來定義的，該函數給定兩個物件，告訴我們哪個物件「較大」（排在前面），哪個物件「較小」。不難看出，這個函數定義了一個集合對（我們給定一個對，必須說它是否屬於該集合）。
然而（這裡開始變得有趣了），並非所有這樣的函數（以及所有這樣的對集合）都定義了序。為了讓這樣的函數真正定義一個序，也就是說，每次都有相同的輸出，獨立於物件最初是如何被洗牌的，它必須遵循幾個規則。
順帶一提（或者說，完全不是順帶一提），這些規則幾乎等同於定義序關係標準的數學定律，也就是說，這些是定義哪個元素可以指向哪個元素的規則。
A 線性序是一組元素，以及這些元素之間的一個二元關係，它遵循自反性、遞移性、反對稱性、全稱性定律。
讓我們把枯燥的定律講完——每個物件都必須大於或等於自身，或對所有 $a$ 都有 $a ≤ a$（序中元素之間的關係通常在公式中表示為 $≤$，但也可以用從第一個物件到第二個物件的箭頭表示）。
這個定律只是為了涵蓋「基本情況」：我們也可以用相反的方式來表述它，說每個物件不應該與自身有關係，在這種情況下，我們將得到一個類似於「大於」的關係，而不是「大於或等於」，以及一種稍微不同的序，有時稱為嚴格序。
第二個定律也許是最不明顯的（但可能是最重要的）——它說明如果物件 $a$ 大於物件 $b$，那麼它自動大於所有小於 $b$ 的物件，或者 $a ≤ b \land b ≤ c o a ≤ c$。
這個定律在很大程度上定義了序是什麼：如果我在踢足球方面比我奶奶厲害，那麼我也會比我奶奶的朋友厲害，而她卻輸給了我奶奶，否則我真的不會比她厲害。
第三個定律稱為反對稱性。它說明定義序的函數不應該給出矛盾的結果（或者換句話說，只有當 $x = y$ 時，你才有 $x ≤ y$ 和 $y ≤ x$）。
這也意味著不允許平局——要麼我在踢足球方面比我奶奶厲害，要麼她比我厲害。
最後一個定律稱為全稱性（或連通性），它規定屬於序的所有元素都必須是可比較的（$a ≤ b \lor b ≤ a$）。也就是說，對於任何兩個元素，總有一個會「大於」另一個。
順帶一提，全稱性定律使得自反性定律變得多餘，因為自反性只是全稱性的一個特例，當 $a$ 和 $b$ 是同一個物件時，但我仍然想呈現它，因為原因很快就會顯現出來。
實際上，這就是原因：全稱性定律可以被移除。不遵循全稱性定律的序稱為部分序（而線性序也稱為全稱序）。
任務 1：之前，我們討論了一個非常相似的關係。你還記得嗎？有什麼區別？
任務 2：想想你認識的一些序，並弄清楚它們是部分序還是全稱序。
部分序實際上比線性/全稱序更有趣。但在我們深入研究它們之前，先談談數字。
自然數在「大於或等於」這個運算下形成一個線性序（我們一直在公式中使用這個符號）。
在許多方面，自然數是典型的序——任何有限物件的序都同構於數字序的子集，因為我們可以將任何序的第一個元素映射到數字 $1$，第二個元素映射到數字 $2$ 等（我們也可以進行相反的操作）。
如果我們仔細想想，這種同構實際上比定律定義的同構更接近日常的線性序概念——當大多數人想到序時，他們想到的不是遞移、反對稱和全稱關係，而是基於這些標準可以決定哪個物件排第一、哪個排第二等。因此，注意到這兩種概念是等價的很重要。
從任何有限物件的序都同構於自然數這一事實，也得出同等大小的所有線性序都是相互同構的。
所以，線性序很簡單，但它也是（我認為這種同構證明了這一點）最無聊的序，特別是從範疇論的觀點來看——所有有限線性序（以及大多數無限線性序）都只是同構於自然數，因此它們的所有圖都看起來一樣。
然而，部分序的情況就不是這樣了，我們接下來將要探討的部分序。
全稱性定律看起來不像其他定律那樣「板上釘釘」，也就是說，我們可能可以想到一些它不適用的情況。例如，如果我們旨在根據足球技能對所有人類進行排序，我們可以通過許多方式對一個人與其朋友、朋友的朋友等進行排名，但無法對從未互相比賽過的人群進行排序。
從線性序的定律中移除全稱性定律，我們就得到了一個部分序（也稱為部分序集，或 poset）。
部分序是一組元素，以及這些元素之間的一個二元關係，它遵循自反性、遞移性、反對稱性定律。
每個線性序也是一個部分序（就像群仍然是么半群一樣），反之則不然。
我們甚至可以創建一個序的序，基於哪個序更普遍。
部分序也與我們在第一章中討論的等價關係概念有關，只是對稱性定律被反對稱性取代了。
如果我們回顧一下足球運動員排名列表的例子，我們可以發現，只包含我自己、我奶奶和她朋友的第一個版本是一個線性序。
然而，包含這個我們誰都還沒和他比賽過的其他人，使得層次結構變成了非線性的，也就是一個部分序。
這是部分序和全稱序之間的主要區別——部分序無法給出「誰比誰厲害」的確定答案。但有時這正是我們需要的——在體育和其他領域，總沒有恰當的方式來線性評估元素。
之前，我們說過所有線性序都可以用相同的鏈狀圖表示，我們可以反轉這個說法，說所有看起來與所述圖不同的圖都代表部分序。
一個例子是包含一堆線性序子集的部分序，例如在我們的足球例子中，我們可以有獨立的朋友群體，他們互相比賽並進行排名，但與其他群體中的任何人無關。
構成部分序的不同線性序稱為鏈。這個圖中有兩條鏈 $m o g o f$ 和 $d o o$。
鏈不必完全彼此斷開才能成為部分序。它們可以連接，只要連接不是一對一的，也就是說，當一條鏈的最後一個元素連接到另一條鏈的第一個元素時（這會有效地將它們合併成一條鏈）。
上述集合不是線性排序的——儘管我們知道 $d ≤ g$ 和 $f ≤ g$，但 $d$ 和 $f$ 之間的關係未知——任何元素都可以比另一個大。
雖然部分序不能給出「誰比誰厲害」的確定答案，但其中一些仍然可以給出更重要問題的答案（在體育和其他領域），即「誰是第一名？」也就是冠軍，比其他所有人都厲害的選手。或者更廣泛地說，大於所有其他元素的元素。
序的最大元素是元素 $a$，使得對於任何其他元素 $x$，都有 $x ≤ a$。一些（不是所有）部分序確實有這樣的元素——在我們最後的圖中，$m$ 是最大元素，在這個圖中，綠色元素是最大的。
有時會有不止一個元素大於所有其他元素，在這種情況下，沒有一個是最大的。
除了最大元素之外，部分序還可以有一個最小（最小）元素，其定義方式相同。
兩個在序中相互連接的元素的最小上界稱為它們的連接（join），例如，綠色元素是其他兩個的連接。
$a$ 和 $b$ 的連接是最小的元素 $c$，它大於它們，形式上為：
$G$ 是 $A$ 和 $B$ 的連接，滿足：
給定兩個元素，其中一個大於另一個（例如 $a ≤ b$），連接就是這個較大的元素（在本例中為 $b$）。
例如，在線性序中，任何兩個元素的連接就是較大的元素。
與最大元素一樣，如果兩個元素有幾個同樣大的上界，那麼它們都不是連接（連接必須是唯一的）。
然而，如果其中一個元素被確定為小於其餘所有元素，它就立即符合資格。
任務 3：範疇論中的哪個概念讓你聯想到連接（join）？
給定兩個元素，比這兩個元素都小的最大元素稱為它們的交集（meet）。
與連接相同的規則適用，但反之亦然。
本節中我們使用的圖稱為「Hasse 圖」，它們的工作方式與我們平時的圖類似，但有一個額外的規則——「較大」的元素總是位於較小的元素之上。
在箭頭方面，規則意味著如果你向一個點添加箭頭，箭頭指向的點必須始終位於箭頭指向的點之上。
Hasse 圖允許我們通過查看哪個點位於另一個點之上來比較任何兩個點，例如，我們可以通過識別它們連接的元素並查看哪個最低來確定兩個元素的連接。
同樣，我們立即看到兩個元素是否沒有連接。
我們都知道許多全稱序的例子（任何形式的圖表或排名都是全稱序），但我們可能想不出那麼多明顯的部分序例子。所以讓我們看一些。這將為我們提供一些背景，並幫助我們理解連接是什麼。
為了保持我們的風格，讓我們回顧一下顏色混合么半群，並創建一個顏色混合部分序，其中所有顏色都指向包含它們的顏色。
如果你仔細觀察，你會注意到連接的一個奇特屬性。
在顏色混合序中，任何兩種顏色的連接是它們混合後形成的顏色。
我們看到，當我們通過「大於或等於」來排序數字時，它們形成一個線性序。但數字也可以形成一個部分序，例如，如果我們按「哪個整除哪個」來排序，它們就形成一個部分序，也就是說，如果 $a$ 整除 $b$，那麼 $a$ 在 $b$ 之前，例如，因為 $2 imes 5 = 10$，所以 $2$ 和 $5$ 在 $10$ 之前（但例如 $3$ 不在 $10$ 之前）。
碰巧的是（實際上是有充分理由的），連接操作再次對應於與物件相關的操作：
在數字按整除關係的部分序中，任何兩個數字的連接是它們的最小公倍數。而它們的交集是它們的最大公約數。
讓我們深入探討一下為什麼會這樣。
給定一組包含給定元素組合的集合...
...我們可以定義這些集合的包含序。
給定集合的包含序（通常是包含某些共同元素的集合）是一種序，基於以下二元關係：如果 $A$ 包含 $B$，或者換句話說，如果 $B$ 是 $A$ 的子集，則 $A$ 在 $B$ 之前。
包含序中兩個集合的連接操作是它們的並集，而交集操作是它們的集合交集。
這個圖可能讓你聯想到什麼——如果我們取每個集合中包含的顏色並將它們混合成一種顏色，我們就會得到前面看到的顏色混合部分序。
數字除法序的例子也同構於包含序，即所有可能的質數集合（包括重複的質數，或質數冪）的包含序。這得到了算術基本定理的證實，該定理指出每個數字都可以以唯一的方式寫成質數的乘積。
到目前為止，我們看到了兩種不同的部分序，一種基於顏色混合，另一種基於數字除法，它們都可以通過某些基本元素（第一種情況下的原色，第二種情況下的質數（或質數冪））的包含序來表示。許多其他部分序也可以這樣定義。具體是哪些，這是一個由一個驚人的結果 Birkhoff 表示定理回答的問題。它們是滿足以下兩個標準的有限部分序：
滿足第一個標準的部分序稱為格（lattices）。滿足第二個標準的稱為分配格（distributive lattices）。讓我們寫下來：
所有元素都有連接和交集的部分序稱為格。其交集和連接操作可以相互分配的格稱為分配格。
我們用來構造包含序的「質數」元素是不能作為任何其他元素連接的元素。它們也稱為連接不可約元素。
所以我們可以這樣表述定理：
每個分配格都同構於其連接不可約元素的包含序。
順帶一提，不是分配格的部分序也同構於包含序，只是它們同構於不包含所有元素組合的包含序。
我們現在將更多地討論格（適用於 Birkhoff 定理的序）。格是部分序，其中每兩個元素都有一個連接和一個交集。所以每個格也是部分序，但並非每個部分序都是格（我們將看到這個層次結構中更多的成員）。
大多數基於某種規則創建的部分序都是分配格，例如上一節的部分序，當它們被完整繪製時，也是分配格，例如顏色混合序。
請注意，我們在頂部添加了黑球，在底部添加了白球。我們這樣做是因為否則頂部的三個元素將沒有連接元素，而底部的三個元素將沒有交集元素。
我們的顏色混合格有一個最大元素（黑球）和一個最小元素（白球）。具有最小和最大元素的格稱為有界格。不難看出，所有有限格也都是有界的。
任務 4：證明所有有限格都是有界的。
我們已經多次提到序同構，所以是時候詳細說明它們是什麼了。
給定兩個集合（我們將以數字除法部分序和質數包含序為例），它們之間的同構由以下兩個函數組成：
序同構本質上是它們底層集合之間的同構（可逆函數）。然而，除了它們的底層集合之外，序還有連接它們的箭頭，所以還有一個額外的條件：為了使可逆函數構成序同構，它必須尊重這些箭頭。
兩個序之間的同構是它們底層集合之間的可逆函數，使得將此函數（我們稱之為 $F$）應用於在一個集合中具有某種序的任何兩個元素（我們稱之為 $a$ 和 $b$）應該得到在另一個集合中具有相應序的兩個元素（即 $a ≤ b$ 當且僅當 $F(a) ≤ F(b)$）。
這樣的函數稱為保序函數。
在上一節中，我們看到了如何從（線性）序的定律中移除全稱性定律會產生一個不同的（且有點更有趣的）結構，稱為部分序。現在讓我們看看如果我們移除另一個定律，即反對稱性定律，會發生什麼。
反對稱性定律規定，一個物件不能同時小於和等於另一個物件（或者說 $a ≤ b \iff b
ot\leq a$）。
結果是一種稱為預序（preorder）的結構：
預序是一組元素，以及這些元素之間的二元關係，它遵循自反性和遞移性定律。
預序不完全是日常意義上的序——它可以有從任何點到任何點的箭頭：如果一個部分序可以用來模擬誰在足球方面比誰厲害，那麼一個預序可以用來模擬誰擊敗了誰，無論是直接的（通過比賽）還是間接的。
預序只有一個定律——遞移性 $a ≤ b \land b ≤ c o a ≤ c$（好吧，如果我們算上自反性，就是兩個）。關於間接勝利的部分是這個定律的結果。由於它，所有間接勝利（那些不是直接對玩家獲勝，而是對擊敗他們的某人獲勝）都作為其應用的一個直接結果被添加，如圖所示（我們用較淺的顏色顯示間接勝利）。
結果是，所有「循環」關係（例如，一個較弱的玩家擊敗一個較強的玩家）都只會導致一堆相互連接的物件。
所有這些結構都自然地源於簡單的遞移性定律。
預序可以被視為部分序和等價關係之間的折衷，因為它們恰好缺少這兩種結構不同的屬性——（反）對稱性。因此，如果我們有一堆預序中的物件遵循對稱性定律，那麼這些物件就構成了一個等價關係。如果它們遵循反對稱性的反向定律，它們就構成了一個部分序。
特別是，任何相互之間雙向連接的物件子集（如上面的例子）都遵循對稱性要求。所以，如果我們將所有具有這種連接的元素分組，我們就會得到一堆集合，所有這些集合都基於預序定義了不同的等價關係，稱為預序的等價類。
更有趣的是，如果我們將預序連接從這些集合的元素轉移到集合之間的連接，這些連接將遵循反對稱性要求，這意味著它們將構成一個部分序。
簡而言之，對於每個預序，我們可以定義該預序的等價類的偏序。
我們看到預序是一個強大的概念，所以讓我們更深入地研究一下支配它們的定律——遞移性定律。這個定律告訴我們，如果我們有兩對關係 $a ≤ b$ 和 $b ≤ c$，那麼我們自動就有第三對 $a ≤ c$。
換句話說，遞移性定律告訴我們 $≤$ 關係可以組合，也就是說，如果我們將「大於」關係視為態射，我們就會看到遞移性定律實際上是組合的範疇定義。
（我們還必須驗證該關係是結合的，但這很容易）。
所以，我們懷疑預序是範疇，但真的是這樣嗎？讓我們再次回顧範疇的定義。
範疇是物件的集合（我們可以將它們視為點）和從一個物件到另一個物件的態射（箭頭），其中：
看起來我們已經涵蓋了第二條定律，即遞移性。那麼身份定律呢？我們也有它，在自反性這個名字下。
所以這是官方的——預序就是範疇（聽起來有點明顯，特別是我們也看到預序可以通過包含序簡化為集合和函數，而集合和函數本身就構成了一個範疇）。
預序是範疇，但並非所有範疇都是預序。大多數範疇在給定的兩個物件之間有許多不同的態射。例如，在集合範疇中，從整數集合到布爾值集合可能有無數個函數，以及許多反向的函數。
而預序，兩個物件之間最多只有一個態射，也就是說，我們要麼有 $A ≤ B$，要麼沒有。
所以，就像么半群是一個只有一個物件的範疇一樣，一個序是一個在兩個物件之間最多只有一個態射的範疇。
任何預序都可以看作是一個在兩個物件之間最多只有一個態射的範疇——對於任何 $A$ 和 $B$，如果 $A ≤ B$，則存在一個態射 $A o B$。由於自反性，存在恆等態射。反之亦然：任何在兩個物件之間最多只有一個態射的範疇都可以看作是一個預序。
一個有趣的結論是，由於它們在給定兩個物件之間最多只有一個態射，所以在預序中所有圖都會自動交換。
我們說過部分序和全稱序是預序。這意味著它們也是範疇。
預序特別是範疇論中所謂的骨架範疇（skeletal categories）——沒有同構物件的範疇，也就是說，其中所有同構物件都是相同的。
我猜全稱序沒有特定的「範疇」名稱，但它們也是一種範疇。
在我們回顧上一章的圖時，讓我們看看第二章中定義範疇中兩個物件的餘積（coproduct）的圖。
如果你還記得，這是一個對應於集合範疇中集合包含的操作。
但是等等，難道沒有其他操作對應於集合包含嗎？哦，是的，序中的連接操作。而且不僅如此，序中的連接操作的定義方式與範疇餘積的定義方式完全相同。
$A$ 和 $B$ 的餘積，表示為 $A + B$，是一個物件，滿足：
在序的領域中，我們將連接定義為：
$A$ 和 $B$ 的連接是一個物件 $G$，滿足：
我們可以發現，這兩個定義及其對應的圖基本上是相同的，我們只是將「大於」替換為「有一個唯一的態射」（因為在序中所有態射都是唯一的）。
用範疇論的術語來說，我們可以說：
預序範疇中的範疇餘積是連接操作。
這當然意味著積對應於交集（對偶）。
在範疇論的術語中，序（具有給定類型簽名的最多一個態射的範疇）被稱為「瘦」範疇（thin categories）。
瘦範疇通常用於探索範疇概念，其背景比普通（非瘦）範疇更容易理解。例如，正如我們所見，理解序論中的交集和連接概念將有助於你更好地理解更一般的範疇概念中的積和餘積。
瘦範疇在我們想保持簡單並且不太關心從一個物件到另一個物件的態射之間的差異時也很有用。我們將在下一章中看到一個例子。
使用 Jekyll Book Boilerplate 製作。使用 Inkscape 繪製。使用 Mell Sans 設定字體。
這項作品採用創用 CC 姓名標示-非商業性 4.0 國際授權條款授權。