我们用映射来表达集合上的额外结构，引出图、动力系统以及其他结构类型的例子。然后我们研究保持结构的映射。

第三篇、范畴的例子——有向图及其他结构

回顾第十讲：

1. 给定一个没有不动点的球的自态射，我们能构造出从球到边界的收缩。
2. 布劳威尔证明不可能有这样的收缩。

由纯逻辑推导：

1. 球的每个自态射都有一个不动点。

我们进一步看到

1. 球面和球体不可能同构（因为球面确实有一个无不动点的自态射，例如它的对映映射）。

特别重要的是，我们所讨论的范畴不是抽象集合和任意函数的范畴：它必须是某种内聚 cohesive 对象和连续 continuous 映射的范畴。

这里的内聚性指的是对象中的点之间的相互作用（结构）。连续性则是指这种对象内部元素之间的相互作用是如何被映射所保持的（结构的保持）。

我们并不关心究竟是哪种具体范畴。重要的是，球面和球体是通过某些具有特定性质的映射联系在一起的，我们在第 1 点中详细说明了这一点。其次，第 2 点在集合与函数范畴中不成立。3 和 4 也不成立：例如，球体、球面和圆在集合范畴中都是同构的（因为球面同构于 $R^2$，球体同构于 $R^3$，圆同构于 $R$，而 $R,R^2,R^3$ 相互同构（可以借助 Hilbert 曲线）！当然有许多范畴都具有使 1234 成立所需的性质：例如拓扑空间和连续映射范畴、光滑空间和光滑映射范畴等等。这些范畴之间有本质区别。精确地说明它们并讨论其区别的任务，留待更高级的著作。

相反，我们建议定义和研究某些更简单的范畴，它们本身也很有意义，而且表现出内聚范畴的许多特征。我们的所有例子都将说明一种基本方法：为了使某些不精确的已知范畴变得精确，我们可以尝试用集合范畴中的结构来模拟它，这些结构总是表达为给定映射的特定配置。本章的主旨是快速浏览结构的一些可能概念，尤其是初步介绍保持结构 structure-preserving 映射这个有力概念。本文中的练习与前面的练习一样，只涉及关联律在给定定义中的应用。当相关范畴在以后出现时，我们将更缓慢、更仔细地处理它们。

1、集合自态射 ${\mathcal{S}}^{\circlearrowright }$ 的范畴

前文已经隐含的提到了集合自态射范畴，其中的对象是一个配有特定自态射的集合。我们用 $\mathcal{S}$ 表示目前为止一直讨论的集合范畴。 $\mathcal{S}$ 中的映射可以看作是任意的 arbitrary；即它只要求为定义域中的每一个点都赋予陪域中的唯一值，除此之外不附加任何其他限制。因此，尽管 $A$ 中的点数在 $\mathcal{S}$ 中被同构保持，但 $\mathcal{S}$ 本身并不能真正赋予任何性质来区分集合 $A$ 中的一点与另一点。我们所举的许多例子比如时间线也只被 $\mathcal{S}$ 捕捉到了部分性质，因为时间的有序性涉及到更多的”结构“；然而，所有的例子在 $S$ 中都有它们的影子，而且在 $\mathcal{S}$ 中可以进行的计算（映射复合以及即将讨论的乘积等）已经为真实的例子提供了一些启发。如果考虑比 $\mathcal{S}$ 中的对象结构更丰富的对象范畴，我们就有望在这些影子之上看到更清晰的图像，并通过相同的范畴计算为例子提供更多的启发。图示如下，我们的计划是

其中 $\mathcal{M}$ 表示真实但不确切的范畴， ${\mathcal{S}}^T$ 表示带有一个特定结构 $T$ ，可以在 $\mathcal{S}$ 上被构造出来的范畴。箭头表示在这些范畴之间的合适映射，即后面我们会提到的 函子 functor 。

现在我们回过来讨论集合自态射的范畴 ${\mathcal{S}}^{\circlearrowright }$。其中的对象是任意配有自态射 $\alpha$ 的集合 $X$，记作 $X^{\circlearrowright \alpha }$。而但定义范畴最关键的还是映射，以及映射复合的规则，这里范畴 ${\mathcal{S}}^{\circlearrowright }$ 的映射是那些保持结构（即自态射）的映射，即映射 $X^{\circlearrowright \alpha }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$ 是两个集合 $X\stackrel{f}{\to }Y$ 之间的映射（首先是 $\mathcal{S}$ 上的映射），且满足 $f\circ \alpha =\beta \circ f$。在完成几个练习之后你将看到这确实是描述保持给定结构最恰当的定义。

命题 1：若 $X^{\circlearrowright \alpha }\stackrel{f}{\to }{Y}^{\circlearrowright \beta },Y^{\circlearrowright \beta }\stackrel{g}{\to }{Z}^{\circlearrowright \gamma }$ 都是 ${\mathcal{S}}^{\circlearrowright }$ 中的映射，则其复合 $g\circ f$ 也是其中的映射。

证明： 首先作为 $\mathcal{S}$ 中的映射， $f,g$ 满足 $X\stackrel{f}{\to }Y,Y\stackrel{g}{\to }Z$，因此 $X\stackrel{g\circ f}{\to }Z$ 也是 $\mathcal{S}$ 中的映射。其次 $g\circ f$ 满足 $(g\circ f)\circ \alpha =g\circ (f\circ \alpha )=g\circ (\beta \circ f)=(g\circ \beta )\circ f=(\gamma \circ g)\circ f=\gamma \circ (g\circ f)$。因此 $X^{\circlearrowright \alpha }\stackrel{g\circ f}{\to }{Z}^{\circlearrowright \gamma }$ 。

${\mathcal{S}}^{\circlearrowright }$ 中的对象具有自态射 $\alpha$ 所蕴含的所有结构，这是因为如果两个对象同构，那么不但它们具有相同数量的元素，还有相同的不动点数目，相同数目的同长轨道等等。这些种种数目刻画了 ${\mathcal{S}}^{\circlearrowright }$ 中对象的内在性质（也就是集合自态射的性质）。

2、 ${\mathcal{S}}^{\circlearrowright }$ 的典型应用

${\mathcal{S}}^{\circlearrowright }$ 中的对象在动力系统或自动机中经常出现。记 $X$ 是某个系统所有可能状态的集合， 自映射 $\alpha$ 是其状态随时间演进的规则。例如当前系统处于状态 $x$，在一个时间单位后它进入状态 $\alpha (x)$，两个时间单位后进入状态 ${\alpha }^2(x)$ 等等。因此我们可以询问这样的问题：

1. 可达性（accessibility）：给定状态 $x$，是否存在状态 $x^{\prime }$ 满足 $\alpha (x^{\prime })=x$？
2. 收敛至平衡态：给定状态 $x$，是否存在充分大的 $n$ 满足 ${\alpha }^{n+1}(x)={\alpha }^n(x)$。、

3、 ${\mathcal{S}}^{\circlearrowright }$ 的两个子范畴

给自态射的类型加上限制，我们就可以得到两个 ${\mathcal{S}}^{\circlearrowright }$ 的子范畴：其中 ${\mathcal{S}}^e$ 指以所有配有幂等自态射的集合为对象的子范畴，而 ${\mathcal{S}}^{\circlearrowright \circlearrowleft }$ 表示以所有配有可逆自态射（自同态、置换）的集合为对象的子范畴。在这两种情况下，映射的定义与原范畴相同。

4、自态射的范畴

若 $\mathcal{C}$ 是任意范畴，我们可以以相应的方式构造 ${\mathcal{C}}^{\circlearrowright }$。其对象就是原范畴上的自态射，其映射就是一个原范畴上的映射且满足前述的复合律。在 ${\mathcal{C}}^{\circlearrowright }$上也有很多子范畴（即那些等变的 equivariant 自态射），例如

它们分别是

其中， involution 意为对合映射，即 $\theta \circ \theta =1_A$，即自己是自己的逆映射。

是否存在一个自态射既是自同态又是幂等映射？首先 $1_A$ 是这样一个自同态。除此之外假设 $\alpha$ 是这样一个自同态，那么由于 $\alpha \circ \alpha =\alpha ,\alpha \circ \beta =1_A,\beta \circ \alpha =1_A$，因此 $1_A=\alpha \circ \beta =(\alpha \circ \alpha )\circ \beta =\alpha \circ (\alpha \circ \beta )=\alpha \circ 1_A=\alpha$，也就是说这样的自同态只有 $1_A$。

练习：若幂等映射有收缩，它有什么性质？

解答：若幂等映射 $\alpha$ 有收缩，则存在 $r\circ \alpha =1_A$，又因为 $\alpha \circ \alpha =\alpha$，则 $1_A=r\circ \alpha =r\circ (\alpha \circ \alpha )=(r\circ \alpha )\circ \alpha =1_A\circ \alpha =\alpha$。也就是说 $\alpha$ 只能是 $1_A$。

也就是说幂等映射不需要有双边逆才是恒等映射，只要有单边逆即可（有收缩或有截面）。

对合映射 $\theta$ 的特点是，它只有不动点或 2-轨道。图示如下：

命题：给定一个有限集合 $A$。

1. $A$ 有偶数个元素当且仅当存在一个 $A$ 上的对合映射没有不动点。
2. $A$ 有奇数个元素当且仅当存在一个 $A$ 上的对合映射只有一个不动点。

证明：

1. 必要性：考虑数学归纳法。如果 $A$ 有两个元素 $a_1,a_2$ 那么显然存在映射 $f(a_1)=a_2,f(a_2)=a_1$ 满足条件。假设 $A$ 有 $2n$ 个元素时必要性成立，那么当它有 $2(n+1)$ 个元素时，任取其中含 $2n$ 个元素的子集 $B$，存在 $f$ 在 $B$ 上为对合映射满足条件。设 $A\mathrm{\setminus }B=\{a_1,a_2\}$，令 $f^{\ast }(x)=f(x),x\in B,f^{\ast }(a_1)=a_2,f^{\ast }(a_2)=a_1$，则 $f^{\ast }$ 为 $A$ 上的对合映射，且没有不动点。

   充分性：若存在 $f$ 为 $A$ 上的对合映射且没有不动点，任取 $x\in A$，则 $f(x)\in A,f(x)\ne x$。考虑 $f$ 在 $A\mathrm{\setminus }\{x,f(x)\}$ 上的限制 $f_{\ast }$，它是 $A\mathrm{\setminus }\{x,f(x)\}$ 上的对合映射。 这是因为 $f(f(x))=x$，且对合映射可逆，故它在限制上的像 $f(A\mathrm{\setminus }\{x,f(x)\})\subset A\mathrm{\setminus }\{x,f(x)\}$。我们可以按照这种方法从剩余的集合上不断移去点对 $\{x,f(x)\}$，直到元素数目少于 2 个。假设只剩下一个元素，那么限制 $f_{\ast }$ 就是单元集上对合映射，它必然有一个不动点，而这个不动点也是原映射的不动点（因为它是原映射的限制），因此矛盾。故当元素数目少于 2 个时，它只能为空。这样我们就证明 $A$ 的元素数目一定是偶数个。

2. 必要性：考虑数学归纳法。如过 $A$ 有一个元素 $a$，那么显然 $1_A$ 是这个对合映射，且只有一个不动点。假设 $A$ 有 $2n-1$ 个元素时必要性成立，那么当它有 $2n+1$ 个元素时，任取其中含 $2n-1$ 个元素的子集 $B$，存在 $f$ 在 $B$ 上为对合映射满足条件。设 $A\mathrm{\setminus }B=\{a_1,a_2\}$，令 $f^{\ast }(x)=f(x),x\in B,f^{\ast }(a_1)=a_2,f^{\ast }(a_2)=a_1$，则 $f^{\ast }$ 为 $A$ 上的对合映射，且只有一个不动点。

   充分性：若存在 $f$ 为 $A$ 上的对合映射且只有一个不动点，记为 $x_0$。考虑 $f$ 在 $A\mathrm{\setminus }\{x_0\}$ 上的限制 $f_{\ast }$，它是 $A\mathrm{\setminus }\{x_0\}$ 上的对合映射且没有不动点。那么根据 1 中的充分性知 $A\mathrm{\setminus }\{x_0\}$ 有偶数个元素，因此 $A$ 有奇数个元素。

尽管这里我们使用了奇数偶数这样的数量概念，但是我们可以用这两条充要条件作为对象奇偶性的定义。因此我们实际上就不需要计算对象中的点数目。在现实生活中，袜子的配对就是这样一个没有不动点的对合映射（袜子不可能自己配对自己），既然每一只袜子都能找到它的配对，袜子的数目一定是偶数。

练习：满足 ${\alpha }^3=\alpha$ 的自态射也构成一个范畴。证明幂等范畴和对合范畴是它的子范畴。

解答：幂等范畴是子范畴 ${\alpha }^2=\alpha ⟹{\alpha }^3={\alpha }^2\circ \alpha =\alpha \circ \alpha =\alpha$。对合范畴是子范畴 ${\alpha }^2=1_A⟹{\alpha }^3={\alpha }^2\circ \alpha =1_A\circ \alpha =\alpha$。

练习：若三元集自态射满足 $\alpha (x)=y,\alpha (y)=z,\alpha (z)=y$，则它满足 ${\alpha }^3=\alpha$，但它不是幂等也不是对合。

解答：显然。

这说明 ${\alpha }^3=\alpha$ 的范畴是真包含幂等范畴和对合范畴。

5、非自反图 Irreflexive graphs

还有一个重要的范畴可以将 ${\mathcal{S}}^{\circlearrowright }$ 视为其子范畴。我们记为 ${\mathcal{S}}^{\cdot \rightrightarrows \cdot }$ 为非自反有向多图。其对象是任何配有一对平行映射的一对集合

其中 $X$ 称为这个图的箭头 arrow 集合而 $P$ 称为这个图的节点 dot 集合。$x\in X$ 是一个箭头， $s(x),t(x)$ 分别称为这个箭头的出射点 source 和入射点 target 。这个术语源于非自反有向多图（以下简称图），图示如下

其中 $p,q,m,k,r,n$ 是图的节点， $a,b,c,d,e$ 是图的箭头（或有向边）。所谓有向图就是边是有向边，所谓多图就是两节点之间可以有多条边，这就是最一般的图。该范畴中的每个对象对应着上面这个图示所描述的非自反有向多图。

非自反什么意思？

其映射则也要定义为保持图结构，即

对象间的映射是任意 $\mathcal{S}$-映射 $X\stackrel{f_A}{\to }Y,P\stackrel{f_D}{\to }Q$ 满足方程 $f_{D}s=s^{\prime }{f}_A,f_{D}t=t^{\prime }{f}_A$，即以下交换图

简言之就是要保持入射和出射关系。 $f_A,f_D$ 的下标只是为了指示它们分别是箭头集合和节点集合的映射。

练习：证明若 $f,g$ 是图范畴的映射，那么其复合映射的分量就是其分量的复合。即 $(g\circ f{)}_A=g_A\circ f_A,(g\circ f{)}_D=g_D\circ f_D$。

证明：由 $f,g$ 定义可知， $f_{D}s=s^{\prime }{f}_A,f_{D}t=t^{\prime }{f}_A,g_D{s}^{\prime }=s^{″}{g}_A,g_D{t}^{\prime }=t^{″}{f}_A$，因此 $(g_D\circ f_D)s=s^{″}(g_A\circ f_A),(g_A\circ f_{A}t=t^{″}(g_A\circ f_A)$。（不停使用结合律即可，或者画交换图）。

我们很自然的把这两个 $\mathcal{S}$-映射构成的 ${\mathcal{S}}^{\cdot \rightrightarrows \cdot }$ -映射记为 $g\circ f$。这样我们在形式上就有$(g\circ f{)}_A\dot{=}{g}_A\circ f_A,(g\circ f{)}_D\dot{=}{g}_D\circ f_D$。

图有许多重要应用。譬如我们可以把节点看成城镇，箭头看成其间的道路（拓扑式的地图，如哥尼斯堡七桥问题的示意图）；节点看成名词，箭头看成及物动词（知识图谱）。电路图、信息流图等等都可以视为 ${\mathcal{S}}^{\cdot \rightrightarrows \cdot }$ 中的对象。被同构所保持的图的数字特征中，除了箭头和点的总数，还有环的数目，连通分支的数目等等。

6、自态射作为一种特殊的图

前面我们说自态射范畴可以视为图范畴的一个子范畴。这是因为对任意自态射范畴中的对象 $X^{\circlearrowright \alpha }$，我们可以将其视为下面的对象

这很好理解，因为如果我们画出任意一个自态射的内在图示，就会发现它其实是图的一个特例。 $X$ 中的每一个元素 $x$ 都是一个节点， $(x,\alpha (x))$ 构成一个箭头，二者分别是它的出射点 $s(x)=x$ 和入射点 $t(x)=\alpha (x)$ 。显然这说明 $s=1_X,t=\alpha$。

同理，自态射范畴中的映射也可以视为图范畴中的映射。给定

显然它满足

这是因为自态射范畴中映射的复合律 $f\circ \alpha =\beta \circ f$ 满足图范畴映射中入射映射 $t$ 的复合律，而出射映射的复合律则由于恒等映射自动满足 $f\circ 1_X=1_Y\circ f$。

记这种把自态射范畴视为图范畴子范畴的操作为 $I$，也即对任意自态射范畴中的对象 $X^{\circlearrowright \alpha }$， $I(X^{\circlearrowright \alpha })$ 是图范畴子范畴中的对象，对任意自态射范畴中的映射 $X^{\circlearrowright \alpha }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$， $I(X^{\circlearrowright \alpha })\stackrel{I(f)}{\to }I(Y^{\circlearrowright \beta })$ 是图范畴中的映射。其中 $I(X^{\circlearrowright \alpha })=(X,X,1_X,\alpha )$， $I(f)=f$。

命题：证明 $I$ 满足 $I(g\circ f)=I(g)\circ I(f)$，因此它确实保持了范畴的基本定义（对象、映射、映射的复合）。

证明：我们只需证明它逐点成立。注意图范畴中的映射 $I(f)$ 有这么几项功能，

1. 把节点映射为节点。即把 $X$ 中的元素映射到 $Y$ 中。
2. 把箭头映射为箭头。即保持图 $X$ 中的出入射关系，也就是把 $X$ 中的箭头出射点映射为 $Y$ 中对应箭头的出射点，把 $X$ 中的箭头入射点映射为 $Y$ 中对应箭头的入射点。

因此为了证明两者相等，只需证明它逐点成立，也就是对任意节点和箭头， $I(g\circ f)$ 与 $I(g)\circ I(f)$ 的像相同。

1. 显然，因为此时 $I(f)=f$。映射的复合由集合映射的复合律保证。

2. 显然。因为根据图复合律性质 $,I(g\circ f{)}_D\alpha =\gamma I(g\circ f{)}_A$， $I(g\circ f)$ 把箭头 $(x,\alpha (x))$ 映射为 $(z,\gamma (z))$。而由复合律性质 $I(f)\alpha =\beta I(f)$，$I(f)$ 把箭头 $(x,\alpha (x))$ 映射为箭头 $(y,\beta (y))$；由复合律性质 $I(g)\beta =\gamma I(g)$， $I(g)$ 把箭头 $(y,\beta (y))$ 映射为箭头 $(z,\gamma (z))$。根据前两组复合律性质，我们得出 $(I(g)\circ I(f))\alpha =\gamma (I(g)\circ I(f))$，即 $I(g)\circ I(f)$ 把箭头 $(x,\alpha (x))$ 映射为箭头 $(z,\gamma (z))$。因此对任意箭头而言 $I(g)\circ I(f)$ 与 $I(g\circ f)$ 逐点相等。即以下交换图成立

   

综上我们证明了 $I(g\circ f)=I(g)\circ I(f)$。

注意到，若 $I(g)\circ I(f)=I(g\circ f)$，则我们自然有 $(I(g)\circ I(f){)}_D=I(g{)}_D\circ I(f{)}_D,(I(g)\circ I(f){)}_A=I(g{)}_A\circ I(f{)}_A$，这与上个练习的规定一致。

命题（全性）：给定由集合自态射经过函子 $I$ 得到的图，若它们之间存在 ${\mathcal{S}}^{\cdot \rightrightarrows \cdot }$-同态，则 $f_A=f_D$，也就是说这个态射是从自态射范畴的映射经过函子而来。

这个问题说的有点不清楚，用数学语言来说就是，若下面的图范畴中的对象是 $I(X^{\circlearrowright \alpha }),I(Y^{\circlearrowright \beta })$（所谓的集合自态射范畴中的对象经过函子 $I$ 得到），且二者之间在图范畴上存在态射，

则 $f_A=f_D$。

证明：首先该同态满足 $f_D\alpha =\beta f_A,f_D{1}_X=1_Y{f}_A$。后面这个性质说明 $f_D=f_A$。也就意味着实际上 $f\dot{=}{f}_D=f_A$ 满足 $f\alpha =\beta f$，它是集合自映射范畴中的映射 $f:X^{\circlearrowright \alpha }\to Y^{\circlearrowright \beta }$。因此它确实可以视为从集合自映射范畴到图范畴的嵌入函子 $I$ 的像。

函子的全性指的是，给定函子 $F$，若任意目标范畴对象之间的态射 $F(A)\stackrel{g}{\to }F(B)$，都可以找到原范畴对象之间的态射 $A\stackrel{f}{\to }B$，使得 $F(f)=g$，则称 $f$ 是全的。说白了就是 $F:\text{Hom}(A,B)\to \text{Hom}(F(A),F(B))$ 是满射。

通过嵌入函子 $I$，我们拓展了我们的范畴包含关系

7、更简单的范畴 ${\mathcal{S}}^{\cdot \to \cdot }$：对象只是集合的映射

不同于自态射范畴的另一个图范畴的子范畴是集合映射范畴，它的对象是任意两个集合之间的映射，它的映射是满足交换方形集合映射。即

把 ${\mathcal{S}}^{\cdot \to \cdot }$ 嵌入 ${\mathcal{S}}^{\cdot \rightrightarrows \cdot }$的函子是通过把对象 $X\stackrel{\alpha }{\to }Y$ 视为 $X\rightrightarrows Y$ 且源映射与目标映射为 $\alpha$。此外，从自态射范畴 ${\mathcal{S}}^{\circlearrowright }$ 到 ${\mathcal{S}}^{\cdot \to \cdot }$ 也有一个显然的嵌入，因为自态射就是一种特殊的集合间映射。不过，这个嵌入却不是全性的。

练习：证明这个嵌入不是全性的。

证明：我们只要找到两个自态射 $X\stackrel{\alpha }{\to }X,Y\stackrel{\beta }{\to }Y$ 满足 $f_D\circ \alpha =\beta \circ f_A$ 但 $f_A\ne f_D$。我们只要取 $X$ 上的两个不同自态射 $\alpha \ne \beta$（这很好构造），令 $f_D=\beta ,f_A=\alpha$ 即可。

因为该嵌入没有全性，这意味着被 ${\mathcal{S}}^{\cdot \to \cdot }$-映射保持的结构比被 ${\mathcal{S}}^{\circlearrowright }$-映射保持的结构要松散的多。 因此，如果我们把自同态仅仅视为一个态射的话，我们就失去了其丰富的细节，而只能沦于回答一些更简单的问题：集合中有多少点，其中每种不同大小的 $\alpha$-堆叠的个数有多少？

8、自反图

最后一个例子是自反图：它们可以被视为包含第三个结构映射的图。

其中源映射和汇映射都是收缩，即它们存在一个共同的截面映射 $i$ 。该截面映射的意义是把一个点映射到它所属的箭头，而且特别的这个箭头是自反的，因为对于 $i(p)$ 而言它的源节点和汇节点都是 $p$。这也就是说每个节点 $p$ 都有一个指向自身的箭头，在这个意义上我们把该图称为自反图。（注意前面的非自反图并不意味着它没有自反箭头，只是不一定每个节点都有自反箭头）。

练习：证明在一个自反图中，箭头集合上的两个自反态射 $e_1=is,e_0=it$ 不但是幂等的，还满足下列四个方程 $e_k{e}_j=e_j,fork,j=0,1$.

解答：

幂等性： $e_1{e}_1=(is)(is)=i(si)s=i{1}_{P}s=is,e_0{e}_0=(it)(it)=i(ti)t=i{1}_{P}t=it$。

方程条件：

$e_0{e}_0=(it)(it)=i(ti)t=i{1}_{P}t=it=e_0$

$e_0{e}_1=(it)(is)=i(ti)s=i{1}_{P}s=is=e_1$

$e_1{e}_0=(is)(it)=i(si)t=i{1}_{P}t=it=e_0$

$e_1{e}_1=(is)(is)=i(si)s=i{1}_{P}s=is=e_1$

既然自反图范畴在图范畴的基础上还要保持 $i$ 的结构，那么自反图范畴中的映射应该满足更多的限制条件。

练习：证明若 $f_A,f_D$ 是 $\mathcal{S}$ 上自反图的映射，则 $f_D$ 由 $f_A$ 与两个图的内部结构决定。

解答：自然，我们要求如下交换图成立。

特别的除图范畴映射中的约束，还有 $f_{A}i=i^{\prime }{f}_D$。结合 $s^{\prime }{f}_A=f_{D}s,si=1_P$ 可知 $f_D=s^{\prime }{f}_{A}i$，类似的可以证明 $f_D=t^{\prime }{f}_{A}i$。

练习：考虑一个涉及两个集合和四个映射的结构

例如 $M$ 表示男人， $F$ 表示女人， $\varphi ,{\varphi }^{\prime }$ 表示父亲， $\mu ,{\mu }^{\prime }$ 表示母亲。设计一个合理的映射定义，使得该结构构成一个范畴。

要求映射满足下面交换图即可

9、关于以上例子及其普遍意义的总结

上图中 $I$ 是全性嵌入（insertion）函子， $J$ 是非全嵌入函子， $U,V$ 不是嵌入函子，而是遗忘（forgetful）函子。嵌入和遗忘函子的区别在于：前者把源范畴中的结构视为目标范畴中的特例，后者则在忽视、遗忘源范畴中的某些结构后变成目标范畴。

在所有例子中，所涉及的一般“结构”类型都可以得到更精确的描述。每个例子都涉及一个内聚的 cohesive 或活动的 active 集合的范畴 category（种类 species 或模式 mode）。与内聚性 internal cohesion 或内部运动 internal motion 为零的抽象集合 $\mathcal{S}$ 不同，这些“集合”具有内部粘连 internally sticking、内部运动 internally moving 的特定方式，而这些类别中的映射允许在不撕裂 tearing 或打断 interrupting 它们的情况下对对象进行比较和研究。通过应用指定的遗忘函子，我们还可以研究在一定范围内撕裂或中断它们的情况下这些对象的性质。

这里 cohesive-cohesion-stick-tear 是从静力学的角度描述这种内部结构，而 active-motion-move-interrupt 则是从动力学的角度描述这种内部结构。

同时我们也更好的理解了前文不断提到的所谓 “抽象集合”的概念的具体意思，这里的“抽象”指的是那种没有任何内部结构的集合。

10、收缩和单射性

什么时候映射有收缩？一个重要的必要条件是它是单射。（我们在上文证明过）

对抽象集合范畴 $\mathcal{S}$ 而言，这个必要条件几乎（除 $X$ 是空集以外）也是充分的（即逆命题也为真）。单射。但是这个逆命题对大多数的范畴都不成立。例如不动点定理告诉我们在连续映射范畴中， 圆 $C$ 到圆盘的嵌入 $D$ 是单射，但却不存在收缩。 任何 $\mathcal{S}$-收缩都会撕裂圆盘的结构，也就是说不存在连续的 $\mathcal{S}$-收缩。

现在我们考虑在 ${\mathcal{S}}^{\circlearrowright }$ 内部的一个相同现象。考虑下面的例子，

其中方框内分别是 $X^{\circlearrowright \alpha },Y^{\circlearrowright \beta }$ 的内部表示，且 $ax=y,a0=0$。

练习：

1. 证明 $a$ 是自态射范畴的映射。
2. 证明 $a$ 是单射。
3. 证明 $a$ 作为一个 $\mathcal{S}$-映射，恰好有两个收缩 $p$。
4. 证明 3 中的两个收缩映射都不是 ${\mathcal{S}}^{\circlearrowright }$-映射，因此 $a$ 在 ${\mathcal{S}}^{\circlearrowright }$ 中没有收缩。
5. 在所有 8 个 $\mathcal{S}$-映射 $Y\to X$ 中，有多少是 ${\mathcal{S}}^{\circlearrowright }$-映射？
6. 证明即使把 $a$ 视为更大的范畴 ${\mathcal{S}}^{\cdot \to \cdot }$ 中的态射（经过第 7 节中的函子 $J$ 嵌入），它也没有收缩。

证明：

1. 证明 $a\circ \alpha =\beta \circ a$ 即可。 $a\alpha x=a0=0=\beta y=\beta ax,a\alpha 0=a0=0=\beta 0=\beta a0$。

2. 显然。

3. 为使得 $Y\stackrel{p}{\to }X$ 满足 $p\circ a=1_X$，至少 $p\circ ax=x,p\circ a0=0$，因此 $p(y)=x,p(0)=0$。最后 $p(\overline{y})$ 只有两种选择要么为 $x$，要么为 $0$，我们记前者为 $p_1$，后者为 $p_2$。

4. 验证 $p$ 是否满足 $p\circ \beta =\alpha \circ p$。 $p\beta \overline{y}=py=x,\alpha p\overline{y}=\alpha x\text{ or }\alpha 0\equiv 0$，因此不满足。

5. 首先这样的集合映射确实有 $|X{|}^{|Y|}=2^3=8$ 个。取值表罗列如下：

   $p(0)$	0	x	0	0	x	x	0	x
   $p(y)$	0	0	x	0	x	0	x	x
   $p(\overline{y})$	0	0	0	x	0	x	x	x

   4 中证明了第 3、7 列的映射不在自态射范畴中。写一个小脚本代替我们验证这件事

   from itertools import product
   
   X = ["0", "x"]
   Y = ["0", "y", "y_bar"]
   alpha = {"x": "0", "0": "0"}
   beta = {"y_bar": "y", "y": "0", "0": "0"}
   
   p = {}
   all_p = []
   
   for values in product(X, X, X):
       for y, v in zip(Y, values):
           p[y] = v
       all_p.append(p.copy())
   
   print(all_p)
   
   for p in all_p:
       trues = [alpha[p[y]] == p[beta[y]] for y in Y]
       if all(trues):
           print(p)

   最后知道只有第 1、4 列的函数符合要求。

6. 验证 $p$ 是否满足 ${\mathcal{S}}^{\cdot \to \cdot }$-映射的条件。即 $f\circ \beta =\alpha \circ g$，然而由自态射范畴的嵌入方式可知， $f=g=p$，所以归根结底还是要验证 $p\circ \beta =\alpha \circ p$ 是否满足，这与 4 相同，故在 ${\mathcal{S}}^{\cdot \to \cdot }$ 中仍然没有收缩。

练习：证明对任意两个图和它们之间的任意图范畴映射

$f_D\circ s=f_D\circ t$ 成立当且仅当 $f_A$ 把 $X$ 中的所有箭头映射为 $Y$ 中的环 loop 。

证明：所谓 $Y$ 中的环 $y$ 满足 $s^{\prime }(y)=t^{\prime }(y)$。翻译一下后半子句就是 $\mathrm{\forall }x\in X,s^{\prime }{f}_A(x)=t^{\prime }{f}_A(x)$，也就是 $s^{\prime }\circ f_A=t^{\prime }\circ f_A$。总之要证明 $f_D\circ s=f_D\circ t\iff s^{\prime }\circ f_A=t^{\prime }\circ f_A$。由 $f_{D}s=s^{\prime }{f}_A,f_{D}t=t^{\prime }{f}_A$ 知，显然。

再看一个例子。 ${\mathbb{Z}}^{\circlearrowright 5\times ()}$ 是整数集配上自态射 $x\mapsto 5x$，这个自态射不是自同构，因为整数集上没有分数，因此该自态射没有逆映射。但如果我们放到有理数集上考察就成立了。

练习：存在一个集合范畴上的嵌入映射 $\mathbb{Z}\stackrel{f}{\to }\mathbb{Q}$ 使得

1. ${\mathbb{Z}}^{\circlearrowright 5\times ()}\stackrel{f}{\to }{\mathbb{Q}}^{\circlearrowright 5\times ()}$ 是自态射范畴上的映射。
2. ${\mathbb{Q}}^{\circlearrowright 5\times ()}$是自同构。
3. $f$ 是单射。

解答： 考虑 $f:x\mapsto x$ 即可。均显然。

练习：考虑幂等映射

令 $Y^{\circlearrowright \beta }$ 是任意自同构。证明任意 ${\mathcal{S}}^{\circlearrowright }$-映射 $X^{\circlearrowright \alpha }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$ 一定是非单射的，即它一定将 $X$ 中的两个元素都映射到 $Y$ 中的同一个不动点。

证明：任何这样的 $f$ 需要满足 $f\alpha =\beta f$，而 $\beta$ 是自同构，因此 ${\beta }^{-1}f\alpha =f$。若我们记 $X=\{a,b\}$，其中 $\alpha (a)=b,\alpha (b)=b$。因此 $f(a)={\beta }^{-1}f\alpha (a)={\beta }^{-1}f(b),f(b)={\beta }^{-1}f\alpha (b)={\beta }^{-1}f(b)$，于是 $f(a)=f(b)$。特别的由后一个式子可知 $\beta f(b)=f(b)$，即 $f(b)$ 是 $\beta$ 的不动点。

练习：若 ${\mathcal{S}}^{\circlearrowright }$ 上的对象 $X^{\circlearrowright \alpha }$ 有一个 ${\mathcal{S}}^{\circlearrowright }$-单射 $f$ 到对象 $Y^{\circlearrowright \beta }$，且 $\beta$ 是自同构，那么 $\alpha$ 必须是单射。

该练习是前一个练习的一般形式。

证明：反证法，假设 $\alpha$ 不是单射。那么 $\mathrm{\exists }{x}_1,x_2,x_1\ne x_2,\text{s.t. }\alpha (x_1)=\alpha (x_2)$。由于 $f\alpha =\beta f$，且 $\beta$ 是自同构，因此 $f(x_1)={\beta }^{-1}f\alpha (x_1)={\beta }^{-1}f\alpha (x_2)=f(x_2)$，矛盾。

11、结构的种类

带有结构的对象有以下要素：

1. 每个对象对应着一个结构的实例，每个对象由一些名称表示而每个名称对应着这个结构的某个组成部分。
2. 每个结构映射（注意不要和对象间的映射搞混）也由一些名称表示而每个名称对应着这种保持这个结构的某个组成部分的映射。
3. 每个保持结构中的某个组成部分的映射的定义域和陪域所对应的结构的某个组成部分也由一些名称指定。

这一大段表达不清，我梳理大意重新表达了一遍。

套入具体的例子这段话的意思会更加清晰：例如对于图范畴而言，它的结构包含节点和箭头。因此每个图对象都有两个组成部分（节点集合和箭头集合），相应的结构映射分别是源映射 $s$与汇映射 $t$，同时源映射与汇映射的定义域和陪域都分别是箭头集合和节点集合。对离散动力系统范畴而言（也就是自态射范畴），它只有一个组成部分“状态”，还有一个结构映射”动力“。此外结构的抽象规定本身，也就是上面那段话也可以被视为一个图范畴，详见第十七讲。

我们必须分清楚对象的组成部分和对象、结构映射与对象之间的映射的区别。对象的组成部分和结构映射都是对象内的要素，是（内部）结构。内部结构为空的抽象集合范畴中的对象是没有这些要素的。

现在，我们可以效仿上面那些带有具体结构的范畴来定义带有抽象结构的范畴，其格式是一样的。假设 $X,Y$ 是两个结构范畴的对象，由集合建模。那么对结构中每个组分的名称 $A$，存在相应的集合 $X(A),Y(A)$ 分别对应 $X$ 和 $Y$ 上的 $A$-组分。每个结构对象间的映射 $X\stackrel{f}{\to }Y$ 由所有组分映射 $X_A\stackrel{f_A}{\to }{Y}_A$ 构成。同时这些映射必须保持结构，也就是说保持组分间的结构映射，所谓结构映射就是同一结构内不同组分间的映射 ${\alpha }_X:X(A)\to X(B)$， $X(A),X(B)$ 分别是结构映射 ${\alpha }_X$ 的定义域和陪域。而结构映射反映的是组分之间的相互关系，它们必须被结构间的映射所保持，即在集合范畴中满足交换图：

该交换图对任意 $A,B,\alpha$ 成立。比方说在图结构中， $A$ 为箭头，$B$ 为节点， $\alpha$ 可以取 $s,t$。上述的交换图我们记作 $f$ 保持 $\alpha$。因此一个结构范畴 category of structures 映射的组分 component maps 数目与其对象中的组分 component-object 名称数目相同，而每个组分本身就是一个集合范畴中的对象所建模的。

除了抽象结构范畴之外还有更多的范畴，不过它们都可以被认为是抽象结构范畴的完整子范畴，因此映射的概念并不改变。这些完整子范畴通过对构成对象的图施加限制条件来确定，最简单的一种条件就是结构映射必须满足的复合律。例如，一个动力系统可能被要求是一个对合系统（即动力映射是对合映射），或者一个图被要求是自反的，因此环结构需要被专门规定，即要求源映射和汇映射都必须是节点集合上的恒等映射。

一个抽象结构常常从下面的特例中出现。设 $\mathcal{A}$ 是某个范畴 $\mathcal{X}$ 中的一小族对象和映射，其中 $\mathcal{A}$ 中的映射的定义域和陪域也都在 $\mathcal{A}$ 中。~~在 $\mathcal{A}$ 中的每个对象 $A$ 被视为 $A$-形图，每个映射 $\alpha$ 被视为结构映射 ${\alpha }^{\ast }$，其中 ${\alpha }^{\ast }$ 的陪域是 $\alpha$ 的定义域， ${\alpha }^{\ast }$的定义域是 $\alpha$ 的陪域。~~由此对每个范畴 $\mathcal{X}$ 中的对象 $X$ 都可以构造一个 $\mathcal{A}$-结构，其中它的第 $A$ 个分量集合（按照上面的写法记为 $X(A)$ 是所有 $\mathcal{X}$-映射 $A\stackrel{x}{\to }X$的集合，且对于每个 $B\stackrel{\alpha }{\to }A$ 结构映射 ${\alpha }^{\ast }$ 满足 ${\alpha }_X^{\ast }(x)=x\circ \alpha$。

原文中每个映射 $\alpha$ 被视为结构映射 ${\alpha }^{\ast }$，其中 ${\alpha }^{\ast }$ 的陪域是 $\alpha$ 的定义域， ${\alpha }^{\ast }$的定义域是 $\alpha$ 的陪域。这句话我感觉有问题，因为如果这里的 ${\alpha }^{\ast }$ 指的是 ${\alpha }_X^{\ast }$，那么显然不对：因为 ${\alpha }_X^{\ast }$ 是把一个映射 $A\stackrel{x}{\to }X$ 映射为另一个映射 $B\stackrel{x\circ \alpha }{\to }X$，而 $\alpha$ 是把 $B$ 中的元素映射到 $A$ 中的元素，而映射的集合和集合并不相等。

练习：根据结合律，每个 $\mathcal{X}$-映射 $X\stackrel{f}{\to }Y$ 产生一个 $A$-结构范畴中的映射。

解答：对任意对象 $X$ 上 $A$-分量集合 $X(A)$ 中的元素 $A\stackrel{x}{\to }X$， $A\stackrel{f\circ x}{\to }Y$ 是对象 $Y$上的 $A$-分量集合 $Y(A)$ 中的元素。那么 $f:X\to Y$ 诱导出 $f_A:X(A)\to Y(A),x\mapsto f\circ x$ 以及 $f_B:X(B)\to Y(B),x\mapsto f\circ x$。 由结构映射定义知 ${\alpha }_X^{\ast }:x\mapsto x\circ \alpha$，因此考虑 $B\stackrel{\alpha }{\to }A\stackrel{x}{\to }X\stackrel{f}{\to }Y$，对任意 $x\in X(A)$， $f_B\circ {\alpha }_X^{\ast }(x)=f\circ (x\circ \alpha )=(f\circ x)\circ \alpha ={\alpha }_Y^{\ast }\circ f_A(x)$。

注意 ${\alpha }_X^{\ast }$ 与 ${\alpha }_Y^{\ast }$ 定义是相同的，唯一的区别就是 $x\mapsto x\circ \alpha$ 中一个 $x:A\to X$，另一个是 $x:A\to Y$。

例如，图结构就可以由下面的 $\mathcal{A}$ 导出

因为对任意图 $X$，$X$ 中的箭头可以视为图映射 $A\stackrel{x}{\to }X$， $X$中的节点可以视为图映射 $D\to X$ 而 $x$ 的源映射为 $s_X^{\ast }(x)=x\circ s$，那么对任意图映射 $X\stackrel{f}{\to }Y$，结合律 $f(xs)=(fx)s$，在该范畴内部即 $f$ 保持源节点： $s_Y^{\ast }\circ f=f\circ s_X^{\ast }$。

这里 $\mathcal{X}$ 是图范畴，$\mathcal{A}$ 是由两个图和两个映射组成：两个图分别是 $D$ （只含一个节点，没有箭头）和 $A$（含两个节点，只有一个箭头）；两个映射分别是 $s$，将 $D$ 中的单点映射到 $A$ 中的（唯一那个）源节点，另一个是 $t$，将 $D$ 中单点映射到 $A$ 中的（唯一那个）汇节点。我们可以把 $D$ 和 $A$ 分别理解成两个最简单的图：一个是节点原型，一个是箭头原型。因此对任意图 $X$ 而言， $X$ 本身是其所有节点和箭头的集合，而这个所有节点和箭头的集合中的元素，恰恰都可以视为从 $D$ 或者 $A$ 出发的全部映射的集合——这个思想是与把任意 $x\in X$ 视为点映射 $1\stackrel{x}{\to }X$ 的思想一致的。

下面这一段没看懂。略。

12、导览

我们已经用一种共同的方法构建了几个有用的范畴示例，并开始探索这些范畴与集合范畴之间的相同或不同之处。第 11-18 课将对这些类别和其他类别进行深入讨论，第 17 课后还将进行一次抽测。

第十一讲、登堂入室：结构更丰富的范畴

1、自态射范畴

略。

至此，我想说的关于这个新范畴的例子就讲完了。结构范畴的例子还有很多，但要注意，这些结构都建立在无结构的集合上，这看起来像是个悖论。这实际上揭示了，虽然一个抽象的集合完全可以用一个数字来描述，但在映射的帮助下集合具有承载各种结构的能力。

2、两个子范畴：幂等范畴和自同构范畴

略

3、图范畴

略

练习：从 $X^{\circlearrowright \alpha }$ 到 $Y^{\circlearrowright \beta }$ 有多少自同构。

解答：3 个。我们先确定有多少自态射，首先注意到自态射的循环性，因此只要确定一个元素的像，由于保持映射性，剩下的两个像也自然确定了。其次验证它们都是自同构即可。

练习：证明从 $X^{\circlearrowright \alpha }$ 到 $Y^{\circlearrowright \beta }$ 不存在态射。

解答：记不在环中的那个元素为 $x$，由于 $Y$的自态射是循环的，因此 $\mathrm{\forall }y\in Y,{\beta }^4(y)=y$。然而若存在从 $X^{\circlearrowright \alpha }$ 到 $Y^{\circlearrowright \beta }$ 的态射 $f$，就意味着 $f{\alpha }^4(x)={\beta }^{4}f(x)$。但显然 $f{\alpha }^4(x)=f\alpha (x)\ne f(x)={\beta }^{4}f(x)$。

练习： 若 $X^{\circlearrowright \alpha }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$ 是 ${\mathcal{S}}^{\circlearrowright }$ 中的映射，且若 $A\stackrel{f}{\to }B$ 作为集合映射有逆 $B\stackrel{f^{-1}}{\to }A$ 则 $f^{-1}$ 也自动是 ${\mathcal{S}}^{\circlearrowright }$ 的映射。

解答：作为集合映射的 $f$ 满足 $f\alpha =\beta f$，因此 $\alpha f^{-1}=f^{-1}\beta$，这就说明 $Y^{\circlearrowright \beta }\stackrel{f^{-1}}{\to }{X}^{\circlearrowright \alpha }$ 且 $f^{-1}$ 也是作为 ${\mathcal{S}}^{\circlearrowright }$ 中映射的逆。

结合上两个练习，我们可以知道如果两个自态射对象在集合范畴内同构，不一定在自态射范畴内同构，但如果二者在自态射范畴上的映射作为集合态射是同构，那么它作为自态射范畴上的态射也是同构。

练习： ${\mathbb{Z}}^{\circlearrowright ()+2}$ 与 ${\mathbb{Z}}^{\circlearrowright ()+3}$ 是否同构？

解答：不是。 ${\mathbb{Z}}^{\circlearrowright ()+2}$ 有两条链 $2\mathbb{Z},2\mathbb{Z}+1$， ${\mathbb{Z}}^{\circlearrowright ()+3}$ 有三条链 $3\mathbb{Z},3\mathbb{Z}+1,3\mathbb{Z}+2$。链与链之间无法通过自态射相交。假设存在这样的态射 $f$ ，根据态射的性质，同一链中的元素只能映射到同一链中：设 $x,y$ 是同一链中的元素，那么 $y-x=2n$ 即 $y=2n+x={\alpha }^n(x)$，因此 $f(y)=f{\alpha }^n(x)={\beta }^{n}f(x)⟹f(y)-f(x)=3n$。那么两条链至多映射到两条链，即后三者中总有一条链的原像为空，故无逆，即不是同构。

练习：将下面的图按同构两两配对。

解答：a-d, b-e, c-f。

练习：这两个图是否同构？

解答：是。把左图中间节点和右边节点交换位置，再把整幅图旋转 180 度即可。

练习：（不可能的旅途） $J$ 是图

$G$ 是任意图， $b,e$ 为其中两点。

1. 若 $G\stackrel{f}{\to }J$ 是图映射，满足 $fb=0,fe=1$，则 $G$ 中不存在从 $b$ 到 $e$ 的路径。
2. 反之，若 $G$ 中不存在从 $b$ 到 $e$ 的路径，则$G\stackrel{f}{\to }J$ 是图映射，满足 $fb=0,fe=1$。

解答：

必要性：反证法，假设存在从 $b$ 到 $e$ 的路径，即存在一系列箭头 $(l_0,l_1,\dots ,l_n)$，使得 $s(l_0)=b,t(l_n)=e,t(l_k)=s(l_{k+1}),\mathrm{\forall }k\in 0,\dots n-1$。由于 $f$ 是图映射，因此 $f(l_k)$ 也都是 $J$ 中的箭头，且 $f(s(l_0))=fb=0,f(t(l_n))=fe=1,t^{\prime }(f(l_k))=s^{\prime }(f(l_{k+1})),\mathrm{\forall }k\in 0,\dots n-1$。即它对应于 $J$中起点为 0 终点为 1 的路径。然而我们知道 $f(l_k)$ 作为 $J$ 中路径只有上面三种情况： 从 0 到 0，从 1 到 1，从 1 到 0。因为 $s^{\prime }(f(l_0))=f(s(l_0))=0$ 所以 $t^{\prime }(f(l_0))=0$。那么根据后面的一连串等式我们知道路径终点也只能为 0，这与终点为 1 矛盾。

充分性：把从 $b$ 出发的所有路径上所有节点映射到 0；把到 $e$ 点为止的所有路径上所有节点都映射到 1。由于不存在从 $b$ 到 $e$ 的路径，因此这两步操作所分配节点都不重合。把剩余的所有节点都映射为节点 1。

第十二讲、图示范畴 categories of diagrams

1、动力系统或自动机

练习：假设 $x^{\prime }={\alpha }^3(x)$， $X^{\circlearrowright \alpha }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$ 为 ${\mathcal{S}}^{\circlearrowright }$ 中映射， 令 $y=f(x),y^{\prime }={\beta }^3(y)$。证明 $f(x^{\prime })=y^{\prime }$。

解答： $f\circ \alpha =\beta \circ f⟹f\circ {\alpha }^3={\beta }^3\circ f⟹f(x^{\prime })=y^{\prime }$。

练习：对有限动力系统而言，所有状态最终会进入循环，即存在 $N$ 使得对任意 $x$， 都存在 $k$ 与 $n>N$， ${\alpha }^{n+k}(x)={\alpha }^n(x)$。

证明：设动力系统的状态数为 $M$，任取一个状态 $x$，考虑状态集合 $\{x,\alpha (x),\dots ,{\alpha }^{M-1}(x),{\alpha }^M(x)\}$，由于这个集合里有 $M+1$ 个状态，而取值只有 $M$ 种，因此由鸽笼原理必然存在 $0\le a<b\le M$，使得 ${\alpha }^a(x)={\alpha }^b(x)$，由此可知对任意 $t>0$ 都有 ${\alpha }^{a+t}(x)={\alpha }^{b+t}(x)$成立。 若取 $k(x)=b(x)-a(x),n=t+a(x)$即可 （这里 $(x)$ 意为与 $x$ 有关），那么如果我们取 $N=\underset{x}{max}\{a(x)\}$，就可知若 $n=t+N>N$，则必然存在 $k(x)$，使得 ${\alpha }^{n+k}(x)={\alpha }^n(x)$。

这里 $N$ 是一个充分大的演化时长，它对系统内所有状态而言是普遍的。而 $k(x)$ 则是 $x$ 在演化充分时长后所进入的那个循环的周期。

2、家族树

我们现在考虑配有两个自态射的集合构成的范畴，记为 ${\mathcal{S}}^{\circlearrowright \circlearrowleft }$。这个范畴中的对象可以用于建模人的家族树，其中每个元素是一个人，而两个自态射 $f,m$ 分别表示父亲和母亲。范畴映射 $g$ 需要保持这两个结构映射。但是并非其中每一个对象都对应着一个现实中的合理家族树，譬如某个对象中元素可能是 $f,m$ 的不动点，但现实中不存在自己是自己父亲或母亲的人。

练习：

1. 假设对象 $P$ 表示配有父母亲自态射的所有人类的集合。证明性别是范畴 ${\mathcal{S}}^{\circlearrowright \circlearrowleft }$ 中从 $P$ 到对象 $G$ 的映射

   

2. 在某个社会，所有人都被分为狼族和熊族两个氏族。同族结婚被禁止。一个孩子的氏族与继承于母亲。证明把人分为氏族的映射是范畴 ${\mathcal{S}}^{\circlearrowright \circlearrowleft }$ 中从 $P$ 到下面对象的映射

   

3. 为下面这个集合构造一个合适的父亲、母亲映射，使得它是 ${\mathcal{S}}^{\circlearrowright \circlearrowleft }$ 中的对象且氏族和性别映射可以被整合为一个映射 $P\to G\times C$。尽管我们尚未定义范畴中对象的乘法，但我们后面会看到 $G\times C$ 确实是二者的积。

解答：

1. 我们只需证明它保持映射即可。即对任意 $x\in P$， $g\circ m(x)=m\circ g(x),g\circ f(x)=f\circ g(x)$ 。前半子句：因为母亲的性别一定为女，即对任意 $x\in P,g\circ m(x)=female$，同理在 $G$ 中无论男性还是女性的母亲都被映射为女性即对任意 $y\in G,m(y)=female$，因此 $g\circ m(x)=female=m\circ g(x)$。同理可证父亲的结构也被保持。

2. 按照氏族母系继承规则可知，狼族的母亲是狼族，熊族的母亲是熊族。又根据同族不婚配的原则，如果母亲是狼族那么父亲一定是熊族，母亲是熊族则父亲一定是狼族。这就是 $C$ 的情况。

3. 如下

   

3、重访动力系统

前面我们所有的构造都基于集合范畴 $\mathcal{S}$，事实上我们可以对任意范畴 $\mathcal{C}$ 如法炮制，构造自态射范畴 ${\mathcal{C}}^{\circlearrowright }$：其对象是配有 $\mathcal{C}$-自态射的 $\mathcal{C}$-对象，其映射 $f$ 首先是 $\mathcal{C}$-映射且满足 $f\circ \alpha =\beta \circ f$， $\alpha ,\beta$ 分别是对象上的 $\mathcal{C}$-自态射。规定 ${\mathcal{C}}^{\circlearrowright }$-映射的复合是 $\mathcal{C}$-映射的复合， ${\mathcal{C}}^{\circlearrowright }$ 上的恒等映射是 $\mathcal{C}$ 上的恒等映射。为证明它确实满足范畴的条件，需要验证

1. ${\mathcal{C}}^{\circlearrowright }$-映射的复合确实是 ${\mathcal{C}}^{\circlearrowright }$-映射
2. ${\mathcal{C}}^{\circlearrowright }$ 上的恒等映射确实是 $\mathcal{C}$ 上的恒等映射

但这两个条件都可由 $\mathcal{C}$-映射的性质外加结构保持律直接推出。

类似的我们可以构造包含链中的这些范畴

注意我们的构造与在集合范畴上的情形完全一致，唯一的区别在于这里的底范畴 $\mathcal{C}$ 是任意的，比如 $\mathcal{C}$ 可以取 $\mathcal{S}$ 也可以取 ${\mathcal{S}}^{\circlearrowright }$。

第十三讲、单元范畴 Monoids

Monoids 常常被翻译为幺半群，但是既然我们讨论的语境是范畴论而非抽象代数，用单元范畴这个翻译更为妥当。

一般来说，为了完整地刻画一个范畴，我必须说明对象是什么，映射是什么，每个映射的定义域是什么对象，每个映射的陪域是什么对象，每个对象的恒等映射是什么，任意两个可复合的映射的复合映射是什么这六件事。当然，还有它们必须满足的法则：簿记律（映射可复合的条件与复合后的定义域和陪域）、结合律、恒同律。

下面是一个特例。假设我们的范畴中只有一个对象，我们称之为 $\ast$。这意味着该范畴中的所有映射都是这个唯一对象的自态射。然而，这个范畴中可能有很多映射。假设我用所有的自然数来索引这些映射：因此我们可以写成 $\ast \stackrel{0}{\to }\ast ,\ast \stackrel{1}{\to }\ast ,\ast \stackrel{2}{\to }\ast$ 等等。

在这个范畴中我们应该如何定义复合呢？有许多可能方式，不过我们选取的是数的乘法，换言之，定义任意两个映射的复合为这两个数的乘积，即 $n\circ m=n\times m$。因为这里只有一个对象，簿记律总是自动满足。

现在，我们必须指定唯一对象 $\ast$ 的恒同映射。我们应该规定哪个数字为 $1_{\ast }$？它应该满足 $\mathrm{\forall }n\in \mathbb{N},1_{\ast }\circ n=n,n\circ 1_{\ast }=n$，由我们对映射复合的定义，这意味着 $1_{\ast }=1$。

这个特殊的范畴我们称为单元范畴 monoid。

它在范畴论中的地位类似于单元集在集合论中的地位。我们把那个唯一的对象也称为单元对象。

单元范畴中的单元对象似乎没有任何特征。然而，任何范畴都可以用集合范畴来解释，从而使对象有一定的生命。我们把上面定义的范畴称为 $\mathcal{M}$，表示乘法单元范畴。我们把一种解释记为一个范畴之间的映射： $\mathcal{M}\stackrel{f}{\to }\mathcal{S}$。其中一种解释是映射 $f$ 把唯一的单元对象映射为全体自然数集 $\ast \mapsto \mathbb{N}$，把每个映射 $n$（即一个自然数）映射为自然数集上的自态射 $\mathbb{N}\stackrel{f_n}{\to }\mathbb{N},f_n(x)=n\times x$， $f:n\mapsto f_n$。因此任何两个自态射的复合 $(f_n\circ f_m)(x)=f_n(f_m(x))=n\times (m\times x)=(n\times m)\times x=(nm)\times x=f_{nm}(x)$，即 $f_n\circ f_m=f_{nm}$ ，$f$ 保持态射的复合。而同时 $f(1)=1_{\mathbb{N}}$，即 $f$ 把单元范畴的恒等映射映射为自然数集的恒等映射。我们把这种保持范畴结构（对象、映射、恒等映射、复合映射、簿记律、结合律、恒同律）的范畴之间的映射称为函子 functor。

这样的函子还启发我们可以在何种意义上使用“负一次幂”的符号作为“逆”推广。如果我们稍微改变一下例子，用有理数代替自然数作为 $\mathcal{M}$ 的映射，我们就会发现 $(f_3{)}^{-1}=f_{(3^{-1})}$。

我们再构造另一个单元范畴的例子称为 $\mathcal{N}$。有唯一一个单元对象 $\ast$，映射也仍旧用数字表示，但映射的复合不再是乘法而是加法，此时单元对象的恒等映射是 $0$ 而不是 $1$。给出一个 $\mathcal{N}\to \mathcal{S}$ 的函子意味着我们要把 $\ast$ 解释为某个集合 $S$，每个映射 $\ast \stackrel{n}{\to }\ast$ 解释为 $S\stackrel{g_n}{\to }S$，使得 $g_0=1_S,g_n\circ g_m=g_{n+m}$。我们取 $S=\mathbb{N}$ 并定义 $g_n(x)=n+x$ 就可以满足上述条件。

上面两种函子是把单元范畴解释为集合范畴的标准案例，其中单元对象被解释为单元对象上的映射的集合。通过这种方法我们得到了从任何单元范畴到集合范畴上的标准函子 standard functor 。

这里“把单元对象解释为单元对象上的映射的集合”，根本就是“人是一切社会关系的总和”的范畴论翻版。

除了标准函子以外， $\mathcal{N}$ 上还有许多其他函子。例如我们考虑一个配有自映射 $\alpha$ 的集合 $X$。函子 $h$ 把 $\ast$ 解释为集合 $X$，把映射 $n$ 解释为 ${\alpha }^n$，把 $0$ 映射为 $X$ 上的恒等映射 $1_X$ 。由此我们可知 $h(n+m)=h(n)\circ h(m)$。

这个函子相当于一个指数映射。只不过底是一个自映射 $\alpha$，指数是 $\alpha$ 自复合的阶次。

这样，从任意一个配有自映射的集合出发，我们都可以得到一个 $\mathcal{N}$ 到集合范畴的解释（函子）。因此我们可以把 ${\mathcal{S}}^{\circlearrowright }$ 记作 ${\mathcal{S}}^{\mathcal{N}}$，以提示我们其中的一个对象是从 $\mathcal{N}$ 到 $\mathcal{S}$ 的函子。

这种符号的写法是因为 $Y^X$ 常用来表示所有 $X\to Y$ 映射的集合，其中每个元素都是 $X\to Y$ 的映射。

我们称其为离散时间动力系统范畴。一个离散时间动力系统（对象）就是一个从单元范畴 $\mathcal{N}$ 到集合范畴的函子。那么连续时间动力系统呢？那么我们就需要把所有实数视为单元对象上的映射以构造单元范 $\mathcal{R}$，这样给定一个从 $\mathcal{R}$ 到集合范畴上的函子，意味着为每个实数 $t$ 分配一个集合 $X$ 和自态射 $X^{\circlearrowright {\alpha }_t}$。为了保持复合性，我们需要保证 ${\alpha }_0=1_X,{\alpha }_{s+t}={\alpha }_s\circ {\alpha }_t$。我们可以把集合 $X$ 视为物理系统连续状态的集合，如果 $x$ 是它此时的状态，那么 ${\alpha }_t(x)$ 就是它演化 $t$ 时间后的状态。

第十四讲、保持积极性质的映射

以下是一些关于自态射范畴中映射含义的练习。这些练习的目的是说明在集合范畴中的交换条件 $f\circ \alpha =\beta \circ f$ 确实是动力系统映射的恰当定义。假设以下练习中的 $f,\alpha ,\beta$ 都满足该条件。若无特殊声明，均默认下面出现的 $y$ 是 $x$ 在 $f$ 下的像。

对于容易的练习，我们省略解答仅给出见解。

练习：若在 $X$ 中 $\alpha (x_1)=\alpha (x_2)$，则在 $Y$ 中 $\beta (y_1)=\beta (y_2)$。

即 $f$ 保持原像性， $f(a)=b⟹f({\alpha }^{-1}(\{a\}))={\beta }^{-1}(\{b\})$。

练习：若 $x_2={\alpha }^5(x_1)$，则 $y_2={\beta }^5(y_1)$。

即 $f$ 保持轨道距离/演化时长。

练习：若 $\alpha (x)=x$ 则 $\beta (y)=y$。

即 $f$ 保持不动点。

练习：给一个反例要求 $x$ 不是 $\alpha$-不动点但 $y$ 是 $\beta$-不动点。

解答：考虑 $X=\{0,1\},\alpha (0)=1,\alpha (1)=0,Y=\{0\},\beta (0)=0,f(0)=f(1)=0$。

这说明 $f$ 只是保持结构，但并不反射结构，也就是说对于定义域中有的结构，在陪域中被保持，但在定义域中没有的结构并不会排除在陪域中有。

练习：证明若 ${\alpha }^4(x)=x$ 则 ${\beta }^4(y)=y$。但举一例使得 ${\alpha }^4(x)=x,{\alpha }^2(x)\ne x$，但 ${\beta }^2(y)=y,\beta (y)\ne y$。

解答：考虑 $X=\{1,-1,i,-i\},Y=\{1,-1\},\alpha (x)=i\times x,\beta (y)=-1\times y,y=f(x)=x^2$。

这表明若 $f$ 保持在环中的结构，则环的大小可能变小。

1、积极性质与消极性质 Positive properties versus negative properties

$X^{\circlearrowright \alpha }$ 中的元素 $x$ 的一个性质是能被 $\alpha$ 取值。这意味着存在一个元素 $\overline{x}$ 使得 $x=\alpha (\overline{x})$。该性质可以称为可达性。例如在下面这个系统中，

$x,z$ 是可达的，但 $y$ 不是。我们说可达性被 ${\mathcal{S}}^{\circlearrowright }$-映射保持，即若 $x$ 是 $\alpha$-可达，则 $y$ 是 $\beta$-可达。

可达性是积极性质的一个例子。消极性质的例子比如 $x$ 不是不动点，即 $\alpha (x)\ne x$。我们之所以把它称作积极性质与消极性质，是因为在范畴映射下，积极性质被保持而消极性质被反射，也就是说若定义域对象有积极性质，那么陪域对象也有积极性质；若陪域对象有消极性质，那么定义域对象也有消极性质。

这两个性质是对偶的。如果 $p$ 是某种积极性质，那么 $\mathrm{\neg }p$ 是对应的消极性质。积极性质被保持与消极性质被反射是互为逆否命题的关系。

第十五讲、动力系统性质的对象化

1、从环到另一个自态射的结构保持映射

设自态射范畴对象 $X^{\circlearrowright \alpha },Y^{\circlearrowright \beta }$ 如下

我们希望找到映射 $X^{\circlearrowright \alpha }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$ 。通过一段小程序，我们可以从总共 $|Y{|}^{|X|}=3^4=81$ 个集合映射的备选项中搜索保持结构的映射。

from itertools import product

X = ["0", "1", "2", "3"]
Y = ["y", "z", "w"]

f = {}

all_f = []
for values in product(Y, Y, Y, Y):
    for x, v in zip(X, values):
        f[x] = v
    all_f.append(f.copy())
all_f
for f in all_f:
    trues = [beta[f[x]] == f[alpha[x]] for x in X]
    if all(trues):
        print(f)

最终这样的映射只有两个

$x$	$f_1(x)$	$f_2(x)$
0	y	z
1	z	y
2	y	z
3	z	y

一般来说没有通用规则可以告诉两个自态射集合之间有多少结构保留映射。但在一些特殊情形，我们可以数出这个数目。例如上面这个例子， $X$ 的结构完全被 $0$ 元素所刻画（因为所有其他元素都可以由 $0$ 生成），因此如果 $f$ 保持结构，那么它完全被 $f(0)$ 的取值所刻画。而 $0$ 在 $X$ 中 $\alpha$-最小正周期为 4，因此 $f(0)$ 也必须在 $Y$ 中 $\beta$-周期为 4，在任意给定的 $Y$ 中这样的可能性并不多：它只可能是最小正周期为 $1,2,4$ 的元素。如果我们记 $N_l$ 为轨道长度为 $l$ 的轨道数目，那么在 $Y$ 中周期为 4 的元素分别有 $N_1+2N_2+4N_4$ 个。

最小正周期为 $d$ 的元素数目有 $d{N}_d$ 个，因为每个 $d$-轨道中的 $d$ 个元素的最小正周期都为 $d$。

2、用映射命名具有给定周期的元素

我们定义 $n$-环为配有如下自映射的 $n$-元集合。

注意这里的元素只是形式上写成自然数，但它可以是任何名字。

$n$-环的基本性质是每个结构保持映射 $C_n\to Y$ 命名了 $f(0)$，从而每个这样的映射与 $Y^{\circlearrowright \beta }$ 中的周期为 $n$ 的元素一一对应。特别的 $C_1\to Y^{\circlearrowright \beta }$ 对应着 $Y$ 上的 $\beta$-不动点。

回忆以下这里的命名 naming，就是第六讲中的含义。

练习：证明若一个元素有周期 5 和周期 7，那么它一定是不动点。

这个练习有一个更强的版本，如果元素有两个周期 $a,b$，那么它也有周期 $gcd(a,b)$。证明采用欧几里得辗转相除法。略过。

3、命名任意元素

我们是否能找到一个 $X^{\circlearrowright \alpha }$ 使得从它到任意其他 $Y^{\circlearrowright \beta }$ 的映射可以命名其中的所有元素？

也就是说是否其中的每个元素都可以被命名，也就是被“表示”。反过来，是否存在不可命名的东西？这里的关键在于这个 $X^{\circlearrowright \alpha }$ 是普遍的，即它可以命名任意 $Y^{\circlearrowright \beta }$ ，否则对每个 $Y^{\circlearrowright \beta }$ 我们至少可以用它自己来命名自己。

若存在这样的 $X^{\circlearrowright \alpha }$ ，它至少存在一个元素没有任何积极性质，否则它在结构保持映射下的像就必然有相同的积极性质——这就排除了它的任意性。特别的，这个元素不能有任何周期，也即它不能在一个环中。例如下面这个自映射中的 $x$

然而这个元素也还有一个性质即“三步以后进入环”。是否可能找到一个排除任何具体积极性质的元素呢？为此，我们至少要取消自态射含环的可能性，因此这样的自态射只可能包含无穷长的链条，例如自然数集上的加法自态射。

这里， $0$ 元素没有任何积极性质，并且我们还可以证明 ${\mathcal{S}}^{\circlearrowright }$ 中从 ${\mathbb{N}}^{\circlearrowright \sigma }$ 到 $Y^{\circlearrowright \beta }$ 的映射确实对应着 $Y$ 中任意一个元素。证明如下：

从映射 ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$ 中我们可以得到 $y=f(0)\in Y$。而因为 $f(n)={\beta }^{n}f(0)$，$f$ 在 $0$ 处的取值唯一决定了 $f$，不同的 $f(0)$ 对应着不同的 $f$，不同的 $f$ 也对应着不同的 $f(0)$。又因为对任意 $y\in Y$，我们总可以定义 $f$ 使得 $f(0)=y$（这里之所以总可以，就是因为 $0$ 元素没有任何积极性质）。

不过 $0$ 元素显然有一个消极性质，即它不是 $\sigma$-可达的，即不存在 $x\in X$，使得 $\sigma (x)=0$。

练习：证明若 $\overline{y}$ 有以下分解，其中 $N\stackrel{s}{\to }{C}_4$ 把 0 映射为 0，则 $\overline{y}(0)=y$ 的 $\beta$-周期为 4。

解答：记 $\overline{y}=r\circ s$，则 $y=\overline{y}(0)=r\circ s(0)=r(0)$，又因为 $r\circ \alpha =\beta \circ r$，可知 $r=r\circ {\alpha }^4={\beta }^4\circ r⟹y=r(0)={\beta }^4\circ r(0)={\beta }^4(y)$。

这个练习说明为了表述动力系统的性质，我们不需要诉诸任何 ${\mathcal{S}}^{\circlearrowright }$ 之外的东西。任何复杂的动力系统都可以用从简单对象 ${\mathbb{N}}^{\circlearrowright \sigma }$ 和 $C_n$ 出发的映射来探测。

练习：找到所有可能的映射 ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{f}{\to }{C}_n$。

解答：根据上面的性质，我们知道这样的映射总共有四个分别是，被它在 $0$ 点处的取值所决定 $f(0)=0,1,2,3$。

对任意 $Y^{\circlearrowright \beta }$ 我们找到两个集合映射

其中赋值映射 ${\alpha }_0(f)\dot{=}f(0)$，迭代映射 $f(n)={\beta }^{n}f(0)$。

命题 1：证明二者互逆。

证明：对任意 ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$，$f(0)=y\in Y$ 是它在 $0$ 点处的取值，因此它对应着映射 $1\to Y,1\mapsto f(0)$。反过来对任意映射 $1\to Y,1\mapsto y$， $y$ 都可以定义为 ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$ 在 $0$ 处的取值，并且把它按照迭代 $f(n)={\beta }^{n}f(0)$ 延拓到整个定义域上。

于是我们把 $Y$ 的信息在 ${\mathcal{S}}^{\circlearrowright }$ 内完全摄取出来。我们同样希望摄取 $\beta$ 的信息，下面两个练习展示了这一点。

练习：对任意动力系统 $X^{\circlearrowright \alpha }$，证明 $\alpha$ 本身也是 ${\mathcal{S}}^{\circlearrowright }$-映射 $X^{\circlearrowright \alpha }\stackrel{\alpha }{\to }{X}^{\circlearrowright \alpha }$。

解答：显然，本身它是集合映射，又满足复合律 $\alpha \circ \alpha =\alpha \circ \alpha$。

特别的， ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{\sigma }{\to }{\mathbb{N}}^{\circlearrowright \sigma }$ 是 ${\mathcal{S}}^{\circlearrowright }$-映射。

命题 2：证明若 ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{f}{\to }{Y}^{\circlearrowright \beta }$ 对应 $y$ （命题 1 中的同构），则 ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{f\circ \sigma }{\to }{Y}^{\circlearrowright \beta }$ 对应 $\beta (y)$。

证明：记 $g=f\circ \sigma$，则由命题 1 中的同构知 $g$ 对应 $g(0)=f\circ \sigma (0)=\beta \circ f(0)=\beta (y)$。

命题 1、2 告诉我们，任何一个动力系统总是被其初值与动力映射所决定，而该同构就记录下每一个动力系统的离散时间动力系统方程 ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{f}{\to }{S}^{\circlearrowright {\sigma }_S}$ ）。而一旦给定了该方程，那么系统在任意离散时刻 $n$ 的状态都可以由初值代入方程给出，即 $\mathrm{\forall }n\in \mathbb{N},{\sigma }_S^n\circ f=f\circ {\sigma }^n$。

这个等式的含义是，时间迭代与状态迭代的相互变换。 ${\sigma }_S^n\circ f(m)$ 是从初始状态 $f(m)$ 开始迭代 $n$ 步状态，而 $f\circ {\sigma }^n(m)$ 则是从初始时刻 $m$ 开始迭代 $n$ 步时间的状态。

1872 年 Felix Klein 提出这个方法用以考察某对象的全部自同构映射，当时它称为对称性 symmetries。的确，在晶体学和其他领域，研究对称性非常有用；但通过从若干标准对象的映射来 探测一个对象更加有用。在我们的动力系统中，这种作用来自于这样一个事实：虽然 $Y^{\circlearrowright \beta }$ 的对称性很贫瘠（极端情况下，只有恒等映射是唯一的自同构），但它总是有足够的从 ${\mathbb{N}}^{\circlearrowright \sigma }$ 出发的映射来完整地描述它。

4、自然数集 $N$ 的哲学角色 philosophical role

在第六讲中我们强调为研究包含所有抽象集合和映射的大范畴 $\mathcal{X}\mathcal{=}\mathcal{S}$，只需研究一个包含八个映射和两个对象的小范畴 $\mathcal{C}$ 就足够了，这是因为：

1. 映射 $1\to X$ 是 $X$ 中的所有点

2. 映射 $2\to X$ 是 $X$ 中的所有点对

3. 映射 $X\to 2$ 足以表示 $X$ 上所有布尔性质（也即该性质可以表达为一个命题在某点上或成立或不成立两种情况）

4. 用一个映射 $2\to 2$ 先复合（precomposing）3 中的映射交换了点对中两点的角色

   在复合方程 $\alpha \circ \beta$ 中，我们称用 $\beta$ 先复合（precomposing with $\beta$），因为它在映射链中先作用于对象。反之 $\alpha$ 称为后复合（following by $\alpha$）。

5. 用一个映射 $2\to 2$ 后复合（following）3 中的映射否定一个性质

6. 复合 $1\to X\to 2$ 记录 $\mathcal{C}$ 中一点是否具有某个特殊性质。

这里的八个映射是怎么数出来的？$1\to 1$ 一个， $1\to 2$ 两个， $2\to 1$ 一个， $2\to 2$ 四个。

回忆在第六讲中，研究一个复杂的客观范畴，选择一些较小的对象构成主观范畴，从主观对象到客观对象的映射是对客观对象中元素的列举 listing，而从客观对象到主观对象的映射则是研究了客观对象的属性。其实我对原文中所谓的客观范畴和主观范畴的命名并不赞同，更恰当的名字应该是”未知”范畴和”已知”范畴。而知本身不是绝对的，而是相对的，也就是说它是体现在用已知物表达未知物的关系中的，在这个表达关系中，用于表达的物处于已知地位，而被表达的物处于未知地位。

这些基本要素足以用于分析任意 $\mathcal{X}$-映射 $X\to Y$。若我们把三元集加入 $\mathcal{C}$，那么我们的主观知识就变得更为丰富了，至少对有限集合 $X$而言，此时我们可以描述用和、或等其他重要的逻辑运算来表述的性质。

这种方法适用于所有更深层次的客观范畴 $\mathcal{X}$，例如离散动力系统范畴。在对其中一些较简单的对象进行初步研究之后，我们可以明智地确定一个适当的子范畴，并将其作为我们进一步研究 大范畴中较复杂对象的主观工具 subjective instrument。

为说明提出的子范畴 $\mathcal{C}$ 是合适的，我们必须证明相应的定理。以离散动力系统范畴 ${\mathcal{S}}^{\circlearrowright }$ 为例，我们看到包含对象 ${\mathbb{N}}^{\circlearrowright }$ 的任何子范畴 $\mathcal{C}$ 都可以讨论任意离散动力系统 $S$ 上的状态，因为

1. 映射 $N\stackrel{y}{\to }S$ 是 $S$ 的状态
2. 用 $N\stackrel{\sigma }{\to }N$ 先复合的效果是取下一个状态的操作（即动力映射）

总之，离散动力系统中的状态和动力映射这两个要素都被刻画了，因此它就刻画了全部的离散动力系统。诸如“某状态是否在 7 步时间单位后回归”的问题，可以在我们将 $C_7$ 囊括进 $\mathcal{C}$ 范畴中得到回答，即在主观（范畴）中的对象化 objectified within the subjective。而“某状态是否在三步以后停止变化”则可以通过将下面的对象加入主观范畴被对象化：

映射 $X\to B$ 可能表达关于状态的重要性质。例如考虑下面的对象 $B$

若 $X^{\circlearrowright m}$ 表示社会的母系方面（即 $x$ 是古往今来的所有人，而 $m$ 则是母亲映射），那么性别映射 $X^{\circlearrowright m}\stackrel{g}{\to }B$ 是离散动力系统范畴中的映射。将对象 $B$ 纳入主观范畴，就可以将性别作为性质在主观范畴中对象化。

将

纳入主观范畴，就可以记录离散动力系统中的任何状态的稳定性，即每个状态在多少步以后进入稳定态。如果某个状态在离散动力系统范畴映射下被映射到 $\mathrm{\Omega }$ 中的有限数 $n$，则其在 $n$ 步后进入稳定态，如果被映射到 $\mathrm{\infty }$ 则永远不会进入稳定态。这个稳定性本身可以看成是真假性的某种推广，因为它可以回答“状态 $x$ 在多少步以后使得某个性质持续为真”，因此每个映射 $X\to \mathrm{\Omega }$ 都相当于这样一个稳定性质，而 $X\to 2$ 只能回答“状态 $x$ 的某个性质是否为真”。

特别的，注意后者是集合中的映射，因为回答某个性质是否为真是一个静态概念，它不涉及时间性，或者我们也可以把它看成是配上恒等自映射的集合，即真假是永恒的。

一般而言，这种用”主观寓于客观“来解释范畴之间的包含关系，即主观范畴 $\mathcal{C}$ 含于客观范畴 $\mathcal{X}$，诱导出映射种类的至少四重划分：

$e$：等变映射 equivariant map，动力系统之间的映射

$m$：用理论系统 $B$ 建模 modeling 或模拟 simulation 自然系统（自由度减少，收束于我们感兴趣的性质）

$s$：在计算机 $B$ 中建模或模拟某理论 $A$

$r$：将设计 $A$ 实现为机器 $X$ （自由度增加，产生额外的副作用）

在作者看来，精神（如理论、设计）与人造物（如计算机）是主观范畴的一部分。而客观物则是外在于主观范畴的客观对象。因此在计算机中建模某理论，是主观范畴内的映射。而等变映射，则是外在于主观的客观动力系统之间的映射。而建模是从具体的客观范畴中抽象出某些性质在主观范畴中进行研究，而实现则是将主观范畴中的对象实现为客观物——在这个过程中我们要求客观物完全的表达主观对象（即用主观对象命名客观物，或者说在客观物中落实我们主观对象所要求的全部），但我们并不保证这其中会引入其他副作用——例如我们将逻辑运算实现为电路中电压的高低水平，但电路还额外产生出热量，这热量就不是任何主观的对应。

为使这些粗略的描述更加精确，则要求结构比单一自映射范畴更深的系统，故而目前来说这些词语只是启发性的。

5、动力系统的表示

${\mathcal{S}}^{\circlearrowright }$-映射 $X^{\circlearrowright \alpha }\to Y^{\circlearrowright \beta }$ 的数目是否可以通过简单的规则确定？此问题值得我们给予的更多关注。 这个问题的答案取决于 $X^{\circlearrowright \alpha },Y^{\circlearrowright \beta }$ 如何表示。但有一种描述有限系统的系统性方法非常有用。例如：

1. 为其中的某些元素赋予名字。若某环有毛（指与环中元素相连的非环路径）则标记其端点；若无毛则标记环中的一个元素。我们称这些标记的元素为 $X$ 的生成元。

   

2. 指定一个顺序罗列生成元，例如 $a,b,c,d$。

3. 从列表中的第一个元素开始，不断作用变换 $\alpha$ 直至出现重复为止，例如 $a,\alpha a,{\alpha }^{2}a,{\alpha }^{3}a,{\alpha }^{4}a$两两不同，但 ${\alpha }^{5}a={\alpha }^{2}a$ 开始重复。

4. 然后轮到列表中的下一个元素，重复 3。

5. 重复 4 直到列表遍历完。

由此我们可以得到一组恰好遍历一遍系统全部状态的列表： $a,\alpha a,{\alpha }^{2}a,{\alpha }^{3}a,{\alpha }^{4}a,b,c,d,\alpha d$，以及以下方程组 $R$：

$$\begin{array}{rl}{\alpha }^{5}a& ={\alpha }^{2}a,\\ \alpha b& ={\alpha }^{2}a,\\ \alpha c& ={\alpha }^{3}a,\\ {\alpha }^{2}d& =d.\end{array}$$

这些方程式称为生成元之间的关系。

将已遍历的点记上标签有助于找到这些方程式。

这个过程能在有限时间内停止，因为我们局限于有限状态系统。

如果任意 ${\mathcal{S}}^{\circlearrowright }$-映射 $X^{\circlearrowright \alpha }\to Y^{\circlearrowright \beta }$ 将 $a\mapsto \overline{a}$ 等等，那么显然在 $Y$ 中也需要满足相同方程组 $\overline{R}$：

$$\begin{array}{rl}{\beta }^5\overline{a}& ={\beta }^2\overline{a},\\ \beta \overline{b}& ={\beta }^2\overline{a},\\ \beta \overline{c}& ={\beta }^3\overline{a},\\ {\beta }^2\overline{d}& =\overline{d}.\end{array}$$

令人惊讶的是，这一程序可以逆转：给定任意 $\overline{a},\overline{b},\overline{c},\overline{d}$ 满足以上关系式，则恰好存在一个 $f$ 使得 $f(a)=\overline{a}$ 等等。也就是说，每个 ${\mathcal{S}}^{\circlearrowright }$-映射 $X^{\circlearrowright \alpha }\to Y^{\circlearrowright \beta }$ 与 $Y$ 中满足相同关系式的四元组 $(\overline{a},\overline{b},\overline{c},\overline{d})$ 一一对应。也就是说这样的四元组是 $f$ 存在的充要条件。

我们把对象中的一组元素和其元素之间的满足方程组合称为对象的表示 presentation，如果它满足上面的“泛性质” universal property，即每个 ${\mathcal{S}}^{\circlearrowright }$-映射 $X^{\circlearrowright \alpha }\to Y^{\circlearrowright \beta }$ 都一一对应于 $Y$ 中满足相同方程的集合。我们上面给出的方法（即对象的生成元及其生成关系）给出了 $X^{\circlearrowright \alpha }$ 的“最小”表示。

这种表示是否能帮助我们找到所有可能的映射呢？尤其是如何计算这些映射的数目？假设 $X^{\circlearrowright \alpha }$ 如上图所描述，而 $Y^{\circlearrowright \beta }$ 如下图

我们可以按照以下步骤找齐所有 ${\mathcal{S}}^{\circlearrowright }$-映射 $X^{\circlearrowright \alpha }\to Y^{\circlearrowright \beta }$：

1. 找到所有可能的 $f(a)$，即满足第一个方程 ${\beta }^5\overline{a}={\beta }^2\overline{a}$ 的元素，例如 $w,x,y,z$ 满足该要求，但 $l,m,p,q,r,s,t,u,v$ 不满足。
2. 对 1 中的每一个可能性，寻找 $\overline{b}$ 满足第二个方程 $\beta \overline{b}={\beta }^2\overline{a}$。例如，当我们取 $\overline{a}=w$ 时，我们可以看到 ${\beta }^2\overline{a}={\beta }^{2}w=y$，因此 $\beta \overline{b}=y$，即 $\overline{b}$ 在 $x,z$ 中选。
3. 然后根据 $\overline{a},\overline{b}$ 的选择，找到符合下一个方程式的 $\overline{c}$
4. 最后找到 $\overline{d}$。

练习：找到所有 ${\mathcal{S}}^{\circlearrowright }$-映射 $X^{\circlearrowright \alpha }\to Y^{\circlearrowright \beta }$。

我们写一个程序帮忙：

X_generator = {'a','b','c','d'}
Y = ['l','m','p','q','r','s','t','u','v','w','x','y','z']
beta = {
    'p':'r',
    'q':'r',
    'r':'t',
    't':'v',
    'v':'u',
    'u':'s',
    's':'t',
    'l':'m',
    'm':'l',
    'z':'y',
    'y':'w',
    'w':'x',
    'x':'y'
}
def apply(f, x, n=1):
  res = x
  for i in range(n):
    res = f[res]
  return res
  
from itertools import product
all_f = []
f={}
for values in product(*[Y]*len(X_generator)):
  for k,v in zip(X_generator, values):
    f[k] = v
  all_f.append(f.copy())
  
from typing import Tuple
def check_rule(rule: Tuple[Tuple[int, str], Tuple[int, str]], endomap, morphism):
  left, right = rule
  n1, x1 = left
  n2, x2 = right
  return apply(endomap, morphism[x1], n1)==apply(endomap, morphism[x2], n2)
  
rules = [((5,'a'),(2,'a')),((1,'b'),(1,'a')),((1,'c'),(3,'a')),((2,'d'),(0,'d'))]
valid_f = [f for f in all_f if all(check_rule(rule, beta, f) for rule in rules)]

最后确实打印出 14 个符合条件的映射，罗列如下：

$\overline{a}$	$\overline{b}$	$\overline{c}$	$\overline{d}$
w	w	y	l
w	w	y	m
x	x	w	l
x	z	w	l
x	x	w	m
x	z	w	m
y	y	x	l
y	y	z	l
y	y	x	m
y	y	z	m
z	x	w	l
z	z	w	l
z	x	w	m
z	z	w	m

不过此处我们采用的是穷举法，即枚举出全部生成元像点的可能性 ${13}^4=28561$ 种，然而同时检验是否满足所有方程。而书中所给的算法是先确定第一个生成元像点的可能取值，相当于提早缩小搜索空间剪枝，而我们则是穷尽到叶节点，然后直接在叶节点上检查方程式。穷举法的好处是不需要确定一个遍历顺序，因此也不需要考虑方程式的验证顺序（毕竟我们必须用第一个方程来确定第一个生成元的可能性，而方程组中的方程之间还有依赖关系，这都使查找、排除变得较为繁琐），从而把方程式的验证顺序同排除生成元的可能取值彻底分开。

这里有一句忠告：盲目地遵循”算法”会比较繁琐。如果你在操作中保持头脑清醒，往往会发现一些有趣的事情。例如在本例中，我们会发现对 $\overline{d}$ 的选择与对 $\overline{a},\overline{b},\overline{c}$ 的选择完全无关；但对 $\overline{b},\overline{c}$ 的选择却取决于先前对 $\overline{a}$ 的选择。这与 $X^{\circlearrowright \alpha }$ 的特征有关，说明它是两个更简单系统的和此外， $Y^{\circlearrowright \beta }$ 是三个部分的和。

与上一段呼应，如果不采用穷举法，则需考虑生成元选择之间（因方程造成的）依赖关系。

练习：请自己找一个简单的动力系统，并确定它的表示。

略。

练习：我们的寻找对象间映射的算法以不同的方式处理源对象 $X^{\circlearrowright \alpha }$ 和目标对象 $Y^{\circlearrowright \beta }$ 。假设现在我们除了 $X^{\circlearrowright \alpha }$ 的表示之外，还知道 $Y^{\circlearrowright \beta }$ 的表示。试着不使用 $Y^{\circlearrowright \beta }$ 的内部图示，仅凭借其表示解出方程组。我们甚至可以使用编程求解。

我早就开始用了。

解答：注意到表示本身就决定了对象的全部结构。我们首先找到 $Y^{\circlearrowright \beta }$ 的表示，生成元 $p,q,l,z$，生成元关系：

$$\begin{array}{rl}{\beta }^{6}p& ={\beta }^{2}p,\\ \beta q& =\beta p,\\ {\beta }^{2}l& =l,\\ {\beta }^{4}z& =\beta z.\end{array}$$

这个过程的副产品是生成表 $p,\beta p,{\beta }^{2}p,...,{\beta }^{5}p,q,l,\beta l,z,\beta z,{\beta }^{2}z,{\beta }^{3}z$。

事实上，所谓的生成元和生成元方程其实是如果写出所有方程，即把所有元素互相之间的变换关系写出，例如 $\beta t=v$ 等等，那么生成元和生成元方程则是总方程组中的极大独立变量组和极大独立方程式组。（类比线性代数中的极大线性无关组和独立方程组）

现在我们要从 $Y^{\circlearrowright \beta }$ 的表示出发寻找映射，一个简单的想法是这种映射应该将 $X^{\circlearrowright \alpha }$ 生成元映射为 $Y^{\circlearrowright \beta }$ 的生成元，可惜从前面答案可以看出并非如此。 因此，我们还是需要逐个在生成表中尝试 $X$ 生成元的取值。

编程如下：

X_generators = ['a','b','c','d']
Y_generators = ['p', 'q', 'l', 'z']
Y_rules = [((6, 'p'),(2,'p')),((1,'q'),(1,'p')),((2,'l'),(0,'l')),((4,'z'),(1,'z'))]
Y_gen_list = []
for g in Y_generators:
    n = 0
    repeat = False
    while not repeat:
      new_element = (n, g)
      for rule in Y_rules:
          left, right = rule
          if left == new_element and right in Y_gen_list:
            repeat = True
            break
      if repeat:
        break
      Y_gen_list.append(new_element)
      n += 1

from itertools import product

all_f = []
f={}
for values in product(*[Y_gen_list]*len(X_generators)):
  for k,v in zip(X_generators, values):
    f[k] = v
  all_f.append(f.copy())
len(all_f)
def apply2(f, x, n):
  t = f[x]
  n0, y = t
  return (n+n0, y)
from typing import Tuple
def reduce(p: Tuple[int, str], gen_list, rules):
  n, y = p
  if not p in gen_list:
    for rule in rules:
      left, right = rule
      n1, y1 = left
      n2, y2 = right
      if y == y1:
        q = n // n1
        r = n % n1
        n_ = n2 * q + r
        return reduce((n_, y2), gen_list, rules)
  else:
    return p
def check_rule2(rule: Tuple[Tuple[int, str], Tuple[int, str]], morphism, Y_gen_list, Y_rules):
  left, right = rule
  n1, x1 = left
  n2, x2 = right
  res1 = apply2(morphism, x1, n1)
  res2 = apply2(morphism, x2, n2)
  res1 = reduce(res1, Y_gen_list, Y_rules)
  res2 = reduce(res2, Y_gen_list, Y_rules)
  return res1 == res2
X_rules = [((5,'a'),(2,'a')),((1,'b'),(1,'a')),((1,'c'),(3,'a')),((2,'d'),(0,'d'))]
valid_f = [f for f in all_f if all(check_rule2(rule, f, Y_gen_list, Y_rules) for rule in X_rules)]

由于我们不直接知道 $Y$ 的内部图示，我们需要把所有元素处理成生成元与自映射作用阶次的序对，而比较两个元素是否相等就归结为比较其序对形式是否一致，为此我们需要利用生成元关系来约化高阶序对。

甚至是无穷状态的动力系统也可能有有限表示，例如自然数集在加法自态射下只有一个生成元 $0$，且没有额外的生成元关系。

练习：找到以下系统的表示。

解答：生成元 $a,b,c$，生成关系 $\sigma a=\sigma b,{\sigma }^{2}a={\sigma }^{2}b$。

练习：考虑图的表示。（想不到的话就留待第二十二讲）

解答：对于自态射对象（动力系统对象）而言，表示的特点在于选取一个对象的子集，然后通过反复施加自态射遍历全部元素。但是这仅仅是针对自态射对象而言，事实上表示的本质是能够刻画对象间的全部映射。我们可以把对象的表示视为是对象间映射的一组基底。不过图的表示具体是什么还想不到。

其实在本节中自态射范畴的表示的定义也是相当粗糙的，毕竟我们压根就没有证明上面那个一一对应的性质。

看完第十八讲，图 $G$ 的表示需要刻画从 $G$ 出发的任意图映射，而我们知道图映射的特点是把箭头映射为箭头，节点映射为节点，且保持箭头的节点关系不变，即源节点映射为源节点，汇节点映射为汇节点。因此，图 $G$ 的表示至少应该包含所有箭头（生成元），因为箭头之间没有生成关系，但是一旦确定了箭头的映射关系，那些属于箭头的源或汇的节点的映射关系也相应的确定了，最后剩下的是不属于任何箭头的节点，即孤立节点。而那些属于多个箭头的节点，换言之就是共享同一个节点的不同箭头还需要满足节点关系（生成元关系），二者共同构成了图的表示。

练习：一个非自主动力系统 $S$ 是”演化规则” $\mathbb{N}\times S\stackrel{r}{\to }S$ 本身依赖于时间的系统。该系统可以通过还原为一个自主系统来研究，其状态空间为 $X=N\times S$，相应的动力映射为 $p(n,s)=(n+1,r(n,s))$。证明对于任意 $r，S$ 中恰好有一个序列 $u$，满足 $u(n+1)=r(n,u(n))$，并且 $u(0)=s_0$ 为给定起点。（提示：将其还原为 ${\mathcal{S}}^{\circlearrowright }$ 上 $N=(\mathbb{N},\sigma )$ 的泛性质）

思路：我们试图使用上面动力系统范畴的表示的泛性质，即每一个表示对应于一个动力系统间的映射。此处我们需要考虑的动力系统间映射是 ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{f}{\to }{X}^{\circlearrowright p}$。

解答：对于任意 $r$， 它都确定了一个题干中的 $p$ 使得我们可以把该非自主动力系统 $S$ 还原为一个自主系统 $X$。因此我们考虑动力系统映射 ${\mathbb{N}}^{\circlearrowright \sigma }\stackrel{f}{\to }{X}^{\circlearrowright p}$，由于 ${\mathbb{N}}^{\circlearrowright \sigma }$ 的泛性质可知，生成元 $0$ 唯一确定了 $f$。由于该元素没有任何积极性质，所以可以取任意值。设 $f(0)=(n_0,s_0)$，那么根据 $f$ 的性质可知 $f(n+1)=p(f(n))=(n_0+1,r(n_0,f(n))$。若取 $u(n)$ 为 $f(n)$ 的 $S$ 分量，则我们有 $u(n+1)=r(n_0,u(n)),u(0)=s_0$ 的递推式成立，最后取 $n_0=0$ 即可。$u$ 的存在唯一性由 $f$ 的存在唯一性得到。

这个命题颇有点类似微分方程初值问题解的存在唯一性结论。

第十六讲、幂等、对合和图

1、解答关于幂等映射和对合映射的习题

略。

2、解答关于图范畴映射的习题

略。

这两节是解答第三篇中的若干习题，因为我们已经在行文中解答了它们，从略。

练习：给定范畴 $\mathcal{C}$ 中的对象 $G$，定义范畴 $\mathcal{C}/G$ 如下：其对象为 $\mathcal{C}$ 中的对象 $X$ 并配有 $\mathcal{C}$-分拣映射（ $\mathcal{C}$-sorting map） $X\stackrel{s}{\to }G$，其映射为满足以下交换图的 $\mathcal{C}$-映射

例如第十二讲第二节中的亲属关系可以视为 $\mathcal{C}/G$ 中的对象，其中 $\mathcal{C}={\mathcal{S}}^{\circlearrowleft \circlearrowright }$，分拣映射分别为父亲映射和母亲映射，而 $G$ 是性别对象。另外，第三第八节中的最后一个练习给出了该范畴的另一个描述。请解释在何种意义下，这两种描述给出了同一个结构。

回忆映射的两种视角，所谓的分拣映射只是为了说明映射的陪域是已知的（简单）对象。这里相当于把人分拣成了两种性别的简单范畴。

解答：一方面 $P$ 是所有人类的集合，配有父母亲自态射，从 $P$ 到 $G$ 有映射 $P\stackrel{g}{\to }G$。

另一方面

其中 $M,F$ 分别为全体男性和全体女性的集合， $\varphi ,\mu$ 分别是父亲映射和母亲映射。为方便起见我们记这个结构为 $Q$。

注意到分拣映射 $P\stackrel{g}{\to }G$ 将 $P$ 分成两个子集 $g^{-1}(female),g^{-1}(male)$，而它们恰好是全体女性和全体男性的集合 $F,M$。事实上我们有如下”交换图“成立，

其实这里并不是严格意义上的交换图，因为它们并非是同一范畴中的对象，但为何这么画且看下面的阐释。

其中 $\pi$ 将 $P$ 中的人按照性别分成两组，若为男性则 $\pi (x)\in M$，若为女性则 $\pi (x)\in F$。而 $i$ 将 $M$ 中的元素全部映射为 $male$，将 $F$ 中的元素全部映射为 $female$，即 $g=i\circ \pi$。此外 $i,\pi ,g$ 与 $P$ 上的自映射 $f,m$ 满足以下性质：

若 $\pi (x)\in M$，则 $g\circ f(x)=i\circ \varphi \circ \pi (x),g\circ m(x)=i\circ {\mu }^{\prime }\circ \pi (x)$；

若 $\pi (x)\in F$，则 $g\circ f(x)=i\circ {\varphi }^{\prime }\circ \pi (x),g\circ m(x)=i\circ \mu \circ \pi (x)$。

用自然语言解释就是 $g\circ f(x),g\circ m(x)$ 询问的是我的父母亲的性别，然后 $\pi$ 的作用是根据我的性别分类讨论，如果我是男性就用 $\varphi ,{\mu }^{\prime }$ 确定我父母亲然后 $i$ 确定其性别，反之亦是。

我们可以简写为 $f{|}_M=i\circ \varphi ,f{|}_F=i\circ {\varphi }^{\prime },m{|}_M=i\circ {\mu }^{\prime },m{|}_F=i\circ \mu$。

此外 $i,\pi ,g$ 与 $G$ 上的自映射 $f,m$ 满足以下性质

若 $\pi (x)\in M$，则 $f\circ g(x)=i\circ \varphi \circ \pi (x),m\circ g(x)=i\circ {\mu }^{\prime }\circ \pi (x)$；

若 $\pi (x)\in F$，则 $f\circ g(x)=i\circ {\varphi }^{\prime }\circ \pi (x),m\circ g(x)=i\circ \mu \circ \pi (x)$。

即在 $G$ 上求我的父母亲的性别，相当于用 $\pi$ 先分类讨论我的性别，再求我的父母亲（$\varphi ,\mu$），再用 $i$ 确定其性别。

这里提到的其实是商结构。不过似乎我的解答还不够完善。

分拣映射 $g$ 定义了等价关系，即把 $P$ 中的元素按其性别分成两类，男性集合和女性集合。这样父亲映射和母亲映射在男性和女性集合上都是自映射。

第十七讲、图的一些用处

1、路径

如何使用图来解决问题？首先是表述问题，为此，我们需要一个通用语境（即范畴），大多数问题及其解答可以在该语境下表达出来。这种语境的好处是，当两个问题（一个已知，另一个未知）以同样的方式表述时，我们就能更准确地看到它们的共同特征，这样处理一个问题的经验就能指导你解决另一个问题。这样，我们就建立了一小族概念和方法，可以用来解决更多问题。

还有一点：解决特定问题不是科学的唯一目标，甚至不是主要目标。理解事物、对事物有清晰的认识也是一个目标。例如，牛顿发现了苹果下落和行星运动都服从同一个普遍原理，寻求对运动的清晰认识正是我们实现太空旅行的可能性所在。

给定一个图 graph，我们可以构造图的自由范畴 free category，其对象为图的节点，其映射为从一个节点到另一个节点的路径，注意恒等映射就是长度为零的路径。而映射的复合就是路径的复合，即将终点和起点重合的两个路径联接起来形成一个新的路径。

练习：考虑以下图上的自由范畴，哪些图有一个终对象 terminal object？

终对象的定义在后文中才给出，它指的是若对任意对象 $X\in \mathcal{C}$，都存在唯一的映射 $X\to S$，则称 $S$ 为终对象。

解答： b,c 有。 a 没有，因为对于单点本身而言存在无穷多路径以自己为终点。 d 没有，道理同上。 e 没有，因为存在两条路径使得左边节点映射到右边节点。 f 没有因为最右侧节点与其他两个节点之间没有路径。我们因此可以归纳得出终对象必须是树（即有向无环连通图）。

2、作为图示形状的图

图 graph 和范畴的外部图示 diagram 的相似性暗示了我们另一个图的主要用法。若 $G$ 是一张图如下，

则在任何范畴中我们都能找到以此图为形状的图示。这个图示把图中每个节点对应为范畴中的一个对象，每个箭头对应为范畴中具有相应定义域和陪域的映射。它可以称为 $\mathcal{C}$ 中的 $G$ 形图 figure of shape $G$ in $\mathcal{C}$ 。注意，节点是可以对应到重复对象的，例如

用我们图 figure 的类比，我们可以称之为奇异图 singular diagram，因其中若干节点对应同一个对象 $A$。从现在起我们暂时把 $\mathcal{C}$ 当作集合范畴，不过我们将看到 $G$ 形图其实适用于任意范畴。

若我们取 $G$ 中的一条路径，如下面加粗的

我们在范畴中的图示允许我们将其解释为范畴中的映射，即映射 $ikf$。这路径的解释也对零长路径成立，譬如最左侧节点可以解释为 $1_A$。

3、交换图

定义：我们称范畴 $\mathcal{C}$ 中的 $G$ 形图交换，如果对任意点对 $p,q\in G$，从 $p$ 到 $q$ 的所有路径都被解释为 $\mathcal{C}$ 中的同一映射。以下是一些例子，

表示 $hg=f$。

剩下的例子就不举了。这里主要是为了给前面提出的交换图一个更明确的定义。

练习：

证明使该图交换的映射是互逆的。

解答：假设该图分配的对象和映射如下

那么考虑 从 $A$ 到 $A$ 的路径，零路径与 $g\circ f$ 交换，因此 $g\circ f=1_A$，同理 $f\circ g=1_B$。故 $f,g$ 互逆。

练习：使得下图交换的充分条件是 $jf=mi,kg=nj,lh=pk$。证明 $pnmi=lhgf$。

解答：充分条件是这三个方块分别单独交换。要证明的式子对应于路径 $ABCDH$ 与 $AEFGH$ 交换。证明很简单首先 $ABF,AEF$ 交换而 $BCG,BFG$ 交换，因此 $ABCG,ABFG,AEFG$ 交换，又 $CDH,CGH$ 交换因此 $ABCDH,ABCGH,ABFGH,AEFGH$ 交换。

练习：对以下各个图，找到最短的方程组使其交换。然后解释以下为什么你知道从这些方程就能推出所有可能路径都给出相同的复合结果。

解答：

1. $g=h,g\circ f=1_A,f\circ g=1_B$.
2. $h\circ g\circ f=1_A,f\circ h\circ g=1_B,g\circ f\circ h=1_C$.
3. $i=1_C,f=g,j\circ h\circ g=1_A,g\circ j\circ h=1_B,h\circ g\circ j=1_A$.

因为我们找的最短方程组涉及的映射相当于生成元，而最短方程组相当于生成元关系。从这些路径可以生成出全部可能的路径。如果这些生成元满足的方程相等，那么一切可能的路径也都相等。

4、图示本身是否是一个映射？

如果 $G$ 是一个图，那么范畴 $\mathcal{C}$ 中的 $G$ 形图示就会把 $G$ 的每个节点关联到 $\mathcal{C}$ 中的一个对象，把 $G$ 的每个箭头关联到 $\mathcal{C}$ 中的一个映射且它保持 $G$ 的结构。这说明 $G$ 形图示是从 $G$ 到范畴 $\mathcal{C}$ 的一个”映射”。可是这里的映射不是某个图范畴中的映射，因为 $\mathcal{C}$ 不是一个图。不过，与任意范畴 $\mathcal{C}$ 相关联的都有一个大图，图中的节点是 $\mathcal{C}$ 中的对象，箭头是 $\mathcal{C}$ 中的映射，其源节点是定义域，其汇节点是陪域。我们称这个大图为 $\mathcal{U}\mathcal{(}\mathcal{C}\mathcal{)}$ 。这个图遗忘了如何在 $\mathcal{C}$ 中对映射进行复合，只记录了对象和映射及其定义域和陪域。此时范畴 $\mathcal{C}$ 中的 $G$ 形图示就是从 $G$ 到 $\mathcal{U}\mathcal{(}\mathcal{C}\mathcal{)}$ 的图映射，事实上它唯一地扩展为从自由范畴 $\mathcal{F}(G)$ 到 $\mathcal{C}$ 的函子。操作 $\mathcal{U}$ 和 $\mathcal{F}$ 可以有效地处理图与范畴之间的基本关系。

这里所谓的遗忘复合其实是指在大图 $\mathcal{U}(C)$ 中只有基本路径（或者说基本映射）而没有复合路径（例如只有路径 $A\stackrel{f}{\to }B\stackrel{g}{\to }C$ 而没有 $A\stackrel{g\circ f}{\to }C$），而图示相当于是嵌入这个大图的一个子图，即找到大图中的一个路径交换的子图。

第十八讲

略