前言

为什么上两篇范畴论笔记大多数都是针对范畴与函数的关系,难道其他关系不能抽象成一个范畴吗?这个答案当然是否定的,前两篇是借助了函数的概念以更好地理解复合或同态究竟是些什么东西,因此而从本篇开始,我们来说一些与函数关系不大的一些知识吧!

概念

既然范畴论里面我们要讨论的东西无非就是各种态射复合(Morphism composition),就连排序关系也不例外,在第一章时就已讲述了相关概念,这里就不再重提。而我们现在要知道的是除了第二章提及的函数关系外,我们究竟还可以拿复合来研究些什么,而排序就是一个很好例子了。

例如我们有时候会说 \(a\) 小于或等于 \(b\),而 \(b\) 小于或等于 \(c\),那么必然蕴含了 \(a \leq c\)(传递性),这里不难看出实际上排序关系其实也是一个简单的复合,只不过我们把对应的态射给替换成具体我们定义的二元关系 \(\leq\) 罢了。 \[ a \xrightarrow[\leq]{} b \xrightarrow[\leq]{} c \\\\ a \xrightarrow[\leq]{} c \]

排序关系(Order Relationship)

排序关系是对排序在直觉上的自然诠释,同样是属于一种二元关系,它们各自有不同的特性,下面将会介绍一些较为常见的排序关系。

预序(Preorder(Quasiorder))

预序关系满足了自反性(Reflexive)及传递性(Transitive),作为排序关系来讲预序可以将其概念进一步推广至等价关系以及非严谨(Non-Strict)的偏序关系。而由预序关系所组成的集合被称为预序集合(Preordered set or Proset)

现在设 \(\leq\) 是 P 上的二元关系,若果满足下列性质,则称这是一个预序关系,例如: - 自反性:\(\forall a \in P, a \leq a\) - 传递性:\(\forall a, b, c \in P\),若 \(a \leq b\)\(b \leq c\),则 \(a \leq c\)

偏序(Partial order)

如果我们将预序进行推广,并加上反对称性(Anti-symmetric)作为约束,那么我们说这个二元关系就是偏序关系。

现在设 \(\leq\) 是 P 上的二元关系,若果满足下列性质,则称这是一个偏序关系,例如: - 自反性:\(\forall a \in P, a \leq a\) - 传递性:\(\forall a, b, c \in P\),若 \(a \leq b\)\(b \leq c\),则 \(a \leq c\) - 反对称性:\(\forall a, b \in P\),若 \(a \leq b\)\(b \leq a\),则蕴含了 \(a = b\)

全序(Total order)

同样地,我们甚至可以再将预序关系进一步推广,设 \(R\) 为二元关系,限制某一个序的二元关系为 \(aRb \lor bRa\),即完全性(Connex)作为约束,那么得出来的这个关系就叫做全序关系。

现在设 \(\leq\) 是 P 上的二元关系,若果满足下列性质,则称这是一个全序关系,例如: - 传递性:\(\forall a, b, c \in P\),若 \(a \leq b\)\(b \leq c\),则 \(a \leq c\) - 反对称性:\(\forall a, b \in P\),若 \(a \leq b\)\(b \leq a\),则蕴含了 \(a = b\) - 完全性:\(\forall a, b \in P, a \leq b \lor b \leq a\) (但注意其已蕴含了自反关系,因为 \(\forall a, b \in P, a \leq a \lor b \leq b\)

排序在范畴论上的关系(Order in Category Theory)

对于上面的排序关系,如果把它们的性质在范畴论中呈现出来又是怎么样的呢?其实也是很简单的,因为上面所提及到的排序关系其实天然就是一种范畴,比如在开头时我们举过的例子:对于最基础的排序关系,也就是预序关系,我们可以很轻易地把它对应到范畴论上的概念,就如同把二元关系(\(\leq\))替换成态射(\(\to\))一样,这就已经满足了传递性质了。

那么自反性呢?对于自反这一概念,由于我们上面已经得知自反的定义,其实不难发现其实也就是范畴上恰巧有一个态射的跟自反性的概念一模一样,那就是单位元态射(Identity morphism)了(因为同样地可以把 \(\leq\) 替换成单位元态射 \(id_a\),例如:$ a a $)。

Hom-集合(Hom-set)

我们的范畴并不总是只有一个态射在其内,而是可以存在很多态射由不同的对象映射到范畴内的其他对象去,例如在范畴 \(C\) 内我们有 \(a\)\(b\) 这两个对象,存在态射 \(f, g, h\),它们均是由 \(a\) 被态射至对象 \(b\) 上,因此这些态射本身可以组成一个由 \(a\) 态射至 \(b\) 的 Hom-集合,一般写作 \(C(a, b)\)\(hom_C (a, b)\)

与态射复合的关系(Relationship with composition)

态射复合对于 Hom-集合 来讲也是可以被公理化地写出来的,例如存在对象 \(a, b, c\),对于态射 \(f \in hom(a, b)\) 以及 \(g \in hom(b, c)\),我们可以写成这样: \[ hom(a, b) \times hom(b, c) \implies hom(a, c) \]

小范畴与大范畴(Small and large category)

Thin 范畴(Thin Category(or Posetal category))

当然地,满足了上述性质的范畴当然有个名字,被称为 Thin 范畴,含义即 “瘦” 的意思,也就是当一个范畴内当且仅当存在唯一态射,那么这个范畴就会 “瘦” 到只剩这么一个了。

设有 \(hom_C (a, b)\),分别由 \(f\)\(g\)\(a\) 被态射至 \(b\),则蕴含了 \(f = g\),形式化定义为: \[ a \overset{f}{\underset{g}\rightrightarrows} b \implies f=g \]

是或不是一个 Thin 范畴?(Is or not a Thin category?)

有时候一些范畴看着并不像是一个 Thin 范畴,假设有范畴 \(C\),且存在对象 \(a, b, c, d\),而在 \(Commutative-Diagram\) 上如下:

\[ \array{& a & \overset{f}\rightarrow & b & \\\\ f' & \downarrow &&\downarrow & g \\\\ &c & \underset{g'}\rightarrow& d & \\\\ } \]

我们可以注意到在这个例子中 \(hom(a, d)\) 上都看似存在着两条路径,貌似直觉上告诉我们这不是一个 Thin 范畴,因为 “当且仅当存在唯一态射” 这句话告诉了我们如果多于一个态射,那它就不算是 Thin 范畴。

但事实真是这样吗?要知道范畴最重要的概念之一就是态射复合,而当我们把 \(f \circ g\) 之后它的态射实际会相等于 \(f' \circ g'\),因为: \[ hom(a, b) \times hom(b, d) = hom(a, c) \times hom(c, d) \implies hom(a, d) \]

所以实际上透过态射复合后,这两条路径在交换图上的态射将被视为等价的,亦即只被视为存在唯一态射,而不是两个态射,因此这也是属于 Thin 范畴。

与预序集合的关系(Relationship with proset)

我们常常会把预序集合在范畴论上视作为 Thin 范畴,当然它天生也就是一个 Thin 范畴,但这又怎么去解释呢?现在先假设我们要去比较一个自然数,且他们,例如我们要整除 \(6\) 这个数,并将整除结果由预序关系排列出来,可得:\(3 \leq 6\)\(2 \leq 6\)\(1 \leq 6\),可见无论是先 \(1 \leq 3 \leq 6\) 或是 \(1 \leq 2 \leq 6\),最终的结果都会是 \(1 \leq 6\)。这里就是一个态射复合后,它们的结果始终相同的一个例子,而最终 \(\leq\) 在态射复合后始终都只有存在唯一态射,而不像函数那样大多数情况均有很多态射从定义域被映射到值域,因此这符合了 Thin 范畴的定义,并且天然是一个 Thin 范畴了。

与偏序集合的关系(Relationship with poset)

一般来说既然我们可以对预序集合和 Thin 范畴产生联系,那么按理来说偏序集合与 Thin 范畴也是可以对应得上的。而这里得知偏序实际只比预序关系多了反对称的特性,但这并没有使得偏序集合上会多于唯一的态射,它该是一个还是只有一个,因此偏序集合自然地也是 Thin 范畴了。

而反对称性我们又怎么在 Thin 范畴上描述出来呢?我们知道当存在反对称性(即 \(a \leq b \leq a \implies a = b\)),那么这个关系肯定是可互逆(Inverse)的,而现在我们对同构关系进行观察发现,实际上同构关系恰巧就是描述了这种关系,因此我们可以将其定义形式化地写成这样(亦即同构关系): \[ a \overset{f}{\underset{g}\leftrightarrows} b \implies f=g \]

推广至同构与等价关系(Up to Isomorphism and Equivalence)

Thin 范畴与预序以及偏序集合的关系上面已经有了个大致的描述了,总括而言只要我们将 Thin 范畴推广至等价关系,亦即态射是并行且相等的,那么它们就是预序了。而偏序关系上面也已经提及到了,对于一个态射可以逆转回去,那么这就变成一个偏序关系了。

群(Group)

概念

群这个概念本身是在群论(Group Theory)中出现的,它以集合论为基础,即群本身存在一个集合,且由一个二元关系所组成的代数结构,其必须满足所谓的 “群公理”,即包含了封闭性、结合律、单位元以及逆元这四种性质。

实际上群与我们日常生活中有着很紧密的联系,就如同日常都可能用到的加法般,我们把两个正整数相加,透过正整数集合与 \(+\) 我们可构成一个加法群,记为 \(G(\mathbb Z{+}, +)\),其满足了群公理: - 封闭性:\(\forall a, b \in G\),其运算结果也落入 \(G\) 中 - 结合律:\(\forall a, b, c \in G, (a · b) · c = a · (b · c)\) - 单位元:\(\forall a, \exists e \in G, e · a = a · e = a\) - 逆元:\(\forall a, \exists b, e \in G, a · b = b · a = e\)

由于群论并不是我们主要的讨论对象,因此这部分并不会举出很多的例子,而在这仅会讨论幺半群的前置知识。

半群(Semi-group)

有时候群公理在把关系进一步推广出去的时候,未必要加入额外的一些规则,反而我们可以通过放松一些条件来构成一个新的代数结构。比方说我们可以把一般群公理的单位元与逆元给拿掉,剩下封闭性,结合律这两条公理,随之被称为半群,这就是一个很好的例子。

幺半群(Monoid)

当然地,从抽象代数来讲半群也可以再次被推广成幺半群,所谓的 “么” 指的其实就是 “单位元(么元,Identity element)” 的意思,也就是只需要对半群给补上单位元的规则就可以了。

对于范畴 \(C\) 内的对象 \(x\),我们都知道存在单位元态射 \(id_f\),但这种单位元态射难道就只能存在一个了吗?当然不是,我们甚至可以有多个单位元态射,例如 \(id_f, id_g, id_h, ... \in hom(x, x)\),将它们透过态射复合将会亦将得到: \[ x \circ id_f = x \\\\ x \circ id_f \circ id_g = x \\\\ x \circ id_f \circ id_g \circ id_h = x \\\\ x \circ id_f \circ id_g \circ id_h \circ ... = x \]

即其实单位元态射可存在无穷多个的,而对于这种一直都存在多个单位元态射且态射至自身的结构(封闭结构)我们就称之为幺半群。

而幺半群实际上对于计算机编程来说也是至关重要的概念,比方说我们日常能接触到的 String,即字符串,其实也是一个幺半群的结构,这时可以把编程语言的类型视为集合,例如: - 封闭性:"foo" <> "bar" = "foobar" 在运算后的结果都是 String 类型 - 结合律:("foo" <> "bar") <> "foo" = "foo" <> ("bar" <> "foo") = "foobarfoo" - 单位元:"" <> "any" = "any" <> "" = "any"

在 Haskell 上的体现(Works with Haskell)

定义

首先我们来看一下在 Haskell 上 Data.Monoid 下的的源码定义究竟是怎样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Semigroup a => Monoid a where
-- | Identity of 'mappend'
-- | 以 'mappend' 作为二元关系时,以 'mempty' 作为单位元
mempty :: a

-- | An associative operation
-- | 结合律公理
--
-- __NOTE__: This method is redundant and has the default
-- implementation @'mappend' = '(<>)'@ since /base-4.11.0.0/.
mappend :: a -> a -> a
mappend = (<>)
{-# INLINE mappend #-}

-- | Fold a list using the monoid.
-- | 使用幺半群折叠一个 List
--
-- For most types, the default definition for 'mconcat' will be
-- used, but the function is included in the class definition so
-- that an optimized version can be provided for specific types.
mconcat :: [a] -> a
mconcat = foldr mappend mempty

应用

除了上述提及到字符串就是一个幺半群之外,我们也可以利用幺半群的定律对其进行一些操作,例如说使用 mappend (或 <>)拼接两个字符串,又或者说可以使用 mconcat 把一个幺半群结构给折叠起来,例如:

1
2
Prelude> mconcat [[1],[2],[3],[4]]
[1,2,3,4]

Kleisli 范畴(Kleisli Category)

待填坑...