Category Theory: 01 One Structured Family of Structures

Category Theory: 01 One Structured Family of Structures

这次看来要放弃了。看了大概三分之一。似乎不能够让注意力集中了。先更新吧。

群的定义

\(G = \{ G, +, e \}\),一个数据集\(G\),一个二元操作符\(+\),和一个幺元\(e\)。

满足结合律:\((a + b) + c = a + (b + c)\)
满足封闭性。
存在单位元:\(e + a = a = a + e\)
存在逆元:对于每一个a,存在一个逆元a': \(a + a' = e\)
如果满足交换律,则是一个交换群,也就是阿尔贝群。

群的同态(homomorphism)和同构(isomorphism)

  • 定义:同态(homomorphism)
    群同态是一个函数f,应用于源群\((G, *, e)\)和目标群\((G', *', e')\),满足:
    1. \(f(x * y) = f(x) *' f(y)\)
    2. \(f(e) = e'\)
      e.g. \(f(x) = e^x, e^{x + y} = e^x e^y\)
  • 定理:
    1. 群\((G, *, e)\),总有一个单位同态,\(1_G : G \to G\).
    2. 给定两个同态\(f: G \to H, g: H \to J\),存在一个组合同态\(g \circ f : G \to J\).
    3. 同态的组合满足结合律(associative),\(j \circ (g \circ f) = (j \circ g) \circ f\)
  • 定义:同构(isomorphism)
    群同构\((f : G \simeq H)\)是一个同态,如果其对应的函数是一个双射。

  • 定理:
    一个群同态\(f: G \to H\)是一个同构,当且仅当它有一个双边的逆,也就是说,有一个同态\(f': H \to G\),有\(f' \circ f = 1_G, f \circ f' = 1_H\)。

  • 定理
    在群之间的同构是一个群之间的等价关系。

02 范畴的定义

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

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

  • 对象集合:ob(C)
    每个元素都是一个对象,一个对象又可以认为是一个集合。

  • 态射集合: hom(C)
    态射集合的每个元素是一个态射, \(f: a \to b\),每个态射f有一个源对象(source object) a和目标对象(target object)b。
    \(hom(a, b)\)表示从a到b的所有态射。
    每个态射\(f: A \to B\)有src()和tgt(),两个属性,可以获得源对象和目标对象,i.e. \(A = src(f), B = tgt(f)\)。

  • 性质:
    • 二元操作:态射结合(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\)。
  • 定理:一个对象的单位箭头是唯一的;不同对象的单位箭头是不同的。

范畴的理解

  • 对象
    从编程语言的角度来说,一个类(范畴)并不需要一个对象集合。
    一个类的对象集合是由这个类的属性和方法决定的,是编程语言的各种数据类型和类的各种各样的组合形式。
    我们往往用元类型来描述范畴里的对象

  • 态射
    态射就是一个类的方法。
    一个方法有多个输入或者输出,可以简单地认为其源对象或者目标对象是一个对象组合。
    如何理解一个没有输入的静态方法。

态射的种类

单态射(monomorphism) \(\simeq\) 单射(injective)
满态射(epimorphism) \(\simeq\) 满射(surjective)
双态射(bimorphism) = 单态射(monomorphism) + 满态射(epimorphism)
同构(isomorphism) = 双态射(bimorphism) + 存在逆态射
自态射(endomorphism) = (src(f) = tgt(f))
自同构(automorphism) = 自态射(endomorphism) + 同构(isomorphism)
撤回射(retraction) = 存在右逆
部分射(section) = 存在左逆
同态 = 两个数据结构之间满足分配律。\(f(x * y) = f(x) *' f(y)\)

半幺群和预次序集合

  • 幺半群(monoid)
    没有逆元限制的群。
    \((M, \dot, e_M)\),\(\dot\)是一个二元函数,\(e_M\)是一个显著对象。
    1. \(\dot\)是满足结合律:\((a \dot b) \dot c = a \dot (b \dot c), \forall a, b, c \in M\)
    2. \(e_M \dot a = a = a \dot e_M\)
      例如:\((\mathbb{N}, +, 0)\)是一个幺半群。
  • 预次序集合(pre-ordered collection)
    \((M, \leqslant)\),具有:
    1. \(a \leqslant b, b \leqslant c \implies a \leqslant c\),
    2. \(a \leqslant a\)
  • 单调映射(monotone map)
    作用于次序集合上的单调映射\(f: (M, \leqslant) \to (N, \sqsubseteq)\),具有:
    如果\(a \leqslant b, \forall a, b \in M\),则\(f(a) \sqsubseteq f(b)\)。

范畴的例子

  • Mon
    Mon是对象为所有幺半群,箭头为幺半群同态。

  • Ord
    Ord是对象为所有预序组,箭头为他们之间的单调映射。

  • Set
    Set是对象为所有set,箭头为他们之间的任意集合函数。

  • Grp
    Grp是对象为所有group,箭头为group的同态。

  • Ab
    Ab是对象为所有abelian group,箭头为group的同态。

  • Rng
    Rng是对象为所有ring,箭头为ring的同态。

  • 任取一个幺半群\((M, \dot, e_M)\),定义范畴\(\mathcal{M}\)如下:
    1. \(\mathcal{M}\)的唯一的对象是任何实体(不一定是M中的对象),我们称其为\(\star\)
    2. \(\mathcal{M}\)的箭头 \(a : \star \to \star\)就是幺半群中的一个对象a;
    3. 箭头的组合\(a \circ b\)定义为幺半群对象的积\(a \dot b\);
    4. 单位箭头1定义为幺半群的单位元\(e_M\)。

4: 范畴生范畴

  • 对偶(duality)
    对于一个范畴\(\mathcal{C}\)的对偶(dual)\(\mathcal{C}^{op}\),也称为逆范畴、反向范畴(opposite)。满足:
    1. \(ob(\mathcal{C}^{op}) = ob(\mathcal{C})\)
    2. 对于\(\mathcal{C}, f : A \to B\),存在$\mathcal{C}^{op}, f : B \to $
    3. 单位箭头保持不变: \(1_A^{op} = 1_A\)
    4. \(\mathcal{C}^{op}\)的复合定义: \(f \circ^{op} g = g \circ f\)
  • 子范畴(subcategory)
    \(\mathcal{C}\) subcategory \(\mathcal{S}\):
    1. objects: some or all of the \(ob(C)\),
    2. arrows: some or all of the \(hom(C)\),
    3. for each \(o \in ob(S)\), the arrow \(1_o \in hom(S)\)
    4. for any arrow \(f: C \in D, g: D \to E\), the arrow \(g \circ f: C \to E \in hom(S)\)
  • 全子范畴(full subcategory)
    \(\mathcal{C}\) subcategory \(\mathcal{S}\) is a full subcategory, when:
    \(\forall A, B \in ob(S), hom_S(A, B) = hom_C(A, B)\)

  • 积范畴(product category)
  • 等价关系(congruence relation)
  • 商范畴(quotient category)
    商范畴\(\mathcal{C}/\sim = (ob(C), hom(hom(X \to Y)\to \sim class)\)是对一个范畴,按照某种属性进行分类。
    商范畴的态射,我的理解是:C的态射 -> 一个具体的分类属性。
    还有一个理解是:\(A \to B, A \sim B\)
    一个例子:
    If X is the set of all cars, and ~ is the equivalence relation "has the same color as", then one particular equivalence class consists of all green cars. X/~ could be naturally identified with the set of all car colors.

  • 箭范畴(Arrow categories)
    一个范畴\(\mathcal{C}\)的派生箭范畴\(\mathcal{C}^{\to}\),
    \(ob(C)\)是范畴\(\mathcal{C}\)的所有箭头\(hom(C)\)。
    给定一个\(\mathcal{C}^{\to}\)的对象\(f_1, f_2 | f_1 : X_1 \to Y_1, f_2 : X_2 \to Y_2\),
    可以派生一个\(\mathcal{C}^{\to}\)的箭头\(f_1 \to f_2\)是一个匹配\((j, k) | j : X_1 \to Y_1, K : X_2 \to Y_2 \in hom(C)\),

  • 切片范畴(Slice categories)
    一个范畴\(\mathcal{C}\)的派生切片范畴\(\mathcal{C}/I, I \in ob(C)\),
    \((A, f) \in ob(C/I) | A \in ob(C), f : A \to I \in hom(C)\),
    \(j' : (A, f) \to (B, g) \in hom(C/I) | j : A \to B, g \circ j = f, j \in hom(C)\),
    \(1_{(A, f)} = 1_A : A \to A | 1_A \in hom(C)\)
    \(j : (A, f) \to (B, g), k : (B, g) \to (C, h), k \circ j : (A, f) \to (C, h) | k \circ j \in hom(C)\)

5: Kinds of arrows

Monomorphism vs Injective

  • definition: monomorphism
    An arrow \(f : C\to D\) in the category \(\mathcal{C}\) is a monomorphism (monic) if and only if it is left-cancellable..
    left-cancellable - 左可消除。
    i.e. for \(g : B \to C\) and \(h : B \to C\), if \(f \circ g = f \circ h \implies g = h\)

  • Theorem : the monomorphisms in Set are exactly the injective functions
    意味着不是所有的范畴的单射都是单射方法。

  • Theorem : the monomorphisms in Grp are exactly the injective group homomorphisms

Epimorphism vs Surjective

  • definition: epimorphism
    An arrow \(f : C\to D\) in the category \(\mathcal{C}\) is a epimorphism (epic) if and only if it is right-cancellable..
    right-cancellable - 右可消除。
    i.e. for \(g : B \to C\) and \(h : B \to C\), if \(g \circ f = h \circ f \implies g = h\)

  • Theorem : the epimorphisms in Set are exactly the surjective functions
    意味着不是所有的范畴的满射都是满射方法。

  • Theorem : the epimorphisms in Grp are exactly the surjective group epimorphisms

  • Theorem :
    1. 单位箭头总是单射,并且也是满射。
    2. 如果f, g是单射,\(f \circ g\)也是单射。
    3. 如果f, g是满射,\(f \circ g\)也是满射。
    4. 如果\(f \circ g\)也是单射,则g是单射。
    5. 如果\(f \circ g\)也是满射,则f是满射。

逆态射(Inverses)

  • 定义:在范畴\(\mathcal{C}\)中给定一个箭头\(f : C \to D\),
    1. \(g: D \to C\)是f的一个 right inverse,\(\iff f \circ g = 1_D\).
    2. \(g: D \to C\)是f的一个 left inverse,\(\iff f \circ g = 1_C\).
    3. \(g: D \to C\)是f的一个逆,如果g是f的左逆和右逆.

right 和 left只是一个记号,没有方向性的含义。
可以这样想象:\(C \to D\)
C在左边,D在右边。
右逆:是从D出发,逆回到D,\(f \circ g = 1_D\);
左逆:是从C出发,逆回到C,\(g \circ f = 1_C\);

  • 定理:如果一个箭头有左逆和右逆,那么左逆和右逆是同一个,也是原箭头的逆。
    \(r = 1_C \circ r = (s \circ f) \circ r = s \circ (f \circ r) = s \circ 1_D = s\)

  • 定理:
    1. 通常,不是每一个单态射都是右逆;(可能存在元素\(c | c \in C\)在D中没有对应的元素。)
    2. 同样,不是每一个满态射都是左逆。(可能存在元素\(d_1, d_2 | d_1, d_2 \in D\)同时指向\(c | c \in C\)。)
    3. 但是,每一个右逆都是单态射,每一个左逆都是满态射。
  • 定理:
    在Set中,每一个单态射是一个右逆,除了\(\emptyset \to D\)。
    同理,在Set中,推论“每一个满态射是一个左逆”是一个选择公理(Axiom of Choice)的一个版本。

  • 定义:section and retraction
    如果\(g \circ f = 1_C\),f也称为是g的一个部分态射(section);g称为是f的一个撤回态射(retraction)。

  • 定义:split monomorphism and split spimonomorphism
    如果f有一个左逆,那么f是一个拆分单态射;
    如果g有一个右逆,那么g是一个拆分满态射。

同构(Isomorphisms)

  • 同构(isomorphism)
    在范畴里的一个同构是一个有逆箭头。一般用\(\sim \over \longrightarrow\)。

  • 定理
    1. 单位箭头是同构。
    2. 一个同构\(f: C \sim \over \longrightarrow D\),有一个唯一的逆,记为\(f^{-1} : D \sim \over \longrightarrow C\),存在以下性质:
    • \(f^{-1} \circ f = 1_C\)
    • \(f \circ f^{-1} = 1_D\)
    • (f^{-1})^{-1} = f
    • f^{-1}是一个同构
    1. 如果f和g是同构,那么如果\(g \circ f\)如果存在,也是一个同构。它的逆是\(f^{-1} \circ g^{-1}\)。
      比如:双射是一个同构。
  • 定理
    如果f同时是单态射(monic)和拆分满态射(split epic)(或者同时是满态射(epic)和拆分单态射),那么f是一个同构。

  • 定理 15
    如果f和g是具有相同目标对象的单态射箭头。并且存在i,j,有\(f = g \circ i, g = f \circ j\),那么因子i和j是同构态射,并且互为逆。

  • 定义: 平衡的(balanced)
    范畴\(\mathcal{C}\)是平衡的,当且仅当每一个箭头都是一个同构。

同构的对象(Isomorphic objects)

  • 定义: 同构的对象(Isomorphic objects)
    在范畴\(\mathcal{C}\)中,一个同构\(f : C \sim \over \longrightarrow D\),那么对象\(C, D\)称为在范畴\(\mathcal{C}\)中被同构化,记做\(fC \sim \over \longrightarrow D\)。

  • 定理 16
    在范畴\(\mathcal{C}\)中,一个对象之间的同构是一个等价关系。

  • 定理 17
    在范畴\(\mathcal{C}\)中,如果\(f : C \sim \over \longrightarrow D\),那么对于所有的对象\(X \in \matchcal{C}\),在箭头\(C \to X\)和箭头\(C \to \Y\)之间有一对一的对应。同样,存在一对一的对应在箭头\(X \to C\)和箭头\(Y \to C\)之间。

6 起点和终点对象(Initial and terminal objects)

  • 定义: 起点对象(initial object)
    在范畴\(\mathcal{C}\)中,对象\(I\)是起点对象,如果,对于每一个范畴中的对象X,都有一个唯一的箭头\(! : I \to X\),可以记做\(!_x\)。

  • 定义: 终点对象(terminal object)
    在范畴\(\mathcal{C}\)中,对象\(T\)是终点对象,如果,对于每一个范畴中的对象X,都有一个唯一的箭头\(! : X \to T\),可以记做\(!_x\)。

  • 定义: 空对象(null object)
    在范畴\(\mathcal{C}\)中的空对象\(O\),如果,对于\(O\)即是起点对象也是终点对象。

从唯一性到唯一性同构(Uniqueness up to unique isomorphism)

  • 定理:起点对象之间是“从唯一性到唯一性同构”。
    在范畴\(\mathcal{C}\)中,\(I, J\)是起点对象,则存在一个唯一的同构\(f : I \sim \over \longrightarrow J\)。
    对终点对象,亦然。
    如果\(I\)是一个起点对象,有\(f : I \sim \over \longrightarrow J\),则\(J\)也是一个起点对象。

  • 定义:将起点对象记为\(0\),将终点对象记为\(1\)

元素和通用化的元素(Elements and generalized elements)

  • 定义: 元素
    在一个带有终点对象\(1\)范畴\(\mathcal{C}\)中,对象X的一个元素(或者对象X的一个点)是一个箭头\(f: 1 \to X\)。

  • 定义: well-pointed
    假设范畴\(\mathcal{C}\)有一个终点对象,并且假设范畴\(\mathcal{C}\)中的任意对象\(X, Y\),平行箭头\(f, g : X \to Y\),\(f = g\)如果\(f \circ x = g \circ x, \forall x : 1 \to X\),那么范畴\(\mathcal{C}\)被称为(well-pointed)。

  • 定理:拿出两个终点对象\(1\)和\(1'\),定义两个不同类型的X的元素\(f_1 : 1 \to X\)和\(f_2 : 1' \to X\)。范畴\(\mathcal{C}\)对于第一个元素是well-pointed,当且仅当范畴\(\mathcal{C}\)对于第二个元素也是well-pointed。

  • 定义:通用化的元素(generalized elements)
    在范畴\(\mathcal{C}\)中,一个\(X\)对象的(shape S的)通用化元素(generalized element)是一个箭头\(e: S \to X\)

  • 定理:在范畴\(\mathcal{C}\)中,平行箭头是相同的,当且仅当它们在所有的通用化元素上都是相同的。

  • 定理:在范畴\(\mathcal{C}\)中,点元素\(x: 1 \to X\)都是单态射。

    每一个生命都是神圣不可侵犯的。
    每一个生命都只是一粒尘埃。
    我们既可以尊重每个生命,又可以对其随心所欲。就是这么矛盾。

7 乘积(products)

结对模式

  • 定义: pairing schema, pair-objects, pairing function, un-pairing (projection) function
    假设X, Y, O是对象的集合(它们可以是相同的或者是不同的)。
    有\(pr: X, Y \to O\)是一个二元函数(tow-place function),
    同时有\(\pi_1 : O \to X\)和\(\pi_2 : O \to Y\)是one-place function。
    这样\([O, pr, \pi_1, \pi_2]\)形成一个对X、Y的结对模式,当且仅当满足条件:
    \[
    a: \pi_1(pr(x, y)) = x \And \pi_2(pr(x, y)) = y, \forall x \in X, \forall y \in Y \\
    b: pr(\pi_1(o), \pi_2(o)) = o, \forall o \in O
    \]
    这样,O被称为这个结对模式的结对对象(pair-objects)
    \(pr\)为关联的结对函数(pairing function)
    \(\pi_1\)和\(\pi_2\)是反结对函数(映射函数)(un-pairing or projection functions)

  • 定理:
    如果\([O, pr, \pi_1, \pi_2]\)是一个结对模式,那么:
    1. \(pr\)不同的输入对生成不同的结对对象。
    2. \(pr, \pi_1, \pi_2\)都是满射。
  • 定理:
    如果\([O, pr, \pi_1, \pi_2]\)和\([O, pr, \pi'_1, \pi'_2]\)都是X和Y的结对模式,则\(\pi_1 = \pi'_1, \pi_2 = \pi'_2\)。
    如果\([O, pr, \pi_1, \pi_2]\)和\([O, pr', \pi_1, \pi_2]\)都是X和Y的结对模式,则\(\pr = \pr'\)。

  • 定理:
    如果\([O, pr, \pi_1, \pi_2]\)和\([O', pr', \pi'_1, \pi'_2]\)都是X和Y的结对模式,则存在一个唯一的双射(bijection)\(f : O \to O'\),有\(pr'(x, y) = f(pr(x, y)), \forall x \in X, \forall y \in Y\)。

  • 定理
    假设X, Y, O是对象集合,和函数\(\pi_1 : O \to X, \pi_2 : O \to Y\),如果有一个唯一的two-place 函数\(pr: X, Y \to O\),满足条件(a):
    \[
    a: \pi_1(pr(x, y)) = x \And \pi_2(pr(x, y)) = y, \forall x \in X, \forall y \in Y
    \]
    则,\([O, pr, \pi_1, \pi_2]\)满足条件(b),从而形成一个结对模式。

  • 定义: 乘积
    如果X, Y是集合,那么\([O, \pi_1, \pi_2]\)形成一个X和Y的乘积
    这里面:
    O是一个集合,
    \(\pi_1 : O \to X\)是一个函数,
    \(\pi_2 : O \to Y\)是一个函数,
    有一个唯一的two-place函数:\(pr : X, Y \to O\),有\(\pi_1(pr(x, y)) = x \And \pi_2(pr(x, y)) = y, \forall x \in X, \forall y \in Y\)。

二元乘积

  • 定义:二元乘积(binary product)
    在任何一个范畴中,一个对于X和Y的二元乘积\([O, \pi_1, \pi_2]\)是一个对象O和映射箭头\(\pi_1 : O \to X, \pi_2 : O \to Y\)的组合。
    这样对于任何对象\(S\)和箭头\(f_1 : S \to X, f_2 : S \to Y\),总有一个协调箭头(mediating arrow)\(u : S \to O\)形成一个交换图。

  • 定义:楔子(wedge)
    对于 X 和 Y 的一个楔子是一个对象S和一对儿箭头\(f_1 : S \to X, f_2 : S \to Y\)。
    一个楔子\([O, \pi_1, \pi_2]\)是X和Y的乘积,当且仅当,对于X和Y的任何其它楔子\([S, f_1, f_2]\),存在一个唯一的态射\(u : S \to O\)形成一个交换图。

  • 定义:衍生楔子范畴(derived wedge category)
    给定一个范畴\(\mathcal{C}, X, Y \in Ob(\mathcal{C})\),衍生楔子范畴(derived wedge category)\(\mathcal{C}_{W(XY)}\)是:
    对象数据是X和Y的所有楔子\([O, f_1, f_2]\);
    \([O, f_1, f_2]\)和\([O', f'_1, f'_2]\)的箭头是范畴\(\mathcal{C}的箭头\)g : O \to O'$;
    \([O, f_1, f_2]\)单位箭头是\(1_O\);
    箭头组合相同于范畴\(\mathcal{C}\)的箭头组合。

  • 定义:在\(\mathcal{C}\)中,一个X和Y的乘积是衍生范畴\(\mathcal{C}_{W(XY)}\)一个终点对象。

唯一同构

范畴\(\mathcal{C}\)中,对于任意的对象X和Y,乘积不一定存在;如果存在,也不一定唯一。

  • 定义:Uniqueness up to unique isomorphism
    如果\([O, \pi_1, \pi_2]\)和\([O', \pi_1', \pi_2']\)是对象X和Y的乘积,
    那么存在一个唯一的同构\(f: O \sim \over \longrightarrow O'\)联系与影射箭头(有:\(\pi_1' \circ f = \pi_1, \pi_2' \circ f = \pi_2\))。

协乘积(co-product)

  • 定义:范畴化定义楔子的对偶(the duals)通常被称为协楔子。这样一个范畴C的协楔子是协范畴\(C^{op}\)的一个楔子。

  • 定义:协乘积(co-product)
    范畴\(\mathcal{C}\)中,对于任意的对象X和Y,一个二元协乘积\([O, l_1, l_2]\)是:
    一个对象O,
    两个影射箭头:\(l1: X \to O, l2: Y \to O\)。
    这样,对于任何S和箭头\(f_1: X \to S, f_2 : Y \to S\),有一个唯一的协调箭头:\(v : O \to S\)形成一个交换图。
    协乘积记为: \(X \oplus Y\)

8 探索乘积

  • 定理:在有一个终点对象的范畴中
    1. 存在乘积\(1 \times X\)和\(X \times 1\),并且有\(1 \times X \simeq X \simeq X \times 1\)。
    2. \(X \times Y \simeq Y \times X\)
    3. \(X \times ( Y \times Z ) \simeq ( X \times Y ) \times Z\)
  • 定理:有这样的范畴,其中总是存在乘积\(0 \times X\)或者\(X \times 0\),但是这个乘积通常不同构与0。

  • 定理
    如果\(1 \overset{!_{1 \times X}}{\longleftarrow} 1 \times X \overset{i}{\longrightarrow} X\)是一个乘积
    则:\(i\)是一个同构。

  • 定义:调解箭头(mediating arrow)的一种表示
    假设\([O, \pi_1, \pi_2]\)是一个对象X和Y的二元乘积,假设有一个楔子\(X \overset{f_1}{\Longleftarrow} S \overset{f_2}{\longrightarrow} Y\),
    通过一个调解箭头\(u : S \to O\),形成一个交换图。
    这个调解箭头\(u : S \to O\)科表示为\(<f_1, f_2>\)。

  • 定理:
    \(<f_1, f_2> = <g_1, g_2> \implies f_1 = g_1, f_2 = g_2\)。

  • 定理
    对于乘积\([X \times Y, \pi_1, \pi_2]\)和箭头\(u: S \to X \times Y, v: S \to X \times Y\),
    如果有\(\pi_1 \circ u = \pi_1 \circ v, \pi_2 \circ u = \pi_2 \circ v \implies u = v\)。

  • 定义:对角态射(diagonal morphism)
    对于乘积\([X \times X, \pi_1, \pi_2]\)和箭头\(\pi_1: X \times X \to X, \pi_2: X \times X \to X\),
    楔子\(X \overset{1_X}{\Longleftarrow} X \overset{1_X}{\longrightarrow} X\),
    它们对应的调解箭头\(<1_X, 1_X>\)为对角态射,记做\(\delta_x\)。

  • 定理:
    \(q: S \to X \implies \delta_x \circ q = <q, q>\)。

  • 定理:
    \(<f, g> \circ e = <f \circ e, g \circ e>\)

  • 定理:
    给定平行箭头\(f_1: S \to X, f_2 : S \to X, f_1 \neq f_2\),那么至少有4个箭头\(S \to X \times X\)。

两个乘积之间的匹配

  • 定义:两个乘积之间的匹配: \(f \times g\)

\[
f : X \to X' \\
g : Y \to Y' \\
[X \times Y, \pi_1, pi_2] \\
[X' \times Y', \pi'_1, \pi'_2] \\
f \times g : X \times Y \to X' \times Y' \\
\pi'_1 \circ f \times g = f \circ \pi_1 \\
\pi'_2 \circ f \times g = g \circ \pi_2
\]

  • 定理:
    假设\(f: X \to X, g: Y \to Y, o: X \times Y \to Y \times X \{ (x, y) \to (y, x)\}\),
    得出:\((f \times g) \cirs o = (g \times f) \circ o\)。

  • 定理:
    存在双箭头\(f, g: X \to Y\),和乘积\(X \times X, Y \times Y\),
    则:楔子 \(<f, g> = (f \times g) \circ \theta_x\)。

  • 定理 37
    有平行箭头\(f: X \to X', j: X' \to X", g: Y \to Y', k: Y' \to Y"\),
    和乘积\([X \times Y, \pi_1, \pi_2], [X' \times Y', \pi'_1, \pi'_2], [X" \times Y", \pi"_1, \pi"_2]\),
    则:\((j \times k) \circ (f \times g) = (j \circ f) \times (k \circ g)\)。

有限元乘积

  • 定义 44:有限元乘积
    对于\(X_1, \cdots, X_n\)的乘积\(O, \pi_1, \cdots, \pi_n\),
    对于任意的S和箭头\(f_i : S \to X_i\),存在一个唯一的协调箭头\(u: S \to O\),\(f_i = \pi_i \circ u\)

  • 定理 38
    在一个范畴里,对于\(X_1, X_2, X_3\),如果有三元乘积\([O, \pi_1, \pi_2, \pi_3]\)和\(O, \pi'_1, \pi'_2, \pi'_3\),
    那么存在一个唯一的同构\(u: O \simeq O'\)

  • 定理 39
    \((X_1 \times X_2) \times X_3\)形成一个\(X_1, X_2, X_3\)的三元乘积。

  • 定义 45:
    范畴\(\mathcal{C}\)有所有的二元乘积,\(\iff\) 对于任意的两个对象,这个范畴都有乘积。
    范畴\(\mathcal{C}\)有所有的有限元乘积,\(\iff\) 对于任意的n个对象,这个范畴都有n元乘积,\(n \geqslant 0\)。

  • 定理 40
    范畴\(\mathcal{C}\)有所有的有限元乘积,\(\iff\) 这个范畴有一个终点对象,并且有所有的二元乘积。

无限乘积

  • 定义 46:无限乘积(infinite products)
    假设范畴\(\mathcal{C}\)中,对象\(X_j\)可以在一套索引\(J\)中通过j索引,\(J\)是一个无限的。
    如果,对于每个\(X_j\)的乘积\(O\),有\(\pi_j : O \to X_j\),
    同时需要对于任意的对象\(S\)和箭头族\(f_j : S \to X_j\),有\(u : S \to O, \And f_j = \pi_j \circ u, \forall j\)。

  • 定义 47:
    范畴\(\mathcal{C}\)有所有的乘积,\(\iff\) 对于任意的对象\(X_j | j \in J\),这个范畴都有乘积,记做\(\prod_{j \in J}{X_j}\)。

均衡器(Equalizers)

  • 定义 48: 叉子(fork)
    一个叉子(从S通过X到Y),包含箭头\(k: S \to X, f: X \to Y, g: X \to Y, f \circ k = g \circ k\),是一个交换图。

  • 定义 49 均衡器(Equalizer)
    在一个范畴中,有平行箭头\(f, g : X \to Y\),一个均衡器:\(E, e: E \to X\),需要满足以下条件:
    1. \(f \circ e = g \cire e\),也就是说E,X,Y形成一个叉子。
    2. 任意的其它叉子\(S, X, Y, s: S \to X\),存在一个唯一的协调箭头(mediating arrow)\(u: S \to E\)。

均衡器是一个约束(limiting case)

  • 定义 50:叉子范畴
    在范畴\(\mathcal{C}\)中,\(f,g:X \to Y\)形成的叉子\(k: S \to X; g, f: X \to Y\),
    可以得到一个衍生叉子范畴\(\mathcal{C_{F(fg)}}\),如下:
    对象:每个\(S \to X; g, f: X \to Y\)为一个对象;
    箭头:\(u: (S \to \cdots) \to (S' \to \cdots)\)是范畴\(\mathcal{C}\)中的\(u : S \to S'\);
    显而易见有交换图:\(k = k' \circ u\);
    单位箭头:\(1_{(S \to \cdots)} = 1_S\);
    结合律:就是范畴\(\mathcal{C}\)中的结合律。

  • 定义 51:叉子范畴的终点对象
    在一个范畴中,平行箭头\(f, g : X \to Y\)的均衡器:\(E, e: E \to X\),其对应在衍生叉子范畴的对象是一个终点对象。

唯一性

  • 定理 41:均衡器之间存在唯一的同构
    在范畴\(\mathcal{C}\)中,\(f,g:X \to Y\)的均衡器\([E, e], [E', e']\)存在唯一的同构:\(j: E \to E'\),
    形成交换图:\(e = e' \circ j\)。

  • 定理 42:
    如果\([E, e]\)构成一个均衡器,那么\(e\)是一个单态射(monomorphism).

  • 定理 43:
    一个满态射的均衡器是一个同构态射。

协均衡器(co-equalizers)

  • 定义 52: 协叉子(co-fork)
    一个协叉子(从X通过Y到S),包含箭头\(f, g: X \to Y; k: S \to X,; \And k \circ f = k \circ g\)。

  • 定义 53 协均衡器(Co-Equalizer)
    在一个范畴中,有平行箭头\(f, g : X \to Y\),一个协均衡器:\(C, c: Y \to C\),需要满足以下条件:
    1. \(c \circ f = c \cire g\),也就是说C,X,Y形成一个协叉子。
    2. 任意的其它协叉子\(S, X, Y, s: Y \to S\),存在一个唯一的协调箭头(mediating arrow)\(u: C \to S\)。
  • 定义 R
    对于平行箭头\(f,g: X \to Y\),可以引出一个对于对象Y的元素之间的关系R(或者记做\(R_{fg}\))。
    \(yRy'\)意味着\(f(x) = y \And g(x)= y', \exists x \in X\)。
    在一个协叉子中,意味着\(yR_{fg}y'\implies k(y) = k(y')\),有记做\(y \equiv_k y'\)。

  • 定义 R 的最小等价关系(the smallest equivalence relation R) \(R~\)
    \(R^~\)需要包括一个箭头\(c: Y \to C, c(y) = c(y') \iff yRy'\),或者说\(\equiv_c = R~\)。

  • 定理 44
    \(C = Y/R~; c: Y \to C\),c 映射 y 到包含 y 的C元素上。\([C, c]\)构成一个\(f, g\)的协均衡器。
    举例:
    \(Y = [a, a', b, b', d, d'], aRa', bRb', dRd'\)
    \(C = Y/R~ = [[a, a'], [b, b'], [d, d']]\)
    \(c(a) = [a, a']\)

10 限制和协限制(limits and co-limits defined)

锥(cone)

  • 定义 图表(diagram)
    一个基于范畴中的diagram,是一些(或者没有)对象\(D_j\),这些对象可以按照索引\(J\)通过序号\(j\)来定位,和一些(或者没有)\(D_j\)之间的箭头。

  • 定义 54 图表的锥(cone)
    对于一个图表D的锥(cone over a diagram),其构成为\([C, c_j: C \to D_j] | j \in J]\),
    并且对于图表中的任意箭头\(d: D_i \to D_j\),有交换关系\(c_j = d \circ c_i\)。

  • 定义 55 图表的闭包(closure)
    对于一个图表D的闭包(closure)是一个最小的图表,并包含:
    1. D的所有对象和箭头
    2. D所有对象的单位箭头
    3. 如果有两个箭头的可组合的(compos-able),那么要包含它们的组合箭头。
  • 定理 45
    一个闭包是一个子范畴。

  • 定理 46
    如果,\([C, c_j]\)是图表D的锥,则也是图表D的闭包的锥。

极限锥(limit cone)

  • 定义 56 图表的极限锥(limit cone)
    图表D的极限锥(limit cone)\([L, \lambda_j]\)的满足条件:
    对于图表 D 的任意一个锥C,都存在一个唯一的协调箭头\(k: C \to L, \lambda_j \circ k = c_j | \forall j \in J\)。

  • 定理 47
    一个给定图表的所有极限锥之间,一对一之间都存在唯一的同构,这个同构与锥箭头之间形成了交换。

  • 定义 56 派生范畴:图表的锥范畴
    一个范畴\(\mathcal{C}\)中,对于图表D,可以派生含有图表D上所有锥的范畴,记做\(\mathcal{C}_{C(D)}\):
    1. 对象:所有锥\([C, c]\)
    2. 箭头:任意C之间的箭头\(k: C \to C'\),并满足\(c'_j \circ k = c_j, j \in J\)
    3. 单位对象:\(1_C\)
    4. 组合关系:箭头的原组合关系。
  • 定理 58
    一个范畴\(\mathcal{C}\)中,图表D的极限锥是图表的锥范畴\(\mathcal{C}_{C(D)}\)的终点对象。

  • 定理 48
    一个范畴\(\mathcal{C}\)中,\([L, \lambda]\)是图表D的极限锥,
    \([L', \lambda']\)是图表D的锥,并且通过\(f: L' \to L\)构成一个同构,
    则:\([L', \lambda']\)是图表D的极限锥。

  • 定理 49 TBD

  • 定理 50
    一个范畴\(\mathcal{C}\)有一个起点对象,当且仅当范畴\(\mathcal{C}\)作为一个图表有一个极限锥。

  • 定义 59 极限对象
    对于一个图表D的一个极限锥,我们将位于这个极限锥的顶点的极限对象,自作\(\lim_{\rightarrow j} D_j\)。

协极限(colimits)

  • 定义 60: 协锥(co-cone)
    一个图表 D 的协锥C,有:
    1. \(c_j: D_j \to C, j \in J\)
    2. \(c_k = c_l \circ d, \forall d: D_k \to D_l\)

撤回(Pullbacks)

  • 定义 61:撤回,撤回正方形(pullback square)
    对于一个角图(corner diagram)的一个极限(limit)\([L, \lambda_1: L \to D_1, \lambda_2: L \to D_2]\)是一个撤回
    一个角图和极限组成一个撤回正方形(pullback square)
    corner diagram: \(D_1, D_2, D_3, d: D_1 \to D_3, e: D_2 \to D_3\)。

  • 定理 51
    撤回一个单态射,产生一个单态射。

  • 定理 52
    \(f: X \to Y\)是一个单态射,当且仅当下面是一个撤回正方形:
    \(1_X: X \to X, f: X \to Y\)
    \(1_X: X \to X, f: X \to Y\)

  • 定理 53
    一个顶点为Z的角的撤回是商范畴\(\mathcal{C}/Z\)的一个乘积。

推出(pushout)

  • 定义 62:一个楔子图的极限是一个推出(pushout)

11 极限的存在性

  • 定义 63:一个包含所有有限极限的范畴,被称为有限地完整。
    有限极限: 对于有限图D(任意图包含D,并拥有有限的索引J)。

12 子对象(sub-object)

13 指数(Exponential)

14 组对象,自然数对象

15 函子(Functor)

16 范畴的范畴(Categories of categories)

17 函子和极限(functors and limits)

18 同态函子(Hom-functors)

19 函子和逗号范畴

20 自然的同构(Natural isomorphisms)

21 自然的变形(Natural transformations)

22 函子范畴(Functor categories)

23 范畴的等价性(Equivalent categories)

24 Yoneda植入(The Yoneda embedding)

25 Yoneda推论(The Yoneda Lemma)

26 可表达和统一元素(Representables and universal elements)

27 Galois连接(Galois connections)

28 伴随的介绍(Adjoints introduced)

  • 定义 125 伴随(adjoint)
    范畴\(\mathcal{A}, \mathcal{B}\),和函子\(F: \mathcal{B} \to B, G: \mathcal{B} \to \mathcal{A}\)。
    则\(F\)是\(G\)的左伴随,则\(G\)是\(F\)的右伴随,记做:\(F \dashv G\)。
    前提条件: \(\mathcal{B}(F(A), B) \simeq \mathcal{A}(A, G(B))\)。

29 伴随的更多探索(Adjoints further explored)

30 伴随函子和极限(Adjoints functors and limits)

符号

Isomorphism: \(\simeq\)
iff: \(\iff\)

各种理解

  • 结合律的理解
    结合律意味着可以在任何一个计算点开始计算。

  • 如何证明单射(injective)
    通过假设两个元素e, e'的射结果相同,既\(f(e) = f(e')\),如果可以推导出\(e = e'\),则\(f\)是一个单射。

  • 如何证明满射(surjective)
    对于任何\(b \in B\),\(f(a) = b, \exists a \in A\)。

  • 如何证明同构\(\simeq\)(isomorphism)
    对于任何\(b \in B\),存在\(f(a) = b, a \in A\)。

  • 交换图
    各种表达:commuting with arrows, form a diagram commuting, triangle commutes, etc.
    其中的含义是:从对象 A 到对象B存在两个相等的路径。

  • 协调箭头(mediate arrows)
    一种常见的交换图形式。总是以这样的形式出现:
    有一组源对象和一个目标对象,存在:\([S_j, s_j: S \to T], j \in J\),
    有一个对象\([M, m: M \to T]\),对于每个源对象,存在唯一的:
    \(k: S_j \to M; \And m \circ k = s_j\)。
    \(k\)就是协调箭头。
    这里,似乎说明了\([M, m]\)有一种特性,存在一个等价的交换路径。

冯诺依曼(Von Neumann)的自然数定义

\[
0 = \emptyset \\
1 = \{ \emptyset \} \\
2 = \{ \emptyset, \{ \emptyset \} \} \\
3 = \{ \emptyset, \{ \emptyset \}, \{ \emptyset, \{ \emptyset \} \} \} \\
\cdots \\
n + 1 = n \cup \{ n \}
\]

参照

  • Category Theory A Gentle Introduction by Peter Smith (University of Cambridge)
  • Wikipedia
上一篇:MapReduce (hive表SequenceFile的结果做输入)、MultipleOutputs和Reduce端迭代iterable的一些说明


下一篇:Java基础之 数组详解