\[ \newcommand{\bs}{\boldsymbol} \newcommand{\bsX}{\boldsymbol{X}} \newcommand{\bf}{\mathbf} \newcommand{\msc}{\mathscr} \newcommand{\mca}{\mathcal} \newcommand{\msf}{\mathsf} \newcommand{\T}{\text{T}} \newcommand{\tb}{\text{b}} \newcommand{\rest}{\text{rest}} \newcommand{\rme}{\mathrm{e}} \newcommand{\rmi}{\mathrm{i}} \newcommand{\rmj}{\mathrm{j}} \newcommand{\rmd}{\mathrm{d}} \newcommand{\rmm}{\mathrm{m}} \newcommand{\rmb}{\mathrm{b}} \newcommand{\and}{\land} \newcommand{\or}{\lor} \newcommand{\exist}{\exists} \newcommand{\sube}{\subseteq} \newcommand{\lr}[3]{\left#1 #2 \right#3} \newcommand{\intfy}{\int_{-\infty}^{+\infty}} \newcommand{\sumfy}[1]{\sum_{#1=-\infty}^{+\infty}} \newcommand{\vt}{\vartheta} \newcommand{\ve}{\varepsilon} \newcommand{\vp}{\varphi} \newcommand{\Var}{\text{Var}} \newcommand{\Cov}{\text{Cov}} \newcommand{\edef}{\xlongequal{\text{def}}} \newcommand{\prob}{\text{P}} \newcommand{\Exp}{\text{E}} \newcommand{\t}{\text} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\true}{\mathtt{true}} \newcommand{\false}{\mathtt{false}} \newcommand{\fatsemi}{⨟} \newcommand{\versionofnewcommand}{\text{260202}} \]

I. Orders and Galois Connections

I.0. Review of ZFC

在这里, 我们先不对集合做非常严格的叙述, 只基于 ZFC 公理做极笼统的介绍. 笼统地讲, ZFC 构筑于一节逻辑, 集合论会用到的二元谓词 $\in$ 和下面的公理 A.1 – A.9. 注意, ZFC 处理的所有对象都应当被理解为集合. 特别地, 集合的元素本身也是一个集合, 且集合 $s$ 和仅含 $s$ 的集合 $\set{s}$ 是两码事.

A.1 外延公理 (Axiom of Extensionality): 若两集合有着完全相同的元素, 则两集合相等.
$\forall x \forall y(\forall z(z \in x \Leftrightarrow z \in y)\Rightarrow x = y)$
我们形式定义空集 $\varnothing \edef \set{u \in X : u \neq u}$, 其中 $X$ 是任意的集合.
A.2 正则公理 (Axiom of Regularity): 任意非空集合, 至少包含一个与原集合不相交的元素. 此定义侧重于 "运算 (operation)". 另有侧重 "序 (order)" 的等价定义: 任意非空集都含有一个对从属关系 $\in$ 极小的元素.
侧重运算的表述是在说, 对于一个非空集合 $S$, 总存在一个元素 $x$, 使得 $x \cap S = \varnothing$. 即, 找不到一个元素 $y$ 既属于 $x$ 又属于 $S$.
- $\neg \exist y (y \in x \and y \in S)$
侧重序的表述是在说, 对于非空集合 $S$, 总存在一个元素 $x$, 使得任何 $S$ 中的元素 $y$ 不能从属于 $x$.
- $\neg \exist y (y \in S \and y \in x)$
该公理禁止了自我包含和无线递降链. $A\in A$ 是不可能的; 集合的层级必然有终点. 当集合中有一个元素是空集, 那么空集一定是该集合对于 $\in$ 的最小元, 也即与原集合不相交. 注意, 空集是所有集合的子集, 但不一定是某集合的元素. 需要区分 "包含" 和 "属于".
A.3 配对公理 (Axiom of Pairing): 对任意的 $x,y$, 存在集合 $\set{x,y}$, 其元素恰好是 $x$ 与 $y$.
$\forall x \forall y \exist z \forall u (u \in z \Leftrightarrow (x=u \or x=v))$
它是构建更大集合的基本步骤.
另外, 有序对的概念可以用配对公理来做. 因为集合$\set{a,b}$是没有顺序的, $\set{a,b} = \set{b,a}$. Kuratowski 给出了 ordered pair 的定义: $(x,y) \edef \set{\set{x},\set{x,y}}$. 可以进一步定义积集: $X \times Y \edef \set{(x,y) : x \in X, \ y \in Y}$.
A.4 分离公理模式 (Axiom Schema of Specification / Separation): 设 $P$ 是关于集合的一个性质. 用 $P(A)$ 表示集合 $A$ 满足性质 $P$. 那么, 对任意集合 $X$ 和任意性质 $P$, 存在 $X$ 的一个子集 $Y$ 包含了所有 $X$ 中满足了性质 $P$ 的元素. $Y = \set{u \in X : P(u)}$.
$\forall x \exist y \forall u (u \in y \Leftrightarrow u \in x \and P(u))$.
在朴素集合论中, 我们认为一个性质 $P$ 就定义了一个集合. 这会导致经典的罗素悖论: 我能不能构造一个不包含自己的集合? 分离公理模式的设立就是为了解决这类问题. 我们要求构建集合时, 必须从一个已知的集合中取元素. 但这显然会引发另一个问题, 溯流而上, 那个最大的集合是什么? 事实上, 我们需要引入一个断言: 存在一个不包含任何元素的集合, 即空集 $\varnothing$. 想要构建自然数, 可以对空集使用幂集定理 (A.6), 得到 $\set{\varnothing}$, 称它为 $1$, $\varnothing$ 则称为 $0$. 随后, $\set{\varnothing, \set{\varnothing}}$ 称为 $2$... 这样就构造出了所有有限的数学结构. 无穷公理 (A.7) 又说, 存在无穷集. 这样就可以构建无穷序数 $\omega$ (见后文).
A.5 并集公理 (Axiom of Union): 对任意集合, 存在相应的并集 $\bigcup X \edef \set{u : \exist v \in X \text{ such that } u \in v}$
$\forall X \exist U \forall x (x \in U \Leftrightarrow \exist Y(x\in Y \and Y \in S))$.
我们熟悉的 $A \cup B$ 实际上是综合使用配对公理和并集公理的结果. 对于集合 $A, B$ 首先构造集合 $S = \set{A,B}$ (配对公理). 接着, 对 $S$ 应用并集公理, 就得到定义 $A \cup B \edef \bigcup S = \bigcup\set{A,B} $.
A.6 幂集公理 (Axiom of Power Set): 对任意集合 $x$, 存在一个集合包含了 $x$ 的所有子集 $\mca{P}(x)\edef \set{u: u\sube x}$.
注意, 我们定义 $z \sube x$ 为: $\forall x \exist y \forall z(z \in y \Leftrightarrow \forall \omega(\omega\in z \Rightarrow \omega \in x))$.
A.7 无穷公理 (Axiom of Infinity): 存在无穷集.
$\exist x(\varnothing \in x \and \forall y \in x(y \cap \set{y} \in x))$.
如上形式化构建的 $x$ 称为归纳集. 在集合论中, 我们定义任意集合 $u$ 的后继为 $S(u)=u\cup\set{u}$. 也就是说, 归纳集对后继封闭.
A.8 替换公理模式 (Axiom Schema of Replacement): 设 $F$ 是一个以集合 $X$ 为定义域的函数, 则存在集合 $F(X) = \set{F(x) : x \in X}$. 用自然语言讲就是, 如果有一个集合 $X$ 和一个对应规则 $F$, 那么按此规则把集合里的每个元素都做替换, 生成的新元素也能组成一个集合. 或者更简单地, 函数的像也是一个集合.
$\forall A(\forall x \in A \exist !y \vp(x,y)) \Rightarrow \exist B\forall y (y \in B \Leftrightarrow \exist x \in A \vp(x,y))$.
A.9 选择公理 (Axiom of Choice): 设有一族互不相交的非空集合, 我们总可以在每一个集合中选取一个元素, 组成一个新的集合.
该定理作为 ZFC 的 "C", 存在着争议. 不过暂时先不管它.
- $\forall \mca{F}(\varnothing \in \mca{F} \Rightarrow \exist f (f:\mca{F}\to\bigcup \mca{F} \and \forall A \in \mca{F}(f(A)\in A)))$.
- 其中, $\mca{F}$ 是由非空集合组成的族. $f$ 被称为选择函数.

I.1 Orders

在一个由若干节点构成的系统中, 根据连接的性质和拓扑结构, 可以从两个维度来将其分类. 其一是作 无向 (Undirected) 和 有向 (Directed) 的区分, 其二是作 无环 (Acyclic) 和 带环 (Cyclic) 的区分. 一个重要的哲学洞察是, 逻辑本质上是无环的, 因此在数学与计算机科学中, 许多研究都聚焦于 有向无环图 (Directed Acyclic Graph, DAG). 尽管在生命系统中, 带环系统似乎是无处不在的.

I.1.1 Preorders

在集合论的视角中, 我们使用 "序关系 (Order Relations)" 来捕捉这些系统的特性. 一个比较基本的序关系是 预序关系 (Preoreder Relations). 可以试着想象, 如果要给一个集合 $X$ 赋予一个序关系 $\leq$, 最简单, 不会导致矛盾的约束条件是什么.

Definition 1.1.1 (Preorders)

我们定义集合 $X$ 上的预序关系是 $X$ 上的一个二元关系, 用 $\leq$ 标记, 并且满足如下性质:

反身性 (Reflexivity): $x \leq x$, for all $x \in X$;
传递性 (Transitivity): If $x\leq y$ and $y \leq z$, then $x \leq z$.

特别地, 如果 $x \leq y$ 且 $y \leq x$, 我们称 $x,y$ 等价 (Equivalent), 一般记作 $x \sim y $. 具有预序关系的 set-relation pair $(X, \leq)$ 称为 预序 (preorder). 也就是说, 等价关系就是具备了对称性的预序关系. 等价关系的定义如下给出:

Definition 1.1.2 (Equivalence)

我们定义集合 $A$ 上的等价关系是 $A$ 上的一个二元关系, 用 $\sim$ 标记, 并且满足如下性质:

Reflexivity: $a \sim a$, for all $a \in A$;
Symmetry: $a \sim b$ $\Leftrightarrow$ $b \sim a$, for all $a, b \in A$;
Transitivity: if $a \sim b$ and $b \sim c$ then $a \sim c$, for all $a, b, c \in A$.

Example 1.1.3 (Discrete Preorders)

我们常说, 集合是无序的. 用本章的语言讲, 所有的集合 $X$ 都可被视作一个离散的预序 $(X, \leq)$. 首先, 我们朴素地定义 $x\leq x, \ \forall x \in X$.

接下来, 需要回顾对 "relation" 的定义: 集合 $A$ 到 $B$ 的一个二元关系 $R$ 是笛卡尔积 $A \times B$ 的一个子集. 若 $(a,b) \in R,\ a\in A,\ b \in B$, 我们就称 $a$ 和 $b$ 有 "关系", 记作 $aRb$.

因此, 如果我们定义集合 $X$ 上的 $\leq$ 关系为 $\{ (x,x) \mid x \in X \}$, 即任意元素只和自身有 $\leq$ 关系, 那么 $(X,\leq)$ 就是一个预序, 且是最稀疏的预序. 到这儿我们就不再装模作样地用 $\leq$ 了, 直接用等号就好, 即任一集合天然蕴含一个最稀疏的预序 $(X, =)$

Example 1.1.4 (Codiscrete Preorders)

同样地, 任一集合也天然地蕴含一个最密集的预序, 任取两个元素都具有 $\leq$ 关系. 也即, 对集合 $X$, 构造关系 $\leq\edef X \times X \sub X \times X$. 我们称这样的预序为 Codiscrete Preorders. 此处 "co-" 当取 "反" 义.

Example 1.1.5 (Booleans)

对于 booleans $\mathbb{B} = \{ \false,\ \true \}$, $\false \leq \true$, 也构成一个预序.

Definition 1.1.6 (Partial Orders and Skeletal Preorders)

Preorders 的信息存在冗余, 互相等价的元素可以兼并为一. 执行完这个操作, 我们就得到了 偏序 (Partial Orders, Posets), 它需要满足以下条件:

Reflexivity: $x \leq x$, for all $x \in X$;
Transitivity: If $x\leq y$ and $y \leq z$, then $x \leq z$;
Skeletality: $x \sim y$ implies $x = y$.

由于第三个条件在范畴论中被称为 skeletality, partial orders 也被叫做 skeletal preorders.

Remark 1.1.7

我们总喜欢把集合论关于序 (Orders) 的语言与图 (Graphs) 的语言结合起来. 因此接下来给出 Graphs 的定义.

Definition 1.1.8 (Graphs)

A graph $G = (V, A, s, t)$ consists of a set $V$ whose elements are called vertices, a set $A$ whose elements are called arrows, and two functions $s,t : A \to V$ known as the source and targets respectively. Given $a \in A$ with $s(a) = v$ and $t(a) = w$, we say that $a$ is an arrow from $v$ to $w$.

Example 1.1.9

举个例子. 在四个 Vertices $V = \{ 1, 2, 3, 4 \}$, 画五个 Arrows $A = \{ a, b, c, d, e \}$; 每个箭头的 source 和 target 分别由函数 $s$ 和 $t$ 给出.

Fig.Graph

Arrows	Source $s(a) \in V$	Target $t(a) \in V$
$a$	1	2
$b$	1	3
$c$	1	3
$d$	2	2
$e$	2	3

注意, 虽然没有 4 到 1, 2, 3 的路径, 但是 4 到 4 自身的路径是存在的, 只是我们称该路径的长度为 0. 同时, 1 到 2 有无穷多条路径, 因为可以在 2 处通过 $d$ 打转任意次.

Remark 1.1.10

我们总可以构建一个 Hesse 图 $G = (V,A,s,t)$ 和一个 preorder 之间的映射关系, 而且它至少是个满射, 也就是说任意的 Preorder 都能找到一个对应的 Graph. 以 Example 1.9 为例, 该 Graph 对应的 Preorder $(P, \leq)$ 可以规定如下:

\[ \begin{cases} \ P = \{ 1, 2, 3, 4\}\\ \ 1\leq1,\ 1\leq2,\ 1\leq3,\ 2\leq2,\ 2\leq3,\ 3\leq3,\ 4\leq4 \end{cases} \]

注意, 从 Graph 到 Preorder 的映射不是单射, 这是因为冗余边的存在, 例如 Example 1.9 中 1 到 3 有两个箭头, 但这在 Preorder 中是体现不出来的.

Definition 1.1.11 (Total Order)

Total Order (全序) 任意两个元素都 "可比较" 的 Preorder.

Reflexivity: $x \leq x$, for all $x \in X$;
Transitivity: If $x\leq y$ and $y \leq z$, then $x \leq z$;
Comparability: For all $x,y$, either $x\leq y$ or $y\leq x$.

Remark 1.1.12

Discrete preorder 并非任意两个元素都不可比较. Reflexivity 保证了自身对自身是可比较的.

Remark 1.1.13 (Partition from Preorder)

对于一个集合, 我们可以做若干种 partition. 我们称, a partition $P$ is finer than a partition $Q$ if, for every part $p \in P$, there is a part $q \in Q$ such that $A_p \subseteq A_q$. 我们可以说 $Q$ is coarser than $P$ (更粗糙). 同时, 集合 $A$ 上的 partition 可以被看作是一个 $A$ 上的满射. 即, 将每个 $A$ 中的元素映射到对应分类的盒子, 所有盒子的编号构成 partition set $P$.

从满射的角度看, 我们也可以说 $f : A \twoheadrightarrow P$ is finer than $g : A \twoheadrightarrow Q$ if there is a function $h : P \to Q$ such that $f \fatsemi h = g$.

Example 1.1.14

对任意集合 $S$ 都有一个最粗糙的 partition, 将所有元素都打包为一部分, 其对应满射 $!: S \to \{1\}$, 我们称之为 unique function. 同样地, 对任意集合 $S$ 也有最精细的 partition, 每个元素都分开打包, 其对应满射 $\text{id}_S : S \to S$, 即 identity function.

Definition 1.1.15 (Upper Sets)

Given a preorder $(P,\leq)$, an upper set in $P$ is a subset $U$ of $P$ that satisfying the condition that if $p \in U$ and $p \leq q$, then $q \in U$. 也就是说, 如果一个元素在 upper set 中, 那么所有比它大的也在其中. 记 $\mathsf{U}(P)$ 为所有 P 上的 upper set 构成的集合. 我们可以自然地给这个集合 $\msf{U}$ 一个序关系 $\leq$: 对于 $U, V \in \msf{U}$, 若 $U \subseteq V$, 则 $U \leq V$. 虽然这从自然语言的观点来看有点脱裤子放屁, 但 $\subseteq$ 和 $\leq$ 在数学上的意义是大为不同的.

Proposition 1.1.16

The preorder of upper sets on a discrete preorder on a set $X$ is simply the power set $\msf{P}(X)$.

我认为书中这样讲会引起混淆, 这句话缩句结果是 The preorder is the set, 让人觉得略摸不着头脑. 不过就当它是简单的说法好了.

Definition 1.1.17 (Product Preorder)

Given preorders $(P,\leq)$ and $(Q,\leq)$, we define a preorder structure on the product set $P \times Q$ by setting $(p,q) \leq (p^\prime, q^\prime)$ if and only if $p\leq p ^\prime \land q \leq q^\prime$. We call this the product preorder.

Definition 1.1.18 (Opposite Preorder)

Given a preorder $(P,\leq)$, we define the opposite preorder $(P, \leq^{\t{op}})$ to have the same set of elements, but with $p \leq^{\t{op}} q$ if and only if $q\leq p$.

I.1.2 Monotone Maps

接下来考察多个集合 / Preorders 之间的关系. 集合之间可以由映射联系, 而性质比较好的映射应当是保序的.

Definition 1.2.1 (Monotone Maps)

A monotone map between preorders $(A, \leq_A)$ and $(B,\leq_B)$ is a funtion $f : A \to B$ such that, $\forall x,y\in A$, if $x\leq_A y$ then $f(x)\leq_B f(y)$.

Proposition 1.2.2

对于一个 preorder $(P,\leq)$, 考察映射 $\msf{U}(P) \to \msf{P}(P)$, 由 proposition 1.16, 当 $\msf{U}$ 中的每个集合被映射到 $\msf{P}$ 中的自身, 该映射就是一个 monotone map.

Proposition 1.2.3 (Yoneda Lemma)

Let $(P,\leq)$ be a preorder. Then:

The set $\uparrow p \edef \{ p^\prime \in P\ \mid p \leq p^\prime \}$ is an upper set, for any $p \in P$.
The map $\uparrow\ :\ P^{\t{op}} \to \msf{U}(P)$ is a monotone map.
$p \leq p^\prime$ in $P$ if and only if $\uparrow (p^\prime) \subseteq$ $\uparrow (p)$.

这实际上传递了一个思想: knowing an element $p$ 和 knowing its upper set $P$ 是等价的. 也就是说, 孤立的元素与元素之间的关系可以互相转化.

Proposition 1.2.4 (Pullback)

Any surjective funciton $f : X \twoheadrightarrow Y$ induces a monotone map $f^* : \msf{Prt}(Y) \to \msf{Prt}(X)$, going "backwards". It is defined by sending a partition $s : Y \twoheadrightarrow P$ to the composite $f \fatsemi s : X \twoheadrightarrow P$.

这段话有些难以理解, 我们一步步来. 由于范畴论关心态射, 我们考虑将以满射的形式看待 partition. 首先, $f$ 作为一个满射, 是 $X$ 上的一个 partition, $f \in \msf{Prt}(X)$. 接下来, 我们再通过满射 $s$ 对 $Y$ 进行一次 partition, $s \in \msf{Prt}(Y)$. 若将 $f$ 与 $s$ 复合, 就可以自然地得到一个 $X$ 上的新的 partition, 且 $f \fatsemi s$ is finer than $f$. 因此我们说, Y 上的 partition $s$ 会自然地产生一个 $X$ 上的 partition $f \fatsemi s$, 这便是由 $f$ 确定的, 或者说诱导的一个映射 $f^* : \msf{Prt}(Y) \to \msf{Prt}(X),\ s \mapsto f \fatsemi s$. 那么, 为什么这个操作叫 "pullback" 呢? 因为按理说我们是要将一整块带骨肉 $X$ 细细切作臊子 $P$, 各种 partition 操作都是直接做在 $X$ 上的; 但我们这里引入了一个中间态 $Y$, 先把大块带骨肉 $X$ 用 $f$ 切成若干小块 $Y$, 再对这些小块做不同的操作 $s$, 例如不见半点肥的, 不见半点瘦的, 莫要见一丁点肉. 结果对 $Y$ 的操作竟 "反作用" 于 $X$ 身上. $Y$ 到 $X$ 的反向即为 pullback 义.

Proposition 1.2.5

For any preorder $(P, \leq_P)$, the identity function is monotone.
If $(Q, \leq_Q)$ and $(R, \leq_R)$ are preorders and $f : P \to Q$ and $g : Q \to R$ are monotone, then $(f \fatsemi g) : P \to R$ is also monotone.

Definition 1.2.6 (Dagger Preorder)

Let $(P,\leq)$ be a preorder. We say $(P, \leq)$ is a dagger preorder if $\forall p, q \in P,\ p \leq q \Rightarrow p \leq q$.

在预序的语境下, dagger condition 和 equivalence 的 symmetry condition (Definition 1.2) 是相同的. 我们在后面还会看到 dagger 在范畴论中的定义, 从而理解为什么要定义这么个新概念.

Proposition 1.2.7

A skeletal dagger preorder is just a discrete preorder, and hence can be identified with a set.

Arrows	Source \(s(a) \in V\)	Target \(t(a) \in V\)
\(a\)	1	2
\(b\)	1	3
\(c\)	1	3
\(d\)	2	2
\(e\)	2	3