Notes from Book: Conceptual Mathematics A First Introduction to Categories - William Lawvere

3588 words · 17 min read


  not adding new items to collection
  but how keep collection in order
    how to find appropriate tool when needed
  general concepts that cut across
    artificial boundaries dividing
      arithmetic, logic, geometry etc.
  little about: how to do specialized discussions
    but on how to decide what to do in what order

ch01: Galileo and multiplication of objects

1. Introduction

basic notion:  category
  which underlies all the others
  a mathematical universe

2. Galileo and the flight of a bird


  a map from time to space
why did galileo focus on vertical motion:
  space = plane x line
  two maps
    shadow map:
      sun is direvtly overhead
      for each point in space
      you get a shadow point on plane
    level map:
      a pole stuck into ground
      for each point in space there is a corresponding point on the line (at the same level)
    together we have:
      [space] level -> [line]
      [space] shadow -> [plane]
    they reduce each problem about space to 2 simpler problems
      one for plane
      one for line
    suppose you keep all positions over time too
      you have
        [time] flight of a bird -> [space]
      we can then get:
        [time] flight of a bird -> [space]
        [space] level -> [line]
        [space] shadow -> [plane]
      we can get these two maps:
        [time] level of flight of bird -> [line]
        [time] shadow of flight of bird -> [plane]
      now space disappeared from the picture
    galileo's discovery:
      from two simpler motions
        recapture motion in space
        if simpler motions are continous
          motion in space is continous too
      [space] level -> [line]
      [space] shadow -> [plane]
      is equivalent to:
      space = plane x line

3. Other examples of multiplication of objects


restaurant has two lists
  option for first course
  option for second course
  a meal involves one item from each list
    [meals] -> [1st course]
    [meals] -> [2nd course]
  similar to Galileo's diagram:
    [space] level -> [line]
    [space] shadow -> [plane]
  cylinder = ellipse x line_segment
  ex: from logic
    "A and B"
      John is sick and Mary is sick
    we can deduce A and B:
      [John is sick and Mary is sick] -> [John is sick "A"]
      [John is sick and Mary is sick] -> [Mary is sick "B"]
    suppose: we can deduce A,B from C
      [C] -> [A]
      [C] -> [B]
      [C] -> [A and B]

Part I: The Category of sets

Article 1: Sets, maps, composition


first become familiar: category of finite sets and maps
  object: a finite set
  map f:
    consists of
      a set A: domain
      a set B: codomain
      a rule assigning each element a to b
        f of a
        f ○ a
    other names
      function, transformation, operator, arrow, morphism
      domain and codomain are same object
      simple endomap: 1_A
        identity map
        f(a) = a
    external diagram:
      [A] f -> [B]
  composition of maps
    gives all the dynamics to the notion of category
    [A] g -> [A] f -> [B]
    f ○ g
    f following g
    f of g
  definition: category (mathematical universe)
      objects: A,B,C...
      maps: f: A -> B
      identity maps: (one per object): 1_A: A -> A
      composition of types:
        assigns to each pair of maps of type:
          [A] g -> [A] f -> [B]
        another map called "f following g"
          [A] f·g -> [C]
      identity laws:
        a) if [A] 1_A -> [A] g -> [B]
          then [A] g·1_A = g -> [B]
        b) if [A] f -> [B] 1_B -> [B]
          then [A] 1_B·g = g -> [B]
      associative law
        if [A] f -> [B] g -> [C] h -> [D]
        then [A] h·(g·f) = (h·g)·f -> [D]
  singleton set: a set with one element
    call this set: 1
  definition: A point of a set X is a map 1 -> X
  if A is familiar set,
    a map from A to X is called: A-element of X
    thus 1-elements are points

ch02: Sets, maps and composition

1. Review of Article 1

3. external diagram

external diagram
  shows domains
internal diagram
  shows instance by instance mapping

4. Problems on the number

#: number of possible maps
A -> B
  if B has 1 elements
    #: 1
  if A has 1 elements
    #: n_B
  if A has zero elements
    #: 1
  if B has zero elements
    #: 0
  if A and B are empty
    #: 1

ch03: Composing maps and counting maps

Part II: The algebra of composition

Article II: Isomorphisms


1. Isomorphisms
  similarities between collections
    ex: same number of elements
    what special properties does map f have then?
      one-to-one: injective and surjective
      then there is an inverse map g for f
        g·f = 1_A
        f·g = 1_B
    a map [A] f -> B is called an isomorphism (or invertible map)
    if there is a map [B] g -> A
      for which g·f = 1_A and f·g = 1_B
    g is inverse for f 
    objects A, B are isomorphic if there is at least one isomorphism
  isomorphic ≅ same-size
  has certain properties
    reflexive: A is isomorphic to A
    symmetric: if A is isomorphic to B, then B is isomorphic to A
    transitive: if A -> B and B -> C, then A -> C isomorphic
  these properties come from associative and identity laws
  ex: cartesian geometry
    analytic approach to geometry starts with an isomorphism:
      [P] f -> [ℝ²]
    assigns each poit a coordinate-pair
    this translated difficult problems in geometry into easier problems in algebra (or opposite way)
  ex: a map f cannot have two different inverses
2. General division problems: Determination and choice
  two sorts of division problems for maps:
    determination (extension) problem
      given f and h, what are all g for which h = g·f
    choice (lifting) problem
      g and h given. what are f for which h = g·f
  determination problem
    we say:
      h is determined by f
      h depends only on f
      a particular solution g: determination of h by f
      h is a function of f
    why is this division problem called determination problem
  ex1: B is a one-element set
      h(x) = (g·f)(x) = g(f(x)) = g(b)
      for all x in A
    h is called: constant
      because even x varies, h(x) is same
  ex2: a choice problem
    B has three elements
    A = C has two elements
    g·f = 1_A
    so f is inverse of g
    for a given g, there are two f that satisfy g · f = 1_A
    for f(x) = z, z ∈ B
      for each x, we need to choose one z value
      but since n_A < n_B we have multiple choices of z for some x
      we can choose any option for those x
    inverse fonksiyon tek bir tane olur demiştik, nasıl oluyor da çok sayıda olabildi?
    choice problem'deki f g'nin inverse'i değil, sadece tek bir taraftan inverse:
      g·f = 1_A
      f·g ≠ 1_B
  ex3: Galileo's determination problem
    Time -> Distance
    Weight !-> Distance
  ex4: Pick's formula
    points in plane
    polygonal figure
    area is a function of
      dots inside
      dost at boundary
3. Retractions, sections, and idempotents
  retraction (section) problem:
    determination/choice problem where h is an identity map
    if [A] f -> [B]
    a retraction for f is a map [B] r -> A 
      for which r·f = 1_A
    a section for f is a map [B] s -> A
      for which f·s = 1_B
  retraction problem is a determination problem
  section problem is a choice problem
  similarity to multiplication
    multiplication annd reciprocals problem
    some have
      1 answer
      0 answers
      infinite answers
  proposition 1:
    if single choice problem has a solution (section for g), then every choice problem involving same g has a solution
      if [A] f -> [B] has a section
      then for any T and map: [T] y -> [B]
      there exists a map [T] x -> A
        for which f · x = y
      eğer f sağ tersinirse, her y için x vardır öyle ki: f·x = y
  ex: representatives
    s for f is thought as a choice of representatives
    A: citizen
    B: city 
    f: city where citizen resides
      | Ahmet | NY |
      | Ali   | NY |
      | Ayşe  | LA |
    what is s?
    one choice for s:
      | NY | Ahmet |
      | LA | Ayşe  |
    [A] n-1 [B]
      going from B to A: take one representative from A
  dual of proposition 1: 1*
    if r has a solution for single determination problem
      then every determination problem with the same f has a solution
  mine: mnemonics for retraction/section:
    for any g there exists t:
    if f has retraction
      t·f = g
    if f has section
      f·t = g
  mine: why is there dual but not triple?
    iki operasyon arasındaki ilişkinin sıralaması ancak iki türlü olabilir:
    üçüncü bir seçenek yok.
  proposition 2:
    if f has retraction r·f=1_A
    for any pair of maps:
      [T] x1 -> [A]
      [T] x2 -> [A]
      f·x1 = f·x2
      x1 = x2
  definition: f satisfies proposition 2
    f is injective for maps from T
  definition: f is injective for maps from T for every T
    f is injective or is a monomorphism
  mine: mnemonics for 1-n between A-B
    ilk kime f uygulanıyorsa, o kümeden 1-n olmalı
      r·f = 1_A
        [A] 1-n [B]
      f·s = 1_B 
        [A] n-1 [B]
    s: sağ. ilk s uygulanır. geri dönme fonksiyonu B'den gider. B:1 A:n
    neden ilk kime f uygulanıyorsa, o küme 1 oluyor?
      daha az elemanı olmalı ki, o kümeye geri dönebilelim
      daha fazla elemanı olan kümenin bazı elemanları aynı karşı elemana bağlanmak zorunda.
  mine: mnemonics for injective/surjective
    injective when r·f=1_A
      A:1 B:n
      x: T -> A bağıntıları injective 
        injective: B'nin alt kümesi
        A'dan birebir
  proposition 2*: dual of 2
    f: A -> B has section: f·s = 1_B
    for any T and t1,t2:
      t1: B->T
      t2: B->T
    if t1·f = t2·f
    then t1 = t2
  definition: a map f with this cancellation property (if t1·f = t2·f then t1 = t2) for every T is called an epimorphism
    monomorphism: f·t1 = f·t2 => t1 = t2 (cancellation from left)
    epimorphism: t1·f = t2·f => t1 = t2 (cancellation from right)
  proposition 3: transivity
    if f: A -> B has a retraction and g: B -> C has a retraction
    then g·f: A -> C has a retraction
    an endomap e is called idempotent if e·e = e
  theorem: uniqueness of inverses
    if f has both a retraction r and a section s then r = s
4. Isomorphisms and automorphisms
  definition: isomorphism (again)
    f is an isomorphism 
    if there is f' which is both a retraction and section for f
    f': inverse map for f
  relation between A and B when isomorphism exists
    A B have same number of elements
    but we don't count elements
      if A and B are isomorphic, then there exists an isomorphism between A and B in the category
  definition: automorphism
    f is both an endomap and isomorphism
  how many isomorphisms are there between A and B
    same number as automorphisms
    Aut(A): set of automorphisms
    Isom(A,B): set of isomorphisms
    Aut(A) is non-empty because at least 1_A is an example
    automorphism in sets: called permutation

Session 4: Division of maps: Isomorphisms


1. Division of maps versus division of numbers
  | Numbers        | Maps        |
  | multiplication | composition |
  | division       | ?           |
  division: reverse operation
  some solutions are not unique
    no solution
    many solutions
    typical for composition of maps
  easiest case: division of maps produces exactly one solution
2. Inverses versus reciprocals
    if f:A->B has an inverse g:B->A satisfying both:
      g·f=1_A and f·g=1_B
    f is an isomorphism and invertible map
  uniqueness of inverses:
    any map f has at most one inverse
3. Isomorphisms as divisors
4. A small zoo of isomorphisms in other categories
  algebra groups:
    f x = 2x
    h x = 1/2 x
    both respect composition
    h is inverse for f
    so f is isomorphism
  ex: geometry
    object: polygonal figure
    map: any map which preserves distances

Session 5: Division of maps: Sections and retractions


1. Determination problems
  f determines another quantity h
      cylinder with gas inside
      heat the system
        volume of gas increases
        raises the piston
      cool the system to original temperature
        gas returns to original volume
      we suspect: temperature determines the volume
        [States of system] h -> [Volumes]
        [States of system] f -> [Temperatures]
        [Temperatures] g -> [Volumes]
      if there is a g for which:
        h = g·f
        g is called a determination of h from f
  generalize this
    suppose we have: f: A -> B and C
    then every map from B to C
      can be composed with f
      to get a map A -> C
    thus f gives us a process
      that takes maps B -> C
      andn gives maps A -> C
    determination problem:
      Given maps f: A -> B and h: A -> C
      find all maps from B to C st g·f = h
    this problem asks
      is h determined by f?
    A: students
    B: gender
    C: yes/no
    f: A -> B gives gender of student
    h: A -> C did student wear hat today?
    case1: h = g·f
      g: B -> C
      whether a student is female/male can tell whether he wears hat or not
      then h is determined by f
  ex 1: to find a proof g that h is determined by f
    a: points
2. A special case: Constant maps
  suppose: B is one-element
    then f is known
    then h must send all elements of A to same element of C
    such a map is called a constant map
    a map that can be factored through 1 is called a constant map
3. Choice problems
  looking for f instead of g
  choice problem because we need to choose for each a ∈ A an element b ∈ B st.
    g(b) = h(a)
    C: towns
    A: people 
    h: resides in town
    B: supermarkets
    g: location of supermarket
    f: supermarket to shop
    f: each person must choose a supermarket in his town
  ex 2: existence of choice maps
    a: if there is an f with g·f = h
      then h and g satisfy:
        ∀ a ∈ A: ∃ b ∈ B st 
        h(a) = g(b)
4. Two special cases of division: Sections and retractions
  special case of choice problem:
    A = C
    h: identity map 1_A
      f: A -> B is a section of 
      g: B -> A if g·f = 1_A
  application of a section:
    solution to choice problem for any map h: A -> C
      variant of 
        if you have 1/2 don't divide by 2; multiply by 1/2 instead
      suppose we have a choice problem
  question: order matters
  mine: mnemonics
    determination problem: what hat to wear today?
      determined by gender of student
    choice problem: each person choose a market
      g·f = 1
      f: section
        f is searched in choice problem
      g: retraction
        g is searched in determination problem
5. Stacking or sorting
    A: books in classroom
    B: people in same classroom
    "belongs to": A -> B
      person that brought the book into classroom
    visualize it by stacking/sorting:
  stacks picture helps us to find all sections of map
    Chad didn't bring a book
      thus: no section for f
    in order f to have a section
      every element of B must have non-empty stack
      ie. ∀ b ∈ B, there must ∃ a ∈ A st f(a) = b
  number of sections
    numbers of each stack multiplied
6. Stacking in a Chinese restaurant

Session 6: Two general aspects or uses of maps


1. Sorting of the domain by a property
  stacking gibi sorting kelimesi de kullanılabilir
    g: X -> B
    we say: g gives rise to a sorting of X into B sorts
      sort: elements in B
    we say: the map is a B-valued property on X
      g is a stacking of the elements of X into B stacks
    in no sort is empty, then the map has a section
    partitioning: such maps
    say: a map X -> B produces a structure in the domain X
      map: B-valued property
      ex: people: X, B: hair color
        map: from the set of people to set of colors
        people are sorted by property of hair color
2. Naming or sampling of the codamin
  f: A -> X
  we say:  f is a familiy of A elements of X
  we say: map from A to X is an A-shaped figure in X
  we say: A-element is the same as figure of shape A
  ex: each students point out a country on a globe
    then we say: Ali's country, Danny's country
  we say: exemplifying, parameterizing maps:
    f:A->X is to parameterize part of X by moving along A following f
3. Philosophical explanation of the two aspects
  Reality consists of things in their motion and development
  other things reflect it, such as words, books,
  small objects:
    1-n ilişkideki 1 tarafı
    small domain sets (listing)
    small codmain sets (properties)

Session 7: Isomorphisms and coordinates

1. One use of isomorphisms: Coordinate systems
  plot: A -> X
  coordinate: X -> A
  coordinate · plot = 1_A
  plot · coordinate = 1_X
cartesian system:
  first: ℝ2 -> ℝ 
  second: ℝ2 -> ℝ 
ex: first(3.12, 4.7) = 3.12
  q is a point in plane
  [1] q -> [P] coordinate -> [ℝ2] first -> [ℝ]
  @mine: her bir sabit değer (constant value) aslında bir morphismdir 1 kümesinden P kümesine
    böylece tüm değerleri de morphism olarak tanımlıyoruz
  to get a number:
      called: first coordinate of q
  once we fixed an isomorphism: f: A -> X
    we can tread A and X as the same object
    because we have inverse maps to translate
2. Two abuses of isomorphisms

Session 8: Pictures of a map making its features evident

why the word "section"
  short for cross section
  section'ın imajı ana kümeden daha küçüktür
    onun bir kesitidir
name: choice of representatives: another name for section

Section 9: Retracts and idempotents


1. Retracts and comparisons
  isomorphism: A ≅ B then
    there is at least one invertible map from A to B
    for finite sets: 
      A and B have same number of points
        maps from a singleton set 1
  how to say: A is at most as big as B
    definition: A ◁ B means that there is at least one map from a to B
    it has two properties:
      R, for reflexive
        since there is the identity map
      T, for transitive
        if A ◁ B and B ◁ C then A ◁ C
    for sets: comparing objects needs additional method
      remember: a section-retration pair: A is at most as big as B
    definition: A is a retract of B means:
      there are maps [A] s -> [B] r -> [A]
      with r·s = 1_A
      we write A ≤_R B
2. Idempotents as records of retracts
  idempotent functions
    A unary operation (or function) is idempotent if, whenever it is applied twice to any value, it gives the same result as if it were applied once; i.e., ƒ(ƒ(x)) ≡ ƒ(x). For example, the absolute value function, where abs(abs(x)) ≡ abs(x), is idempotent.
  e = s·r is idempotent
    B: people in USA
    A: districts
    s: choice of represantitves
    r: residence
    fixed points: image of e = s·r
      they are congress represantitives
      it is isomorphic to set of districts
    e: idempotent map
    r is as sorting of B by A
    if e:B->B is an idempotent map
    a splitting of e consists of an object A
    together with maps:
      s: A -> B
      r: B -> A
      r·s = 1_A
      s·r = e
  crucial idea:
    all essential information about A, r, s
    are contained in B and e
4. Three kinds of retract problems
  r: sorting of B into A sorts
  s: choosing for each sort an example of that sort
  problem: a section s of r
  ex: museum director's problem
    B: mammals
    A: specifies of mammals
    r known
    s unknown
    job: choose a section s of r
      ie. selecting one example for each species
  opposite (dual) problem
  ex: bird watcher's problem
    manual gives an example of each species (sampling/exempliying map s)
    B: birds observerd
    A: species of birds
    s known
    r unknown
    job: assign each bird he sees a species
    bu problem tasnif problemi
    A: sınıflar
    B: örnekler
    type/instance meselesi
  third problem: idempotent
  ex: child sees a variety of animals. young child learns animals
    tries to select an idempotent endomap e
    B = Animals 
    e: Animals -> Animals
    e: assigns each animal to most familar animal
    having selected e, he is asked to split this idempotent into sorts of animals
    B: Animals
    A: sorts of animals
    sr = e
    rs = 1_A
    s: assigns to each sort of animal, the most familiar example
    r: assigns to each animal, its sort
  museum director's problem:
    choosing a cross-section
  bird watcher's problem:
    view s as a sampling of B by A
    choosing for each bird the most similar bird identified in the manual s
  child's problem:
    selection of the idempotent
    then splitting by idempotent
5. Comparing infinite sets

Composition of opposed maps

test for equality of maps
  for f: A -> B, h: B -> A:
  f = h
  iff f·a = h·a for every point a: 1 -> A

Session 10: Brouwer’s theorems

1. Balls, spheres, fixed points, and retractions
  Brouwer fixed point theorem
    I: line segment
    suppose: f: I -> I is a continous endomap
    then this map must have a fixed point
      f(x) = x
  D is a closed disk. f a continous endomap of D. Then f has a fixed point

 Tech    24 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...