CTFP Ch05

概要

摘录

• We are defined by our relationship.

• We can only single out a object in a category by describing the relationship between it and others.

• universial construction: defined object by describing its pattern of relationships with other objects. two step

  • define a pattern
  • define the order of the objs which match the pattern, pick the smallest or the biggest one.

• Several Kind of Objects

  • Initial Ojbect:

    • single object in the category, every obj in the category should must have and only have one arrow from the object. notice that the single is not in the definition of initial object, we describe it from the relationship outside the object, while single is the describtion inside the object.
    • it may not exists.
    • the initial object is the object that has one and only one morphism going to any object in the category
    • there maybe not only one initial objects.
    • e.g:
      • in the category of sets and functions: initial object is the empty set.
      • Void in Haskell, the morphism is absurc :: Void -> a

  • Terminal Object:

    • Single object in the category with one and only one morphism coming to it from the other object in the category.
    • e.g
      • unit in Haskell; void in C++

  • Products

    • pre knowledge: all we can say about product is just two projection function which extract different components of it
    • product pattern c is defined by the projection: $$ p :: c \to a \\ q :: c \to b $$ and we have many cs who satify such pattern. so, we should give them a way to ranking.
    • ranking: if c' and c satify the pattern defined above, we say c is prioritized than c', if there is a morphism m, satify that $$ p' :: c' \to a, q' :: c' \to b \\ p :: c \to a, q :: c \to b \\ m :: c' \to c \\ p' = p . m, q' = q . m $$
    • definition: A product of a and b is the object c equipped with two projection such that for any object c' equipped with two projection there must be a unique morphism from c' to c that factorizes the projection of c'.
    • factorization: $$ factorization :: (c \to a) -> (c \to b) -> (c \to (a, b)) \\ factorization\ p\ q = \ x -> (p x, q x) $$ a object with the factorization function will get the Cardesian product of a and b, so the object c is the product of a and b;

  • Coproducts: which is the reverse version of product

    • pattern: object c equipped with two injection $$ i :: a \to c \\ j :: b \to c $$
    • ranking: for two object c and c' who satify the pattern above, if there is a morphism from c to c' which satify $$ i :: a \to c, j :: b \to c \\ i' :: a \to c', j' :: b \to c' \\ m :: c \to c' \\ i' :: m . i, j' :: m . j $$ then c is precedence than c'.

• Duality:

  • with a category on hand, you can construct another category by keeping all the objs and reversing the arrow bewteen objs. Suppose that the original category is C, and we can define the opposite category $C^{op}$ by just reversing the arrow. That is for the original morphism $ f :: a \to b , g :: b \to c $ and their composition $ h :: a \to c $ with $ h = g \cdot f $, by reversing the arrow we have $ f^{op} :: b \to a, g^{op} :: c \to b, h^{op} :: c \to a $ with $ h^{op} :: f^{op} \cdot g^{op} $, put them all together. $$ f :: a \to b, g :: b \to c, h :: a \to c = g \cdot f \\ f^{op} :: b \to a, g^{op} :: c \to b, h^{op} :: c \to a = f^{op} \cdot g^{op} $$

• Isomorphisms

  • isomorphic objects look the same, it means that every part of one object coresponds to ssome part of another object in a one-to-one mapping.
  • isomorphic from morphism view: an isomorphism is an ivertible morphism, we can understand it in terms of composition and identity. if f is the invertion of g, then: $$ f . g = id_A \\ g . f = id_B $$

• Asymmetry:

  • initial object vs terminal object:

  • product vs coproduct

  • product with terminal object ==> multiply

  • coproduct with initial object ==> sum

  • it's the singleton set make the difference between product and coproduct; remember the pattern and the ranking of product, if we choose unit type as the candidate for the product pattern, for the reason that product type is the universal one, there must be a morphism from unit type to product type and the morphism will choose a particular pair of the product type. Beside, that two projection equipped with the unit type could be factorizated by m: $$ p = fst . m \\ q = snd . m $$ if you apply () to both side you wiil get $$ p () = fst ( m () ) \\ q () = snd ( m () ) $$ the equalation above has a nice interpretation: the element picked by p from the first set is the first component of the pair picked by m from the product, the same as q and the element picked from the second set.

  • while there is no such interpretation for coproduct, if you choose unit as another candidate, there is no such nice interpretation. you may say we should choose initial object as our candidate, but don't forget morphism could only come from but not go into initial object.

  • it's not the intrinsic property of sets but the property of function who make such difference and which we use as morphism in Set. Functions are asymmetric

  • The asymmetric of function shows in two aspect:

    • the asymmetric between domain and codomain:

      1. domain: for every element in the domain, the function should have definition on it.
      2. codomain: while for codomain, there is not such restriction. Any domain that containes all the value a function will output could be the codomain of that function.
      3. There are two situiations: 3.1 embed: if domain is smaller than codomain, then it's called embed; 3.2 collapse: if the codomain is smalle than domain, then it's called collapse;

    • the asymmetric arise from the mapping between input and output:

      1. the definition of function allow the situiation that two values from domain are mapped into the same value in the same codomain; but forbidded that two values in the codomain are mapped by the same value in domain.
      2. surjective: for every value in codomain, there must a value from domain map to;
      3. injective: there are no two value in domain mapped into the same value in codomain

  • the relationship between embed, collapse, surjective and injective

    • if surjective, there is no embed
    • if injective, there is no collapse

随笔

category屏蔽调用obj内部的细节,我们只能够从obj与obj之间的关系来描述一些特定的对象,由此引出了category的universal construction用于勾勒出某些特定的obj. 该方法有两个步骤: 1. 给定某个特别的pattern; 2. 在符合pattern的对象中定义某种ranking, 选出极值. 随后给出了Set Category中几种对象的构造过程， 包括了: 1. initial object; 2. terminal object; 3. product; 4. coproduct; 并阐述了对偶构造的方法, 指出了initial object 与terminal object 以及 product与coproduct之间的duality; 同时, 由于initial object以及terminal object 并不是唯一的, 但是在isomorphism的意义上是唯一的,也就是两个对象之间存在这一一映射的关系, 并且在identity以及composition的角度上面解释了isomorphic的意义; 随后,本章阐述了虽然initial obj与terminal obj 以及 product与coproduct可以通过reverse category中的arrow得来，但是得到的obj的行为表现却是非对称的, 这种非对称来自于几个方面：

1. unit 在 product中的作用
2. 函数在定义域以及值域上面定义要求的不一致；
3. 函数在单射, 满射上面的要求不一样