Notes from Book: Category Theory for the Sciences - David I. Spivak

3289 words · 16 min read

Note: All figures are taken from the book.

ch01: Introduction

~/Dropbox/public/img/ss-23.png
ontology logs: ologs
  to give structure to the kinds of ideas that are often communicated in graphics
  it encompasses a database schema
category theory
  communication of ideas between different fields in mathematics
  different branches can be formalized into categories
  categories are connected by functors
transfer of proofs
  theorems proven in one category
  transferred through a functor to yield proofs in another category
functor is like
  conductor of mathematical truth
use in scientific models
  study of basic building blocks
  certain structures show up again and again
    vector spaces
    also hierarchies, daat models, self-similarity

1.1 A brief history of category theory

invented in early 40s by Samuel Eilenberg and Saunders Mac Lane
  to bridge topology and algebra
  there were already links (such as cohomology theory)
  but they compared different links with one another precisely
  first: extract fundamental nature of these two fields
    ideas fit to other mathematical disciplines as well
first use: clarifying lanugage for existing mathematical ideas
  1957 Grothendieck used it to build new mathematical fields: new cohomology theories
    that made insight into behavior of algebraic equations
Bull Lawvere: foundation for all mathematical thought
  19th century: foundation was set theory
  Lawvere showed category of sets is one category but not the center of mathematical universe
1980 Joachim Lambek: types and programs form a specific kind of category
  new semantics on how programs combine to create other programs
Eugenio Moggi: brought monads into programming
Daniel Kan, Andre Joyal
language of choice for algebra
main use: bridge

1.2 Intention of this book

applied mathematics is much smaller than 
  applicable mathematics
abstract conceps can be communicated to scientists
journals: substantial experties
  it is impossible to read a methods section and repeat the experiment
first goal: reusable methodologies can be formalized
  ct is incredibly efficient
    as a language for experimental design patterns
    researches has ability to think about models that is impossible without it
    forces a person to clarify her assumptions
  value: conceptual chaos is a major problem
    creativity demands clarity of thinking
      how pieces fit together

1.3 What is requested from the student

only way to learn mathematics: doing exercises

1.4 Category theory references

most books: for mathematicians or computer scientists

ch02 The Category of Sets

theory of sets
  invented as a foundation for all mathematics
  serves as a basis to build intuition about categories
this chapter
  sets, functions, commutative diagrams
  ologs
category of sets: Set

2.1 Sets and functions

[a thing] is put into -> [a bin]

2.1.1 Sets

a set X: a collection of elements x ∈ X
  we can tell if x = x' or not
notation 2.1.1.1. symbol ∅ denotes set with no elements, also {}
  N: natural numbers
  Z: natural numbers annd their negatives
if A and B are sets
  we say A is a subset of B, also A ⊆ B
    if every element of A is an element of B
for any set A
  ∅ ⊆ A and A ⊆ A
set-builder notation to denote subsets
  ex: set of even integers: {n ∈ Z| n is even}
  ex: set of integers greater than 2:
    {n ∈ Z | n > 2}
symbol ∃: there exists
  ex: set of even integers
    {n ∈ Z | n is even} = {n ∈ Z | ∃ m ∈ Z st 2m = n}
symbol ∃!: there exists a unique
symbol ∀: for all
colon equals notation ":=": define x to be y

2.1.2 Functions

if X and Y are sets
  then a function f from X to Y
  denoted f:X->Y
  is a mapping that sends each element x ∈ X to an element of Y denoted f(x) ∈ Y
  X: domain of function f
  Y: codomain of f
slogan 2.1.2.1
  given a function f: X -> Y
  we say: 
    X: a set of things
    Y: a set of bins
  function tells us in which bin to put each thing
ex 2.1.2.4:
  suppose 
    X is a set 
    X' ⊆ X is a subset
  consider function: X' -> X
    given by sending every element of X' to itself
  notation:
    i:X'⊆ X
      i is the name of the associated function
image of f:
  given f:X->Y
  elements of Y that have at least one arrow pointing to them: are in the image of f
  im(f) := {y∈Y| ∃ x ∈ X st f(x) = y}
image of f is always a subset of its codomain
  im(f) ⊆ Y
composable:
  given:
    f: X -> Y
    g: Y -> Z
    ie: codomain of f is domain of g
  then: f and g are composable
    [X] f-> [Y] g-> [Z]
  denoted:
    composition of f and g
    g · f: X -> Z
image of set A:
  if A ⊆ X
    then: i: A -> X
  given f: X -> Y
    then: we can compose
      [A] i-> [X] f-> [Y]
      f · i: A -> Y
  image of this function is denoted
    f(A) := im(f·i)
notation 2.1.2.9: represents
  let 
    X be a set
    x ∈ X an element
  there is a function {😃 } -> X
    that sends 😃  → x
  say:
    this function represents x ∈ X
  denote:
    x: {😃 } -> X
ex 2.1.2.10
  let
    X a set
    x ∈ X an element
    x:{😃 } -> X function representing it
  given f:X->Y
  what is f·x?
    function {😃 } -> Y
      that sends 😃  to f(x)
    it represents the element f(x)
Remark 2.1.2.11
  g·f(a) means g(f(a))
    do g to whatever results from doing f to a
  diagrammatic order:
    another way to write composition
    f;g: A -> C
      means: "do f, then do g"
  given an element a ∈ A
    represented by a:{😃 } -> A
    we have an element:
      a;f;g
Hom_{Set}(X,Y)
  let: X,Y sets
  set of functions X->Y
    denoted as: Hom_{Set}(X,Y)
  note:
    two functions f,g:X->Y are equal
      iff ∀ x ∈ X, f(x) = g(x)
ex 2.1.2.12
  let A = {1,2,3}, B = {x,y}
  how many elements does Hom_{Set}(A,B) have?
identity function on X
  id_X: X -> X
  st ∀ x ∈ X, id_X(x) = x
definition 2.1.2.14: isomorphism
  let X, Y be sets
  function f:X->Y is an isomorphism
    denoted [f:X] ≅-> [Y]
  if ∃ g:Y->X st.
    g·f = id_X and f·g = id_Y
  we also say
    f is invertible
    g is the inverse of f
    X and Y are isomorphic sets
    X ≅ Y
    one-to-one correspondence
application 2.1.2.16
  isomorphism between Nuc_{DNA} nucleotides in DNA and Nuc_{RNA} nucleotides in RNA
  boths sets have 4 elements
    so there are 24 different isomorphisms
    only one is useful in biology
  another isomorphism: Nuc_{DNA} ≅ {A,C,G,T} and Nuc_{RNA} ≅ {A,C,G,U}
    so we can use those letters as short form for nucleotides
  convenient isomorphism [Nuc_{DNA}] ≅-> [Nuc_{RNA}] is given by RNA transcription:
    A→U, C→G, G→C, T→A
  another isomorphism: [Nuc_{DNA}] ≅-> [Nuc_{DNA}] the matching in double helix, given by:
    A→T, C→G, G→C, T→A
  protein production:
    a function from the set of 3-nucleotide sequences to the set of amino acids
    it cannot be isomorphism because 
      4^3=64 triplets of RNA nucleotides
      but only 21 eukaryotic amino acids
proposition 2.1.2.18
  1. any set A is isomorphic to itself
  2. if A is isomorphic to B, then B is isomorphic to A
  3. if A ≅ B and B ≅ C, then A ≅ C
ex 2.1.2.19
  even if two sets are isomorphic, they cannot be treated as the same
  to be treated as same,
    we need to have in hand a specified isomorphism
ex 2.1.2.20
  find A st for any set X, there is an isomorphism of sets
    X ≅ Hom_{Set}(A,X)
notation 2.1.2.21
  ∀ n ∈ N, define a set ṉ := {1,2,3,...,n}
  ṉ the numeral set of size n 
  ex:
    2_ = {1,2}, 1_ = {1}, 0_ = ∅ 
  let A be any set
  function f:ṉ->A can be written as a length n sequence:
    f = (f(1),f(2),...f(n))
  called: sequence notation for f
ex 2.1.2.22
  a. A = {a,b,c 2017-01-28}. 
    if f:10_->A is in sequence notation as (a,b,c,c,b,a,d,d,a,b)
    what is f(4)?
definition 2.1.2.23: cardinality of finite sets
  A a set. n ∈ N 
  A has cardinality n
  denoted
    |A| = n
  if there exists an isomorphism of sets A ≅ ṉ
  if A has cardinality n, then A is finite
  other wise A is infinite
  we write |A| ≥ ∞ 
proposition 2.1.2.25
  if there is an isomorphism of sets f:A->B
    then |A| = |B|

2.2 Commutative diagrams

ex:
  [A] f-> [B]
  [A] h-> [C]
  [B] g-> [C]
  we say:
    a diagram of sets if A,B,C is a set and each of f,g,h is a function
    this diagram commutes if g·f=h
    we refer to it as a commutative triangle of sets, or as a commutative diagram of sets
application 2.2.1.1
  biology:
    function from DNA to RNA
    function from RNA to amino acids
  we say: translation from DNA to amino acids
    following commutative diagram is this fact:
      [DNA] -> [RNA]
      [RNA] -> [AA]
      [DNA] -> [AA]
consider:
  [A] f-> [B]
  [A] h-> [C]
  [B] g-> [D]
  [C] i-> [D]
  we say:
    diagram of sets if 
      each A,B,C,D is a set
      each f,g,h,i is a function
    this diagram commutes if
      g·f = i·h
      then we refer: commutative square of sets
      or commutative diagram of sets
application 2.2.1.2
  given a system S
  there are two mathematical approaches:
    f:S->A
    g:S->B
  either results in a prediction:
    f':A->P
    g':B->P
  diagram commutes = both approaches give the same result

2.3 Ologs

ologs
  serve as a bridge between mathematics and various conceptual landscapes
  ex:
    [A| arginine] is-> [D| an amino acid found in dairy]
    [A] has -> [E| an electrically charged side chain]
    [D] is -> [X| an amino acid]
    [A] is -> [X]
    [E] is -> [R| a side chain]
    [X] has -> [R]
    [X] has -> [N| an amine group]
    [X] has -> [C| a carboxylic acid]

2.3.1 Types

type: an abstract concept
  represented as a box
    containing a singular indefinite noun phrase
      [a man]
      [an automobile]
      [a pair (a,w) where w is a woman and a is an automobile]
    each box represents a type of thing
    label on that box: each example of that class
      thus: [a man] is not a single man, but the set of men. each example of which is called [a man]
2.3.1.1 Types with compound structures
compound structures: composed of smaller units
ex
  [a man and a woman]
  [a food portion f and a child c such that c ate all of f]
good practice to declare variables in a compound type
  ex
    [a man and a woman]
    [a pair (m), where m is a man and w is a woman]
rules of good practice 2.3.1.2
  a type is presented as a text box
  text should
    begin with word "a"
    refer to a distinction made by the author
    refer to a distinction for which instances can be documented
    use common name for each instance
    declare all variables in compound structures
  nicknames:
    [Steve] stands as a nickname for [a thing classified as Steve]
    [arginine] for [a molecule of arginine]

2.3.2 Aspects

aspect of a thing x
  a particular way in which x can be regarded
ex
  a woman can be regarded as a person
    being a person is an aspect
    [a woman] is-> [a person]
  a molecule has a molecular mass
    having a molecular mass is an aspect
    [a molecule] has a molecular mass-> [a positive real number]
aspect: means function
  f:A->B
  domain A: the thing we are measuring
  codomain B: set of possible answers of the measurement
ex
  [a woman] is-> [a person]
  domain: set of women (3 billion elements)
  codomain: set of persons (6 bil elements)
  no woman points to two different people nor to zero people
    so this is a function
ex
  [a molecule] has a molecular mass-> [a positive real number]
  domain: set of molecules
  codomain: positive real numbers
  for each molecule: there is a corresponding positive real number
  no molecule has two different masses, nor no mass
2.3.2.1 Invalid aspects
to be valid: aspect must be a functional relationship
ex:
  [a person] has-> [a child]
  a person may have no children, or multiple children. hence not a function
2.3.2.4 Reading aspects and paths as English phrases
each arrow (aspect) [X] f-> [Y]
  read by order: 
    ex: [a book] has as first author -> [a perso]
      a book has as first author a person
remark 2.3.2.5
  [a book] has as author -> [a person]
    not valid
    because it is not functional
if it is obvious, you can drop labels on arrows
  ex:
    [A| a pair (x,y) where x and y are integers] x -> [B| an integer]
    [A] y -> [B'| an integer]
  label x is as a nickname for the full name "yields as the value of x"
opt: use "which" before each arrow label
2.3.2.6 Converting nonfunctional relationships to aspects
ex:
  [a person] owns -> [a car]
    invalid
  valid form:
    [A| a pair (p,c), where p is a person, c is a car, and p owns c] p -> [a person]
    [A] c -> [a car]

2.3.3 Facts

fact: path equivalences in an olog
  this is what makes category theory so powerful
path in an olog: head-to-tail sequence of arrows
  number of arrows: length of the path
  B0: source
  Bn: target
two paths are equivalent:
  triangle in olog commutes
    A -> B -> C
    A -> C
  commutative diagrams
  ex:
    [A| a person] has as parents -> [B| a pair (w,m), w: woman, m: man]
    [B] yields as w -> [C| a woman]
    [A] has as mother -> [C]
notation: a diagram commutes:
  A[f,g] ≅ A[h,i]
  means:
    starting from A, 
      doing f, then g
      is equivalent to
      doing h, then i
ex:
  [A| a DNA sequence] is transcribed to -> [B| an RNA sequence]
  [B] is translated to -> [C| a protein]
  [A] codes for -> [C]
ex 2.3.3.1:
  [a child] has -> [a mother]
  [a mother] is -> [a person]
  [a child] is -> [a person]
  this triangle doesn't commute
  if they would, we would say: "a child and its mother are the same person"
ex 2.3.3.2:
  [a person] has as father -> [a man]
  [a man] lives in -> [a city]
  [a person] lives in -> [a city]
  noncommuting diagram
2.3.3.4 A formula for writing facts as English
paths: P, Q
ex 2.3.3.5:
  consider olog
    [A|a person]
    [B| an address]
    [C| a city]
    [A] has -> [B]
    [B] is in -> [C]
    [A] lives in -> [C]
  to put this diagram commutes into English:
    two paths:
      F="a person has an address which is in a city"
      G="a person lives in a city"
      source of both: s="a person"
      target of both: t="a city"
    write:
      given x, a person, consider the following.
      We know that x is a person,
      who has an address, which is in a city,
      that we call P(x).
      We also know that x is a person,
      who lives in a city
      that we call Q(x).
      Fact: Whenever x is a person, we will have P(x) = Q(x).
    more concisely:
      A person x has an address, which is in a city, and this is the city x lives in.
general:
  paths: P,Q
    P: [a0=s] f1-> [a1] f2-> [a2] ... fm -> [am=t]
    Q: [b0=s] g1-> [b1] g2-> [b2] ... gm -> [bm=t]
  every part l (ie. every box and every arrow) has an English phrase
    denoted: <<l>>
  englished as:
    Given x,<<s>> consider the following.
    We know that x is <<s>>,
    which <<f1>><<a1>>, which <<f2>><<a2>>,..., which <<fm>><<t>>,
    that we call P(x).
    We also know that x is <<s>>,
    which <<g1>><<b1>>, which <<g2>><<b2>>,..., which <<gm>><<t>>,
    that we call Q(x).
    Fact: Whenever x is <<s>>, we will have P(x)=Q(x).
ex 2.3.3.6:
  olog
    [OLP| an operational landline phone]
    [N| a phone number]
    [C| an area code]
    [P| a physical phone]
    [R| a region]
    [OLP] is assigned -> [N]
    [N] has -> [C]
    [C] corresponds to -> [R]
    [OLP] is -> [P]
    [P] is currently located in -> [R]
  short form:
    [OLP] is assigned -> [N] has -> [C] corresponds to -> [R]
    [OLP] is -> [P] is currently located in -> [R]
2.3.3.8 Images
ex:
  set of mothers is the image of the "has as mother" function
    [P|a person]
    [P'|a person]
    [M|a mother]
    [P] has as mother -> [P']
    [P] has -> [M] is -> [P']

ch03: Fundamental Considerations in Set

3.1 Products and coproducts

3.1.1 Products

definition 3.1.1.1
  product of X and Y
    denoted X ⨯ Y 
    is set of ordered pairs (x,y), x ∈ X and y ∈ Y
  X ⨯ Y = {(x,y)| x ∈ X, y ∈ Y}
there are two natural projection functions:
  π1: X ⨯ Y -> X
  π2: X ⨯ Y -> Y
  olog
    [X⨯Y] π1 -> [X]
    [X⨯Y] π2 -> [Y]
ex 3.1.1.8: 
  let
    +: Z ⨯ Z -> Z addition function
    ·: Z ⨯ Z -> Z multiplication function
3.1.1.9 Universal property for products

proposition 3.1.1.10 
  /Users/mertnuhoglu/Dropbox/public/img/ss-25.png
  for f:A->X and g:A->Y
  ∃ a unique function A -> X ⨯ Y
  st the following diagram commutes:
    [X ⨯ Y] π1 -> [X]
    [X ⨯ Y] π2 -> [Y]
    [A] f -> [X]
    [A] g -> [Y]
    [A] <f,g> -> [X ⨯ Y] 
  we say:
    this function is induced by f and g
    denoted:
      <f,g>: A -> X ⨯ Y
      <f,g>(a) = (f(a),g(a))
    that is:
      π1 · <f,g> = f
      π2 · <f,g> = g
      <f,g> is the only function for which this is so
ex 3.1.1.13
  for every set A there is some relationship between the following three sets:
    Hom_{Set}(A,X)
    Hom_{Set}(A,Y)
    Hom_{Set}(A,X⨯Y)
  solution
    there is an isomorphism
    Hom_{Set}(A,X⨯Y) ≅ -> Hom_{Set}(A,X) ⨯ Hom_{Set}(A,Y)
  ex
    height function: from set P of people to Z of integers
    name function: from P to S of strings
    so, we have 
      an element of Hom_{Set}(P,Z) and 
      an element of Hom_{Set}(P,S) 
    from this we get an element of:
      Hom_{Set}(P,Z) ⨯ Hom_{Set}(P,S)
    ie: two pieces of information combined
      we pack height and name into a single datum
        ie. an element of Z ⨯ S
ex 3.1.1.14
  let:
    π1: X ⨯ Y -> X
    π2: X ⨯ Y -> Y
    p1: Y ⨯ X -> Y
    p2: Y ⨯ X -> X
  construct swap map:
    s: X ⨯ Y -> Y ⨯ X
    write s in terms of π, p, ·, <, >
  solution:
    s = <π2,π1>
3.1.1.16 Ologging products
ex 3.1.1.17

3.1.2 Coproducts

definition 3.1.2.1
  coproduct of X and Y 
  denoted X ▄ Y
  is defined as disjoint union of X and Y
    ie. the set for which an element is either from X or Y
  two natural inclusion functions:
    i1: X -> X ▄ Y
    i2: Y -> X ▄ Y
ex 3.1.2.2
  coproduct of X := {a,b,c} and Y := {1,2}
    X ▄ Y ≅ {a,b,c,1,2}
coproduct of X and itself
  X ▄ X ≅ {a1,b1,c1,a2,b2,c2}
names of the elements in X ▄ Y are not important
  inclusion maps i1,i2 are important
  which ensure we know where each element is from
ex 3.1.2.3: Airplane seats
  X: an economy-class seat in an airplane
  Y: a first-class seat in an airplane
  X▄Y: a seat in an airplane
  [X] is -> [X▄Y]
  [Y] is -> [X▄Y]
@mine
  coproduct is inheritance is-a relationship
  product is join table
ex 3.1.2.4
  is [a phone] is coproduct of [a cell phone] and [a landline phone]?
  solution
    if there is no phone other than a cell phone and landline phone, yes. if not, no
ex 3.1.2.5: disjoint union of dots
  /Users/mertnuhoglu/Dropbox/public/img/ss-26.png

3.1.2.6 Universal property for coproducts

proposition 3.1.2.7
  ~/Dropbox/public/img/ss-27.png
  the following diagram commutes:
    X i1 -> X ▄ Y
    Y i2 -> X ▄ Y
    X f -> A
    Y g -> A
    X ▄ Y {f g -> A
  this function is induced by f and g
  ie. we have
    {f g · i1 = f
    {f g · i2 = g
slogan 3.1.2.8
  any time behavior is determined by cases, there is a coproduct involved
why two-line symbol {
  because this is case notation

 Tech    23 Nov, 2017

Any work (images, writings, presentations, ideas or whatever) which I own is always provided under
Creative Commons License Creative Commons Attribution-Share Alike 3.0 License

Mert Nuhoglu is a Trabzon-born programmer and data scientist.

You may also like...