读书笔记: 范畴论

读书笔记: 范畴论

基本概念

范畴论

  • 数学构造(Mathematical structure) 在数学上,在集合上的一个构造是一个附加的数学对象,赋予这个集合某种意义。
  • 范畴论(category theory) 范畴论的目的是:规范化数学构造。 方法为:使用带标签的有向图。 研究内容:各种数学结构之间的关系。

范畴(category)

一个范畴是一个带标签的有向图,其节点为对象(object),带有标签的有向边为箭头(arrow or morphism)。

一个范畴C包含3个数学实体:

  • 对象集合:ob(C) 每个元素都是一个对象,一个对象又可以认为是一个集合。
  • 态射集合: hom(C) 态射集合的每个元素是一个态射, \(f: a \to b\),每个态射f有一个源对象(source object) a和目标对象(target object)b。 \(hom(a, b)\)表示从a到b的所有态射。
  • 性质:二元操作:态射结合(composition of morphisms): \(\circ\) \(f: a \to b, g: b \to c\) 的结合是 \(g \circ f\)。具有
    • 满足结合律(Associativity): $ h \circ ( g \circ f ) = ( h \circ g ) \circ f $
    • 存在恒等态射(identity): 对于每个对象x,存在一个恒等态射(identity morphism) \(1_x: x \to x\), 其性质为,对于任何态射\(f: a \to b\),有\(1_b \circ f = f = f \circ 1_a\) 恒等态射的含义是:定义了相同关系(equality relation A = B)。 可以简单的认为是;\(f(x) = x\)。

态射(morphism)

态射可以理解为一个函数,在范畴论中,往往表示为一个对象和另一个对象的map关系。 态射作为函数理解的时候,不用纠结于参数的个数。

态射的种类(\(f: a \to b\)):

  • 单态射(monomorphism or monic) 如果\(f \circ g_1 = f \circ g_2 \implies g_1 = g_2, \forall g_1, g_2: x \to a\)。 其含义是:不存在两个a中元素 map 到同一个b中的元素。 \(\forall a_1, a_2 \in A, a_1 \neq a_2 \implies f(a_1) \neq f(a_2)\)
  • 满态射(epimorphism or epic) 如果\(g_1 \circ f = g_2 \circ f \implies g_1 = g_2, \forall g_1, g_2: b \to x\)。 其含义是:每一个b中的元素,都在a中有至少一个 source mapper。
  • 双态射(bimorphism) 即是单态射,有时满态射。
  • 同构(isomorphism) 如果存在一个同构\(g:b \to a\),有\(f \circ g = 1_b, g \circ f = 1_a\)。 其含义是:a,b两个对象的元素存在一对一的 map 关系。 同构 = 双态射 + 存在逆态射。 g称为逆态射,也是一个同构,g 的逆态射是 f。 比如:f是加法,g是减法。
  • 自态射(endomorphism) 表示一个态射源对象和目标对象是同一个, \(f: a \to a\)。记为:end(a)。
  • 自同构(automorphism) 如果f既是一种自态射,又是具有同构性。记为:aut(a)。
  • 撤回射(retraction) 如果存在一个f的右逆,也就是说,如果存在: $g : b \to a, f \circ g = 1_b。 f 是另一个态射g的撤回射,其含义是:g 可以通过f找到 source element。f必定是一个满态射(epimorphism)。
  • 部分射(section) 如果f的左逆是存在的,也就是说,如果存在: $g : b \to a, g \circ f = 1_a。 f 是另一个态射g的部分射,其含义是:f 确定了g的同构部分。f必定是一个单态射(monomorphism)。 是不是可以理解为f的g应用的一个条件???
  • 同态(homomorphism) 同态(homomorphism)是一个态射,表示一个数学结构\mathcal{A}(C, , e)到另一个数学结构\mathcal{B}(C', ', e')的map关系,并且维持了数学结构上的的每一种操作*。 同态(homomorphism) \(f: \mathcal{A} \to \mathcal{B}\),有: \(f(x * y) = f(x) *' f(y)\) 同一种操作在不同的数学结构上定义可以不同。 比如:指数函数是一个同态。

\[ f : \mathbb{R} \to \mathbb{R} \\ f(x) = e^x \\ e^{x + y} = e^x e^y \to f(x * y) = f(x) * f(y) \\ where \\ f \text{ exponential function is a homomorphism} \\ \text{the source is A} = \mathbb{R} \\ \text{the target is B} = \mathbb{R} \\ * = + \text{ in A} \\ * = \times \text{ in B} \]

  • 域(domain)/协域(codomain) 对于一个态射(morphism) \(f : S \to T\)。 域(domain)是这个态射的源,协域(codomain)是这个态射目标。
  • 范畴的表达
    1. 表达1

\[ C = (Ob(C), Hom_C(x,y), id_x, \circ) \\ where \\ Ob(C) \in Set_{object} \\ Hom_C(x, y) \in Set_{morphism} \ | \ x, y \in Ob(C) \\ id_x \in Hom_C(x, x) \text{ : identity morphism of x} \\ \circ : Hom_C(y, z) \times Hom_C(x, y) \to Hom_C(x, z) \text{ : composition formula} \\ \text{Identity Law:} \\ \forall x, y \in Ob(C), f: x \to y \\ f \circ id_x = f \\ id_y \circ f= f \\ \text{Associative Law:} \\ \forall w, x, y, z \in Ob(C), h: w \to x, g: x \to y, f: y \to z \\ (h \circ g) \circ f = h \circ ( g \circ f) \in Hom_C(w, z) \]

函子(functor)

函子是范畴之间的map关系。可以理解为范畴之间的态射。

  • 协变(covariant)函子 \(F: C \to D\), F包含:
    • 对于每一个 C 中的对象x,对应一个 D 中的F(x)。
    • 对于每一个C中的态射\(f: x \to y\),对应D的态射\(F(f): F(x) \to F(y)\)。
  • 逆变(contravariant)函子 和协变函子类似,只不过态射的方向是从D到C。

自然转换(Natural transformation)

自然转换是两个函子之间的关系。函子描述“自然构造(natural constructions)”,自然转换描述两个这样构造的"自然同态(natural homomorphisms)"。 homomorphism的意思是相同的形状。

其它

  • 本体(olog)
  • 交换图(commutative diagram)
  • 通用性质(universal property) 如果,两个数学结构是同构(isomorphism),那么它们之间就存在通用性质。 同构意味着两个数学结构X和Y中的元素是存在一一对应。 那么,Y上的性质(态射)意味着X上存在一个对应的性质(态射)。比如: X = {A, B, C} Y = {1, 2, 3} A --> 1 B --> 2 C --> 3 如果+(1, 2) = 3,我们也可以认为存在 +(A, B) = C。起点性质。 如果+(1, 2),我们也可以认为存在 +(C) = (A, B)。起点性质。 通用性质(universal property)要么是一个起点性质(initial property),要么是一个终点性质(terminal property)。
    • 起点性质(initial property) 唯一存在 \[ U: D \to C \\ D \{ A, Y \} \\ C \{ X, U(A), U(Y), \phi: X \to U(A) \} \\ \therefore \\ \text{initial property:} \\ \forall f: X \to U(Y) \\ \exists g, g: A \to Y \\ \exists U(g), g: U(A) \to U(Y) \\ \]
    • 终点性质(terminal property) 唯一存在 \[ U: D \to C \\ D \{ A, Y \} \\ C \{ X, U(A), U(Y), \phi: U(A) \to X \} \\ \therefore \\ \text{terminal property:} \\ \forall f: U(Y) \to X \\ \exists g, g: Y \to A \\ \exists U(g), g: U(Y) \to U(A) \\ \]
    • 起点性质示例 \[ X = (L : (a,b,c), A:L \times L, B: L) \\ Y = (N : (1,2,3), A_y:N \times N, B_y: N, C_y: A_y) \\ \phi: C_y \to A_y = c \\ \text{e.g. } (1, 2) = (1, 2) \\ f: C_y \to B_y = c_1 + c_2 \\ \text{e.g. } 1 + 2 = 3 \\ \therefore \\ \exists g: A \to B \\ \text{e.g. } a + b = c \]
    • 终点性质示例 \[ X = (L : (a,b,c), A:L \times L, B: L) \\ Y = (N : (1,2,3), A_y:N \times N, B_y: N, C_y: B_y) \\ \phi: A_y \to C_y = a_1 + a_2 \\ \text{e.g. } 1 + 2 = 3 \\ f: B_y \to C_y = b \\ \text{e.g. } 3 = 3 \\ \therefore \\ \exists g: B \to A \\ \text{e.g. } c = a + b \]
  • 拉回(pullback)
  • 推出(pushout)
  • limit/colimit

关系

  • 二元关系(binary relation) 一个基于集合X的二元关系,是一个\(R \subseteq X \times X\)的子集。
  • 等价关系(equivalence relations) 一个集合X上的等价关系\(\sim\),是一个\(R \subseteq X \times X\)的子集,具有
    • 自反性(Reflexivity) \((x, x) \in R\)
    • 对称性(Symmetry) $(x, y) \in R \text{, iff } \((y, x) \in R\)$
    • 传递性(Transitivity) $\text{if } (x, y) \in R, (y, z) \in R \text{, then } \((x, z) \in R\)$

幺半群(monoid)

幺半群可以代表一个序列或者列表。

  • 幺半群(monoid) 一个幺半群是一个序列(sequence)\((M, e, \star)\)。M是一个集合, \(e \in M\)是一个元素,成为单位元素(identity element)。 \(\star : M \times M \to M\)是一个函数,称为乘法公式(multiplication formula)。 幺半群具有以下属性:
    • 同一律(identity law) \(m \star e = m\) \(e \star m = m\)
    • 结合律(associativity law) \((m \star n) \star p = m \star ( n \star p)\) 比如:字符串就是一个幺半群,e = "", \(\star\) = +。
  • List in set 集合X,在X上的List是 \[ (n, f) \\ where \\ n \in \mathbb{N} \text{ : the length of the list} \\ f: \underline{n} \to X \\ \underline{n} = \{ 1,2, \cdots, n\} \] 记做: \[ (n, f) = [f(1), f(2), \cdots, f(n)] \]
  • 列表单体(free monoid generated by X) \(M: = (List(X), [], ++)\) List(X);集合X的元素列表集合。 []是一个空列表。 ++是连接操作(concatenation)。
  • 显示幺半群(presented monoid) 显示幺半群的作用是提供了替换方法。 由有限集合G和等价关系产生的显示幺半群(the monoid presented by generators G and relation $ { (m_i, m'_i) | 1 \le i \le n } $)

\[ M = \{ M, e, \star \} \\ where \\ \{ (xm_iy \sim xm'_iy) | x, y \in List(G), 1 \le i \le n \} \text{ : equivalence relation} \\ M = List(G)/\sim \\ e = [] \\ \star \text{ : concatenating operation} \]

  • 循环(cyclic)幺半群 循环幺半群的作用是提供了一个环形列表的定义方法。 循环(cyclic)幺半群是只有一个等价关系的显示幺半群。
  • 幺半群行动(monoid actions) 在集合S上的幺半群\((M, e, \star)\)的行动为函数: \[ \hookrightarrow \]

符号

术语

English

Notation

单态射

monomorphisms

$ \hookrightarrow $

满态射

epimorphisms

$ \twoheadrightarrow $

同构

isomorphisms

$ \overset{\sim}{\to} $

群(group)

group是一个monoid,并且每个元素都有一个倒数(inverse)。 推论:倒数具有唯一性。

图形(graphs)

图形(graphs)是由多个顶点(vertex)和顶点之间的箭头(arrow)定义而成。 路径(path)

顺序(order)

  • 预次序关系(preorder) 预次序关系(preorder)\((S, \leq)\)是一个基于集合S的二元关系\(R \subseteq S \times S\), R的关系:\(\text{if } (s, s') \in R, \text{then } s \leq s'\) 并且有
    • 自反性(Reflexivity): \(s \leq s\)
    • 传递性(Transitivity): \(\text{if } s \leq s' \text{and } s' \leq s", \text{then } s \leq s"\)
  • 部分有序(partial order) 部分有序(partial order)是预次序关系,并且
    • 反对称性(Antisymmetry) 如果s <= s', 并且 s' <= s, 则 s = s'。
  • 线性有序(linear order) 线性有序(linear order)是部分有序,并且
    • 可比较性(Comparability) 要么 s <= s', 要么 s' <= s。
  • 派系(clique) 派系(clique)中的每两个点都是毗邻的(adjacent)。 \[ clique \doteq S' \\ where \\ (S, \leqslant) \text{ is a preorder}\\ S' \subseteq S \\ a \leqslant b, \forall a,b \in S' \]
  • meet 和 join \((S, \leqslant)\)是一个preorder。\(s, t \in S\) s和t的meet(the biggest thing smaller than both)是一个元素\(w \in S\), 表示为:$ w \cong s \land t $ 具有: \[ w \leqslant s \\ w \leqslant t \\ x \leqslant w \ | \ \forall x \in S, x \leqslant s \ \And \ x \leqslant t \] s和t的join(the smallest thing bigger than both)是一个元素\(w \in S\), 表示为:$ w \cong s \lor t $ 具有: \[ s \leqslant w \\ t \leqslant w \\ w \leqslant x \ | \ \forall x \in S, s \leqslant x \ \And \ t \leqslant x \] meet 和 join 不一定是唯一的。任何两个meet一定在同一个派系内。
digraph finite_state_machine {
    rankdir=LR;
    size="8,5"

    node [shape = doublecircle]; S;
    node [shape = point ]; qi

    node [shape = circle];
    qi -> S;
    S  -> q1 [ label = "a" ];
    S  -> S  [ label = "a" ];
    q1 -> S  [ label = "a" ];
    q1 -> q2 [ label = "ddb" ];
    q2 -> q1 [ label = "b" ];
    q2 -> q2 [ label = "b" ];
}
  • 反顺序(Opposite order) \(S := (S, \leqslant)\)是一个预次序(preorder),则反顺序\(S^{op} := (s, \leqslant^{op})\), 有: $ s \leqslant s' \iff s' \leqslant s $
  • 次序的态射(morphism of orders) 从\(S := (S, \leqslant)\)到\(S' := (S', \leqslant')\)次序的态射f,表示为\(f: S \to S'\)。 \[ \text{if } s_1 \leqslant s_2 \text{, then } f(s_1) \leqslant f(s_2) \]

Database vs Graph

  • 路径等价声明(path equivalence declaration) 图形\(G := (V, A, src, tgt)\), \(Path_G\)为G中所有路径的集合。 \(p \simeq q | p,g \in Path_G\)为路径等价声明,表示p,g有相同的起点和终点。 在G上的一个一致(congruence) 是一个在\(Path_G\)上的 等价关系\(\simeq\),具有:
  1. \(\simeq\)是一个等价关系.
  2. 如果 \(p \simeq q\),则src(p) = src(q).
  3. 如果 \(p \simeq q\),则tgt(p) = tgt(q).
  4. 假设 \(p,q: b \to c\)是路径,并且\(m: a \to b\)。如果 \(p \simeq q\),则\(mp \simeq mq\).
  5. 假设 \(p,q: b \to c\)是路径,并且\(n: b \to c\)。如果 \(p \simeq q\),则\(pn \simeq qn\). \(\simeq\) 是一个集合,定义了图形上的所有约束。
  • 引理:假设\(p simeq q : a \to b, r \simeq s: b \to c\),则\(pr \simeq qs\)。
  • Database Schema Database Schema \(C := (G, \simeq)\),G是一个图形,\(\simeq\)是G上的一致。
  • Olog = Database Schema
  • 实例(instance) 一个顶点对应的集合,和出入箭头的所有路径上的节点集合。 \[ (PK, FK) : C \to Set \text{ is an instance} \\ where \\ C = (G, \simeq) \\ G = (V, A, src, tgt) \\ PK : V \to Set \text{, one set for one vertex} \\ FK(a) : PK(v) \to PK(w) \ | \ v = src(a), w = tgt(a), \forall a \in A \]
  • 路径法则(Law 1 - Path through a database) \[ FK(a_m) \circ \dots \circ FK(a_1) (x) = FK(a'_n) \circ \dots \circ FK(a'_1) (x) = PK(w), \forall x \in PK(v) \\ where \\ p = v a_1 a_2 \dots a_m : v \to w \\ q = v a'_1 a'_2 \dots a'_n : v \to w \\ p \simeq q \]

范畴化

如何将一个monoid/order group/group index通过一个函子转化成一个范畴。

Database Schema present categories

参照

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

12810
来自专栏欧阳大哥的轮子

常用的数学函数以及浮点数处理函数

在编程中我们总要进行一些数学运算以及数字处理,尤其是浮点数的运算和处理,这篇文章主要介绍C语言下的数学库。而其他语言中的数学库函数的定义以及最终实现也是通过对C...

21320
来自专栏Jacklin攻城狮

简谈常用算法

9820
来自专栏计算机视觉与深度学习基础

Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

26450
来自专栏java初学

top K 问题

494160
来自专栏ACM算法日常

独角兽与数列(置换群循环)- HDU 4985

群论是法国数学家伽罗瓦(Galois)的发明。伽罗瓦是一个极具传奇性的人物,年仅21岁就英年早逝于一场近乎自杀的决斗中。他用该理论,具体来说是伽罗瓦群,解决了五...

9130
来自专栏python3

python3--类的组合,初始类的继承

圆环是由两个圆组成的,圆环的面积是外面圆的面积减去内部圆的面积。圆环的周长是内部圆的周长加上外部圆的周长

17520
来自专栏趣谈编程

快速排序(基础版)

16930
来自专栏漫漫全栈路

计算机组成原理-运算方法之数据格式

数据格式 先说下数据格式,在选择计算机数的表示方式时,需要考虑以下几个因数: 要表达的书的类型(小数,整数,实数,复数) 可能遇到的数值范围 数值精度 数据存储...

29560
来自专栏爱撒谎的男孩

设计模式之常见关系

22130

扫码关注云+社区

领取腾讯云代金券