7 Sketches in Compositionality (Fong, Spivak)

Seven Sketches in Compositionality: An Invitation to Applied Category Theory (Brendan Fong, David I. Spivak)

88 flashcards · Mathematics · by lakesare

1. Visually imagine something-preserving function f.

   Extremely disparate examples, no common form!

2. Visually imagine 3 things we need for a concept of generative effect.

   system \= observation f some x so that there is a "f is x-preserving" proposition

3. Visually imagine a Hasse diagram.

   In order theory, a Hasse diagram (/ˈhæsə/; German: [ˈhasə]) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction.

4. What does ∨ stand for?

   Join Joining our simple systems. Joining two systems A and B is performed simply by combining their connections. That is, we shall say the join of systems A and B, denote it A ∨ B, has a connection between points x and y if there are some points z1 , . . . , zn such that each of the following are true in at least one of A or B: x is connected to z1, zi is connected to zi+1, and zn is connected to y.

5. Visually imagine 2 definitions of A join B.

   join definition - it should be possible to walk from x to y Joining our simple systems. Joining two systems A and B is performed simply by combining their connections. That is, we shall say the join of systems A and B, denote it A ∨ B, has a connection between points x and y if there are some points z1 , . . . , zn such that each of the following are true in at least one of A or B: x is connected to z1, zi is connected to zi+1, and zn is connected to y.Hasse diagram - least common parent A ∨ B…

6. How is join ∨ related to logical ∨?

7. What does n stand for?

   nth ordinal

8. What's 0?

   ∅

9. What's 5?

   { 1, 2, 3, 4, 5 }

10. What does X ⊔ Y stand for?

    Disjoint union Given two sets X and Y, their disjoint union X ⊔ Y is the set of pairs of the form (x, 1) or (y, 2), where x ∈ X and y ∈ Y.X ⊔ Y = { (x, 1) : x ∈ X } ∪ { (y, 2) : y ∈ Y }.

11. Visually imagine a notation for: union disjoint union

    union - ∪ E.g. {h, 1} ∪ {1, 2, 3} = { h, 1, 2, 3 }disjoint union - ⊔ E.g. {h, 1} ⊔ {1, 2, 3} = (h, 1), (1, 1), (1, 2), (2, 2), (3, 2)

12. Visually imagine the solution.

    This is a disjoint union

13. Visually imagine the expansion of this notation.

    X0 ∪ X1 ∪ X2 ∪ X3 ∪ X4 ∪~ Example:

14. Visually imagine the expansion of this notation.

    X0 ∩ X1 ∩ X2 ∩ X3 ∩ X4 ∩~ Example: ∩n∈N Xn = ∅

15. Visually imagine: relation VS binary relation.

    relation - R ⊆ X1 × X2 × X3 × X4 × X5 × ... × Xn binary relation - R ⊆ X1 × X2 Wikipedia: a binary relation is the most studied special case n = 2 of an n-ary relation over sets X1, ..., Xn, which is a subset of the Cartesian product X1 × ... × Xn.

16. Visually imagine what { Ap }p∈P expands into. Partition of set A.

    { Aa, Ab, Ac} Considering that P = { a, b, c }.

17. What does P stand for? Partition of set A.

    A set of labels, e.g. { a, b, c }. We refer to P as the set of part labels and if p ∈ P is a part label, we refer to Ap as the pth part.

18. What's a partition physically? Partition of set A.

    A set of sets: { {11, 12}, {13}, {21}, {22, 23} }.

19. When are 2 partitions equal?

    When 2 sets are equal! We, of course, don't care about labels. Partition is a set of sets: { {11, 12}, {13}, {21}, {22, 23} }.

20. Visually imagine one-to-one correspondence between: partitions of A AND equivalence relations on A.

21. How to read A/∼?

    Quotient of A under tilde.

22. [Quotient of A under ~] What's the data type of A?

    A set, { a, b, c, d }.

23. [Quotient of A under ~] What's the data type of ~?

    An equivalence relation on A, { (a, b)..., (c, c), (d, d) }.

24. [Quotient of A under ~] What's the data type of A/~?

    A partition, { { a, b }, { c }, { d } }.

25. [Functions] What does ↠ stand for?

    Surjective function. Onto function.

26. [Functions] What does ↣ stand for?

    Injective function. One-to-one function.

27. [Functions] What does this stand for?

    Bijective function. One-to-one function.

28. Visually imagine a surjection denoting this partition.

29. Visually imagine what F;G this stands for.

    F; then X.

30. Visually imagine x as a strange function. E.g. x = 2, X = { 1, 2, 3 }.

31. [Types of relations] Name 3 names for the main character of the order theory.

32. [Types of relations] Visually imagine 2 great children of the preorder.

33. [Types of relations] Name analogies for 2 great children: Equivalence Relation Partial Order.

    Equivalence Relation - forms a partition Partial Order - comparing how well people can play tennis

34. Visually imagine a join.

    The least upper bound of two elements that are connected as part of an order is called the join of these elements, e.g. the green element is a join of the other two.Like with the greatest element, if two elements have several upper bounds that are equally big, then none of them is a join (a join must be unique).

35. Visually imagine a meet.

    The least upper bound of two elements that are connected as part of an order is called the join of these elements, e.g. the green element is a join of the other two.

36. Give a catchphrase for: join meet.

    join - we'll join in heaven meet - we'll meet on earth

37. [Hasse diagram] What's the logic behind levels in a Hasse diagram?

    If there is an arrow to that el - it jumps to the next level! In this section, we use what are called “Hasse diagrams” - they are much like our usual diagrams, however they have an additional rule that is followed - “bigger” elements are always positioned above smaller ones.In terms of arrows, the rule means that if you add an arrow to a point, the point to which the arrow points must always be above the one from which it points.

38. What does (V, A, s, t) stand for?

    V - Vertices A - Arrows s - source t - target

39. What does ≅ stand for when we discuss orders?

    x ≤ y AND y ≤ x.

40. Name another word for antisymmetry.

    Skeletality.

41. What does poset stand for?

    Partially ordered set. Partial order == poset == partially ordered set.

42. [Hasse diagram] How is Hasse diagram defined: in 7 sketches book VS usually?

    in 7 sketches book - represents preorder (reflexive, transitive) usually - represents partial order (+antisymmetric)

43. [Hasse diagram] Name a shorthand way to determine the relation described by Hasse diagram.

    Is there a path between a and b? Then a~b. By a path in G we mean any sequence of arrows such that the target of one arrow is the source of the next. This includes sequences of length 1, which are just arrows a ∈ A in G, and sequences of length 0, which just start and end at the same vertex v, without traversing any arrows.

44. [Hasse diagram] Visually imagine 2 steps to find all arrows in a Hasse diagram.

    Add reflections Add transitions There should be 12 arrows.

45. What does "equivalence relation induces a partition" mean?

    induces == we can turn A (eq. relation) into B (partition). The phrase "A induces B" means that we have an automatic way to turn an A into a B. In this case, we're saying that we have an automatic way to turn equivalence relations into partitions.

46. What is the default order on a power set, P(X)?

    A~B iff A is a subset of B. The power set can naturally be given an order by inclusion of subsets (and from now on, whenever we speak of the power set as an ordered set, this is the order we mean).

47. [Hasse diagram] Visually imagine Hasse diagram for the default order on a power set, P(X).

    Always a cube of dimension n. For example, taking X  {0, 1, 2}, this is a Hasse diagram for P(X), where order is defined by inclusion. See the cube? The Hasse diagram for the power set of a finite set, say P({1, 2, . . . , n}), always looks like a cube of dimension n. The default order on a power set is A~B iff A is a subset of B.

48. What does P(X) stand for?

    Power set of X { ...all subsets of X } : Set (Set α)

49. What does Prt(X) stand for?

    Partitions of X { ...all partitions of X } : Set (Set (Set α))

50. What does U(X) stand for?

    Upper sets of X { ...all upper sets of X } : Set (Set α)

51. Visually imagine the coarsest partition of { a, b, c, d }.

    { { a, b, c, d } }. For any set S there is a coarsest partition, having just one part. There is also a finest partition, where everything is in its own partition.

52. Visually imagine the finest partition of { a, b, c, d }.

    { { a }, { b }, { c }, { d } }. For any set S there is a coarsest partition, having just one part. There is also a finest partition, where everything is in its own partition.

53. What's a natural way to order these datatypes: Power set of X P(X) : Set (Set α)Upper sets of X U(X) : Set (Set α) Partitions of X Prt(X) : Set (Set (Set α))

    Set (Set α) - a~b iff a is a subset of b Set (Set (Set α)) - a~b iff a is finer than b

54. Give a catchphrase for the upper set of X.

    If x is an element, then so is anything bigger.

55. Visually imagine the upper set generated by these els.

56. What does ≤op stand for?

    Opposite

57. [Monotone maps] Visually imagine a monotone map from preorder (A, ≤A) to preorder (B, ≤B).

58. [Monotone maps] Give a catchphrase for the monotone map between preorders.

    Whenever there is a path x → y upstairs, there is a path F(x) → F(y) downstairs. It is monotone because it preserves order: whenever there is a path x → y upstairs, there is a path F(x) → F(y) downstairs

59. Visually imagine Yoneda lemma (for preorders!).

    We know the upper set {...} => we know the element 2! In mathematics, the Yoneda lemma is arguably the most important result in category theory.It is a vast generalisation of Cayley's theorem from group theory (viewing a group as a miniature category with just one object and only isomorphisms).

60. Why is the greatest lower bound called the universal property?

    Because the greatest lower bound is the greatest among ALL lower bounds.

61. Give a catchphrase for lower bound.

    Set is only to the right (or =).

62. Give a catchphrase for greatest lower bound.

    set is only to the right (or =) lower bounds are only to the left (or =)

63. What's the full notation for a ∧ b?

    ∧{ a, b }

64. What's the analogy for notation ∧A?

    We'll meet on earth (2 hands pointing to earth).

65. What's the analogy for notation ∨A?

    We'll join in heaven (2 hands ponting to heaven).

66. Visually imagine a monotone map.

    Dotted lines don't intersect!

67. What does it mean in maths when we say A can be identified with B.

    There is a default path from A to B; and a default path from B to A. We say that an A “can be identified with” a B when any A gives us a unique B and any B gives us a unique A, and both round-trips—from an A to a B and back to an A, or from a B to an A and back to a B—return us where we started. For example, any discrete preorder (P, ≤) has an underlying set P, and any set P can be made into a discrete preorder (p1 ≤ p2 iff p1  p2), and the round-trips return us where we started.

68. Visually imagine: monotone map between preorders VS isomorphism between preorders.

    monotone map isomorphsism

69. Visually imagine why ∧A is considered abuse of notation.

    ∧{a, b} = c ∧{a, b} = d It may be the case that a subset A has more than one meet or join. Let A be the subset {a, b} in the preorder specified by this Hasse diagram. Then both c and d are meets of A: any element less than both a and b is also less than c, and also less than d.

70. Visually imagine what p ≅ q stands for?

    p ≤ q AND q ≤ p.

71. What's the datatype of P and Q?

    P - preorder (P, ▵) Q - preorder (Q, □)

72. Visually imagine formulas for a monotone map that: preserves joins has a generative effect.

    monotone map that preserves joins monotone map that has a generative effect

73. Give a catchphrase for when a monotone map has a generative effect.

    When it DOESNT preserve joins.

74. I hoped I would find the computer course a useful adjunct to my other studies.

    Something added or connected to a larger or more important thing.

75. Give a catchphrase for a Galois connection.

    Relaxed isomorphism.

76. Visually imagine: Galois connection between preorders VS isomorphism between preorders.

    Galois connection - 2 functions + certain properties isomorphism - 1 function + certain properties

77. adjoint VS adjunction??/

78. [Galois connection] Visually imagine adjoints of the Galois connection.

    f - left adjoint g - right adjoint

79. [Galois connection] Visually imagine left&right adjoints.

    A and B are preorders (from the ground up).

80. [Galois connection] Visually imagine the default way of creating a Galois connection given: preorder Prt(S) preorder Prt(T) g: S → T.

    Можно ли открыть трубы с двух сторон так, чтобы краски не смешивались. Можно ли открыть трубы так, чтобы наполнить одно и то же корыто.

81. [Galois connection] Visually spot the difference between these definitions.

    For all p ∈ P, q ∈ Q: isomorphism: p = g(f(p)) and q = f(g(p)) Galois connection: p ≤ g(f(p)) and q ≥ f(g(q)) Galois connection - 2 functions + certain properties isomorphism - 1 function + certain properties

82. [Galois connection] Give a catchphrase for adjoints & meets/joins.

    left adjoint preserves joins right adjoint preserves meets

83. [Galois connection] Give a catchphrase for how to read this.

    Left adjoint of the Galois connection preserves joins.

84. What does "preorder that has all meets" mean?

    All nonempty subsets have a meet.

85. [monoidal preorder] Visually imagine how to build monoidal preorder from these.

    We need to combine preorder + monoid using monotonicity!

86. [monoidal preorder] Visually imagine monotonicity.

87. [monoidal preorder] Visually imagine what do we call I.

    monoidal unit

88. [monoidal preorder] Visually imagine what do we call ⊗.

    monoidal product