Chapter 4: Co-design

Can we build it(1)
Enriched profunctors(22)
Feasibility relationships as Bool-profunctors(6)

  • Whenever you have 10 W of power, you also have 5 W (\(5 W \leq 10 W\))

  • The requirement that the feasibility relation map is monotone says that if \(x' \leq_X x\) and \(y \leq_Y y'\), then \(\phi(x,y) \leq_{Bool} \phi(x',y')\)

    • If x can be obtained from y, something easier to obtain than x can also be obtained from y

    • If x can be obtained from y, then x can be obtained from something harder to obtain than y

  • This chapter should make the following table clear:

    Bool-
    Bool-
    Bool-

  • Bool is a quantale, meaning it has all joins and a closure operation, \(\mathbb{B}\times\mathbb{B}\xrightarrow{\Rightarrow}\mathbb{B}\). The closure operation must satisfy \(b \land c \leq d\) iff \(b \leq (c \Rightarrow d)\). It is the fact that Bool is a quantale that makes this chapter work; we could alternatively use Cost and obtain the cost of obtaining \(x\) from \(y\), not just whether or not it’s possible.

Feasilibiliy relation(1)

A feasibility relation for preorder \(X\) given preorder \(Y\)

  • A monotone map \(X^{op}\times Y \xrightarrow{\phi} \mathbf{Bool}\)

  • Also denoted \(X \overset{\phi}\nrightarrow Y\)

  • Given \(x \in X, y \in Y\), if \(\phi(x,y)=true\) then we say x can be obtained from y

Linked by

Exercise 4-4(2)

Suppose we have the preorders \(X:=\boxed{monoid\rightarrow category \leftarrow preorder}, Y:=\boxed{nothing \rightarrow thisBook}\)

  1. Draw the Hasse diagram for the preorder \(X^{op} \times Y\)

  2. Write a profunctor \(X \overset{\phi}\nrightarrow Y\)

    • True means “my aunt can explain an x given y"

    • Interpret the fact that the preimage of true is an upper set in \(X^{op}\times Y\)

Solution(1)

  2. Let \(\phi((M,B))=\phi((P,B))=True\) else \(False\)

    • The preimage of true being an upper set is a consequence of monotone maps to Bool. The domain orders combinations by feasibility (\(x\leq y\) means x is easier than y), and the preimage being an upper set says that if my aunt can explain \(x\) given \(y\), then she can do something easier than \(x\) given \(y\) and can explain \(x\) with something with more explanatory power than \(y\).

Exercise 4-7(2)

Show that the Boolean \(\Rightarrow\) satsifies the requirements of a closure operator.

Solution(1)

This boils down to the tautology that \((a \land v) \implies w\) iff \(a \implies (v \implies w)\), where the last \(\implies\) comes from \(\multimap\) and the others come from \(\leq\).

V-profunctors(12)

  • A \(\mathcal{V}\) functor must have \(\mathcal{V}\) categories for domain and codomain, so the \(\mathcal{V}\) of a \(\mathcal{V}\) profunctor must be considered as enriched in itself.

  • Matrix algorithm for computing distance matrix of profunctor: \(d_X * M_\phi * d_Y\)

V-profunctor(1)
Bool-profunctors(1)

Bool-profunctors and their interpretation as bridges

  • Let’s consider Bool-profunctors. Recall a preorder (Bool-category) can be drawn as a Hasse diagram.

  • A Bool-profunctor \(X \overset{\phi}{\nrightarrow} Y\) can look like this:

  • With bridges coming from the profunctor, one can now use both paths to get from points in \(X\) to points in \(Y\).

  • There is a path from N to e, so \(\phi(N,e)=\)\(true\) but \(\phi(W,d)=\)\(false\).

  • We could put a box around both preorders and define a new preorder, called the collage.

Linked by

Cost-profunctors(1)

Cost profunctors and their interpretation as bridges.

  • Cost categories are Lawvere metric spaces and can be represented by weighted graphs

  • This is a depiction of a Cost-profunctor

  • The distance from a point in the left to a point in the right will run through the left, across a bridge, then through through the right.

  • \(\phi(B,x)=\)\(11\),\(\phi(A,z)=\)\(20\),\(\phi(C,y)=\)\(17\)

Linked by

Exercise 4-10(2)

Is it true that a Bool-profunctor is exactly the same as a feasibility relation?

Solution(1)

Monotone maps are Bool-functors between Bool-categories, so the definitions line up

Exercise 4-12(2)

We can express \(\phi\) as a matrix where the (m,n)th entry is the value of \(\phi(m,n) \in \mathbb{B}\). Fill out the feasibility matrix for this example

Solution(1)

  • \(\phi\) a b c d e
    N T F T F T
    E T T T T T
    W T F T F T
    S T T T T T

Linked by

Exercise 4-15(2)

Fill out the Cost-matrix associated with Example 4.13 NOCARD

Solution(1)
\(\phi\) x y z
A 17 21 20
B 11 15 14
C 14 18 17
D 12 9 15
Exercise 4-9(2)

Show that a \(\mathcal{V}\) profunctor is the same as a function \(Ob(\mathcal{X})\times Ob(\mathcal{Y}) \xrightarrow{\phi} V\) such that, \(\forall x,x' \in \mathcal{X}, y,y' \in \mathcal{Y}\), the following holds in \(\mathcal{V}\):

\(\mathcal{X}(x',x)\otimes \phi(x,y) \otimes \mathcal{Y}(y,y') \leq \phi(x',y')\)

Solution(1)

  • A \(\mathcal{V}\) profunctor must be a function satisfying the following constraint, according to the \(\mathcal{V}\) functor definition:

    • \(Z((x,y),(x',y')) \leq\) \(\mathcal{V}(\phi((x,y)),\phi((x',y')))\)

    • where \(Z = \mathcal{X}^{op}\times \mathcal{Y}\)

  • Unpacking the definition of a product \(\mathcal{V}\) category, we obtain

    \(\mathcal{X}^{op}(x,x') \otimes \mathcal{Y}(y,y') \leq \mathcal{V}(\phi((x,y)),\phi((x',y')))\)

  • And applying opposite category definition: \(\mathcal{X}(x',x) \otimes \mathcal{Y}(y,y') \leq \mathcal{V}(\phi((x,y)),\phi((x',y')))\)

  • Noting the definition of \(\multimap\) for a \(\mathcal{V}\) category enriched in itself:

    \(\mathcal{V}(v,w)=v\multimap w\), so now we have: \(\mathcal{X}(x',x) \otimes \mathcal{Y}(y,y') \leq \phi((x,y)) \multimap \phi((x',y'))\)

  • From the constraint of a hom-element of a symmetric monoidal preorder \(\mathcal{V}\), i.e. \(a \leq (v \multimap w)\) iff \((a \otimes v) \leq w\), we see that the first case pattern matches with:

    • \(a \mapsto\) \(\mathcal{X}(x',x) \otimes \mathcal{Y}(y,y')\)

    • \(v \mapsto\) \(\phi((x,y))\)

    • \(w \mapsto\) \(\phi((x',y'))\)

  • So using the iff we can rewrite as \((a \otimes v) \leq w\), and use the commutativity of \(\otimes\) to obtain the desired expression.

Linked by

Back to co-design diagrams(4)

Each box in a codesign problem has a list of preorders on the LHS and another list on the right.

The box represents a feasibility relation: \(Load \times Velocity \nrightarrow Torque \times Speed \times \$\)

Movie constraints(1)

  • Consider the feasibility relation

    • \(T:=\boxed{mean\rightarrow nice}\)

    • \(E:=\boxed{boring\rightarrow funny}\)

    • \(Money:=\boxed{100 K\rightarrow 500 K \rightarrow 1M}\)

  • A possible feasibility relation is here:

  • This says, e.g., a nice but boring movie costs $500,000 to produce.

  • We can infer that we can also make a mean/boring movie with what we can produce nice/boring movie.

Linked by

Exercise 4-18(2)

The node \((nice,funny)\) has no arrow from it in Example 4.18a. What does this mean?

Solution(1)

It is not feasible, for any amount of money listed, to produce a nice and funny movie.

Categories of profunctors(27)
Composing profunctors(4)
V-profunctor composition(1)

The composite \(\mathcal{X}\overset{\phi;\psi}\nrightarrow \mathcal{Z}\) of two \(\mathcal{V}\) profunctors, \(\mathcal{X}\overset{\phi}\nrightarrow\mathcal{Y}\) and \(\mathcal{Y}\overset{\psi}\nrightarrow\mathcal{Z}\)

\((\phi;\psi)(x,z) = \bigvee_Y(\phi(x,y)\otimes\psi(y,z))\)

Linked by

Composing Bool-profunctors(1)

  • Need a formula for composing two feasibility relations in series.

  • Suppose \(P,Q,R\) are cities (preorders) and there are bridges (hence, feasibility matrices).

  • The feasibility matrices are:

    \(\textcolor{blue}{\phi}\) a b c d e
    N T F T F F
    E T F T F T
    W T T T T F
    S T T T T T
    \(\textcolor{red}{\psi}\) x y
    a F T
    b T T
    c F T
    d T T
    e F F

  • Feasibility from \(P\) to \(R\) means there is a way-point in Q which is both reachable from \(p \in P\) and can reach \(r \in R\).

  • Composition is a union \((\phi;\psi)(p,r):= \bigvee_Q \phi(p,q)\land \psi(q,r)\).

  • But this is tantamount to matrix multiplication which gives us the result matrix:

    \(\phi;\psi\) x y
    N F T
    E F T
    W T T
    S T T
Exercise 4-22(2)

Consider the following Cost profunctors \(\textcolor{blue}{\phi},\textcolor{red}{\psi}\) \[\begin{tikzcd}[ampersand replacement=\&] A \arrow[d, "3"', bend right] \& B \arrow[l, "2"', bend right] \arrow[d, "5", bend left] \arrow[r, "11", blue, dotted, bend left] \& x \arrow[rr, "3", bend left] \arrow[rd, "4", bend left] \& \& z \arrow[ld, "4", bend left] \arrow[r, "4", red,dotted, bend left] \arrow[rd, red, "4", dotted, bend right] \& p \arrow[r, "2", bend left] \& q \arrow[d, "2", bend left] \\ C \arrow[ru, "3"] \& D \arrow[l, "4", bend left] \arrow[rr, blue, "9", dotted, bend right] \& \& y \arrow[lu, "3", bend left] \arrow[rrr, red, "0", dotted, bend right=49] \& \& d \arrow[u, "1", bend left] \& r \arrow[l, "1", bend left] \end{tikzcd}\]

Fill in the matrix for the composite profunctor.

Solution(1)
\(\phi;\psi\) p q r s
A 23 25 21 22
B 17 19 15 16
C 20 22 18 19
D 11 13 9 10
The categories V-Prof and Feas(12)

  • Because Feas is a category, we can describe feasibility relation using one-dimensional wiring diagrams:

    \(\xrightarrow{a}\boxed{f}\xrightarrow{b}\boxed{g}\xrightarrow{c}\boxed{h}\xrightarrow{d}\)

  • We need more structure to talk about multi-input/output case.

  • This chapter restricts discussion to skeletal quantales, but it is not hard to extend to non-skeltal ones. Two ways:

    1. Let morphisms of \(\mathbf{Prof}_\mathcal{V}\) be isomorphism classes of \(\mathcal{V}\) profunctors. (analogous to trick used when defining Cospan category.)

    2. We could relax what we mean by category (requiring composition to be unital/associative ‘up to isomorphism’ ... this is known as bicategory theory).

V-profunctor category(1)

The category \(\mathbf{Prof}_\mathcal{V}\), given a skeletal quantale \(\mathcal{V}\)

Linked by

The category Feas(1)

The category Feas

Instantiate a \(\mathbf{Prof}_\mathcal{V}\) category with \(\mathcal{V}=\mathbf{Bool}\)

The unit profunctor(1)
Unitality of unit profunctor(2)
Proof(1)

  • Due to skeletality, we need to show for all inputs that \(\phi \leq U_P;\phi\) and \(U_P;\phi \leq \phi\) (the second equality to show is done similarly).

  • Forward direction

    • \(\phi(p,q) = I \otimes \phi(p,q)\)

    • \(\leq P(p,p) \otimes \phi(p,q)\)

      • This is because \(\forall p \in P:\) \(I \leq P(p,p)\) (a constraint of a \(\mathcal{V}\) category), the reflexivity of \(\leq\) for \(\phi(p,q)\), and the monotonicity of \(\otimes\).

    • \(\leq \underset{p' \in P}\bigvee(P(p,p') \otimes \phi(p',q))\)

      • The join is a least upper bound, and the LHS is an element of the set being joined over (the case where \(p=p'\)).

    • \(= (U_P;\phi)(p,q)\)

  • Reverse direction

    • Need to show \(\underset{p' \in P}\bigvee(P(p,p')\otimes \phi(p',q)) \leq \phi(p,q)\)

    • Show that this property holds for each \(p' \in P\) - given the join is a least upper bound, it will also be less than or equal to \(\phi(p,q)\)

    • \(P(p,p')\otimes\phi(p',q) = P(p,p')\otimes\phi(p',q)\otimes I\)

    • \(\leq P(p,p')\otimes \phi(p',q)\otimes Q(q,q)\)

      • \(\forall p:\) \(I \leq P(p,p)\) (a constraint of a \(\mathcal{V}\) category) and the monotonicity of \(\otimes\).

    • \(\leq\phi(p,q)\)

The unit profunctor is unital, i.e. for any profunctor \(P \overset{\phi}\nrightarrow Q\): \(U_P;\phi = \phi = \phi; U_Q\)

Linked by

Exercise 4-26(2)

Choose a nontrivial Cost-category \(\mathcal{X}\) and draw a bridge-style diagram of the unit profunctor \(\mathcal{X} \overset{U_\mathcal{X}}\nrightarrow \mathcal{X}\)

Solution(1)

becomes

Exercise 4-30(2)

  1. Justify all steps the proof of the unitality of unit profunctors.

  2. In the case of \(\mathcal{V}=\mathbf{Bool}\) show each step in the forward direction is actually an equality. NOCARD

Solution(1)

  1. Done, see the proof

    • \(\forall p: P(p,p)=true\) for a Bool-enriched category, because that is the only option for \(I=true\leq P(p,p)\)

      • \(true \land x = x\)

    • If \(\phi(p,q)\):

      • then at least one element of the set being joined over is true (where \(p=p'\) such that \(P(p,p')\land \phi(p',q) = true\)), and the least upper bound of such a set is \(true\)

    • Else:

      • Then every element of that set is \(false\) such that the join is also \(false\).

        • If \(p\leq p'\), it fails because of the second conjunct (consider the constraint on profunctors: we are demanding equal or more resources than something we know fails)

        • If \(p \not \leq p'\), it fails because of the first conjunct. In a Bool-category \(P\), \(P(a,b)\) iff \(a \leq b\).

Exercise 4-31(2)

Prove that the serial composition of profunctors, \(\mathcal{X}\overset{\phi}\nrightarrow\mathcal{Y}\) and \(\mathcal{Y}\overset{\psi}\nrightarrow\mathcal{Z}\), is associative.

Solution(1)

This is tantamount to the quantale matrix multiplication being associative, which was shown in Exercise 2.104.

Fun profunctor facts - companions, conjoints, collages(11)
Companion and conjoint(1)

The companion and conjoint of a \(\mathcal{V}\) functor, \(\mathcal{P}\xrightarrow{F}\mathcal{Q}\)

  • Companion, denoted \(\mathcal{P}\overset{\hat F}\nrightarrow \mathcal{Q}\), is defined \(\hat{F}(p,q):=\mathcal{Q}(F(p),q)\)

  • Conjoint, denoted \(\mathcal{Q}\overset{\check{F}}\nrightarrow\mathcal{P}\)

Linked by

V-adjunction(1)

A \(\mathcal{V}\) adjunction.

A pair of \(\mathcal{V}\) functors, \(\mathcal{P}\overset{F}{\underset{G}\rightleftarrows} \mathcal{Q}\) such that: \(\forall p\in \mathcal{P}, q \in \mathcal{Q}: \mathcal{P}(p,G(q)) \cong \mathcal{Q}(F(p),q)\)

V-profunctor collage(1)

The collage of a \(\mathcal{V}\) profunctor, \(\mathcal{X}\overset{\phi}\nrightarrow \mathcal{Y}\)

  • A \(\mathcal{V}\) category, denoted \(\mathbf{Col}(\phi)\)

    • \(Ob(\mathbf{Col}(\phi)):=\)\(Ob(\mathcal{X})\sqcup Ob(\mathcal{Y})\)

    • \(\mathbf{Col}(\phi)(a,b) :=\) \(\begin{cases}\mathcal{X}(a,b) & a,b \in \mathcal{X} \\ \phi(a,b)& a \in \mathcal{X}, b \in \mathcal{Y} \\ \varnothing & a \in \mathcal{Y}, b \in \mathcal{X} \\ \mathcal{Y}(a,b) & a,b \in \mathcal{Y} \end{cases}\)

  • There are obvious functors \(\mathcal{X}\xrightarrow{i_\mathcal{X}}\mathbf{Col}(\phi)\) and \(\mathcal{Y}\xrightarrow{i_\mathcal{Y}}\mathbf{Col}(\phi)\) sending each object to “itself" called collage inclusions

Linked by

Companion and conjoint of identity(1)

  • For any preorder \(\mathcal{P}\), there is an identity functor \(\mathcal{P}\xrightarrow{id}\mathcal{P}\)

  • Its companion and conjoint agree: \(\hat{id}=\check{id}=\mathcal{P}\overset{U_\mathcal{P}}\nrightarrow \mathcal{P}\) equivalent to the unit profunctor.

Companion and conjoint of addition(1)

  • Consider the addition function on real numbers.

  • It is monotonic, since \((a,b,c)\leq(a',b',c')\) means \(a+b+c\leq a'+b'+c'\)

  • Therefore it has a companion and a conjoint

    • The companion \(\mathbb{R}\times\mathbb{R}\times\mathbb{R}\overset{\hat +}\nrightarrow \mathbb{R}\) sends (a,b,c,d) to true iff \(a+b+c\leq d\).

Linked by

Example 4-43 todo(1)

TODO

Exercise 4-36(2)

Check that the companion \(\hat{id}\) of the identity functor is actually the unit profunctor.

Solution(1)

TODO

Exercise 4-38(1)

Considering the addition example, what is the conjoint of this addition function?

Solution(0)

TODO

Exercise 4-41(1)

Let \(\mathcal{V}\) be a skeletal quantale and \(\mathcal{P}\overset{F}{\underset{G}\rightleftarrows} \mathcal{Q}\) be \(\mathcal{V}\) functors. Show that \(F \dashv G\) iff the companion of the former equals the conjoint of the latter, i.e. \(\hat F = \check G\)

Solution(0)

TODO

Exercise 4-44(1)

Draw a Hasse diagram for the collage of the profunctor:

Solution(0)

TODO

Categorification(15)
The basic idea(2)

  • General idea: take a thing we know and add structure to it such that things that were formerly properties become structures

  • Do in such a way as to be able to recover the thing we categorified by forgetting the new structure.

  • In categorified world, we have more structure available to talk about the relationships between objects.

  • An example is how we treated preorders as categories.

  • Ordinary categories are Set-categories

Categorification of arithmetic(1)

  • Categorification of arithmetic using the category FinSet

  • Replace natural numbers with arbtirary sets of that cardinality.

  • Replace \(+\) with coproduct.

  • This is good categorification because, with replacements, arithmatic truths are preserved: \(\bar{5}\sqcup \bar{3} \cong \bar{8}\)

A reflection on wiring diagrams(1)

To do...

Monoidal categories(6)
SMC(1)

A rough definition of a symmetric monoidal structure on a category \(\mathcal{C}\)

  • Two additional constituents

    1. An object \(I \in Ob(\mathcal{C})\) called the monoidal unit

    2. A functor \(\mathcal{C}\times \mathcal{C}\xrightarrow{\otimes}\mathcal{C}\) called the monoidal product

  • Subject to the well-behaved, natural isomorphisms

    1. \(I \otimes c \overset{\lambda_c}\cong c\)

    2. \(c \otimes I \overset{\rho_c}\cong c\)

    3. \((c \otimes d)\otimes e \overset{\alpha_{c,d,e}}\cong c \otimes (d\otimes e)\)

    4. \(c \otimes d \overset{\sigma_{c,d}}\cong d \otimes c\)

  • A category equipped with these is a symmetric monoidal category

Linked by

Set as SMC(1)

  • Monoidal structure on Set

  • Let \(I\) be any singleton, say \(\{1\}\) and the monoidal product is the cartesian product.

  • This means that \(\times\) is a functor:

    • For any pair of sets in \((S,T) \in Ob(\mathbf{Set}\times\mathbf{Set})\), one obtains a set \(S \times T \in Ob(\mathbf{Set})\).

    • For any pair of morphisms (functions) one obtains a function \((f\times g)\) which works pointwise: \((f\times g)(s,t):=(f(s),g(t))\) which preserves identities and composition.

  • The bookkeeping isomorphisms are obvious in Set

Linked by

Exercise 4-48(1)

Check that monoidal categories generalize monoidal preorders: a monoidal preorder is a monoidal category \((P,I,\otimes)\) where \(P(p,q)\) has at most one element.

Solution(0)

TODO

Exercise 4-50(2)

  • Consider the monoidal category \((\mathbf{Set},1,\times)\) together with the following diagram TODO - NEED TO COPY HERE

  • \(A=B=C=D=F=G=\mathbb{Z}\) and \(E=\mathbb{B}\)

  • \(f_C(a)=|a|\),

  • \(f_D(a)=a*5\),

  • \(g_E(d,b)=d\leq b\)

  • \(g_F(d,b)=d-b\)

  • \(h(c,e)=\text{if }e\text{ then }c\text{ else }1-c\)

  • Suppose the whole diagram defines a function \(A \times B \xrightarrow{q} G \times F\)

  • Answer:

    1. What are \(g_E(5,3)\) and \(g_F(5,3)\)?

    2. What are \(g_E(3,5)\) and \(g_F(3,5)\)?

    3. What is \(h(5,true)\)?

    4. What is \(h(-5,true)\)?

    5. What is \(h(-5,false)\)?

    6. What are \(q_G(-2,3)\) and \(q_F(-2,3)\)?

    7. What are \(q_G(2,3)\) and \(q_F(2,3)\)?

Solution(1)

  1. \(False,\ 2\)

  2. \(True,\ -2\)

  3. \(5\)

  4. \(-5\)

  5. \(6\)

  6. \((2,-13)\) ... \(a\mapsto -2,\ b \mapsto 3,\ c\mapsto 2,\ d\mapsto -10,\ e\mapsto true,\ f\mapsto -13, g \mapsto 2\)

  7. \((-1,7)\) ... \(a\mapsto 2,\ b \mapsto 3,\ c \mapsto 2,\ d\mapsto 10,\ e\mapsto false, f\mapsto 7, g\mapsto -1\)

Categories enriched in a symmetric monoidal category(6)

  • We said that ordinary categories were just Set-categories, but our definition of \(\mathcal{V}\) categories required the \(\mathcal{V}\) to be a preorder!

  • We have to generalize (categorify) \(\mathcal{V}\) categories.

  • Symmetric monoidal preorders can be considered as symmetric monoidal categories, despite not providing the data for identities and composition (these are not needed because there is no choice).

Enrichment in a SMC(1)

A \(\mathcal{V}\) category (a category enriched in \(\mathcal{V}\)) where \(\mathcal{V}\) is a symmetric monoidal category.

  • Call the category \(\mathcal{X}\). There are four constituents:

    • A collection of objects, \(Ob(\mathcal{X})\)

    • For every pair in \(Ob(\mathcal{X})\) one specifies the hom-object \(X(x,y) \in \mathcal{V}\).

    • For every object, specify a \(I \xrightarrow{id_x}X(x,x) \in \mathcal{V}\) called the identity element

    • For every pair of compatible morphisms, a \(\mathcal{X}(x,y)\otimes\mathcal{X}(y,z)\xrightarrow{;}\mathcal{X}(x,z)\) called the composition morphism.

  • These satisfy the usual associative and unital laws.

Linked by

Exercise 4-52(2)

Recall the example with Set as a symmetric moniodal category. Apply the definition of a \(\mathcal{V}\) category and see if this agrees with the definition of an ordinary category. Is there a subtle difference?

Solution(1)

We’ve replaced the identity morphisms with maps from the monoidal unit, but that is functionally equivalent to ‘just picking one’ given that the initial object is a singleton.

Exercise 4-54(2)

What are identity elements in Lawvere metric spaces (Cost-categories)? How do we interpret this in terms of distances?

Solution(1)

\(0\) was the monoidal unit - the distance from an object to itself.

Profunctors form a compact closed category(12)
Compact closed categories(7)
Dual object in a SMC(1)

The dual for an object \(c \in Ob(\mathcal{C})\), which is part of a symmetric monoidal category \((\mathcal{C},I,\otimes)\).

Three consituents:

  1. An object \(c^* \in Ob(\mathcal{C})\) called the dual of c

  2. A morphism \(I\xrightarrow{\eta_c}c^* \otimes c\) called the unit for c

  3. A morphism \(c \otimes c^* \xrightarrow{\epsilon_c}I\) called the counit for c

These are required to satisfy two commutative diagram relations (snake equations)

and

Linked by

Compact closed SMC(1)

A compact closed symmetric monoidal category

One for which every object there exists a dual. This allows us to use the following morphisms without reservation:

and

This also allows us to use the following snake equations in wiring diagrams without reservation:

and

Linked by

Compact closed properties(2)

If \(\mathcal{C}\) is a compact closed category, then:

  1. \(\mathcal{C}\) is monoidal closed

  2. the dual of c is unique up to isomorphism

  3. \(c \cong (c^*)^*\)

Proof(1)

Not really proven, but: \(c \multimap d\) is given by \(c^* \otimes d\)

The natural isomorphism \(\mathcal{C}(b \otimes c, d)\cong \mathcal{C}(b,c \multimap d)\) is given by precomposing with \(id_b \otimes \eta_c\)

Correl as CCC(1)

  • The compact closed category: Corel

  • A correlation \(A \rightarrow B\) is an equivalence relation on \(A \sqcup B\)

  • Correlations are composed by the following rule: two elements are equivalent in the composite if we may travel from one to the other while staying within the component equivalence classes of either

  • There is a symmetric monoidal structure \((\varnothing, \sqcup)\). For any finite set A there is an equivalence relation on \(A \sqcup A\) that partitions elements in the first set from the second. The unit and counit are given by this partition:

    • \(\varnothing \xrightarrow{\eta_A} A \sqcup A\)

    • \(A \sqcup A \xrightarrow{\epsilon_A} \varnothing\)

Linked by

Exercise 4-62(2)

  1. Draw a picture of the unit correlation \(\varnothing \xrightarrow{\eta_{\bar 3}} \bar 3 \sqcup \bar 3\)

  2. Draw a picture of the counit correlation \(\bar 3 \sqcup \bar 3 \xrightarrow{\epsilon_{\bar 3}} \varnothing\)

  3. Check that the snake equations hold. Since every object is its own dual, only one has to be checked.

Solution(1)

  1. \(\boxed{\varnothing}\rightarrow \underset{\bar 3}{\boxed{\bullet\ \bullet\ \bullet}}\ \underset{\bar 3}{\boxed{\bullet\ \bullet\ \bullet}}\)

  2. \(\boxed{\varnothing}\leftarrow \underset{\bar 3}{\boxed{\bullet\ \bullet\ \bullet}}\ \underset{\bar 3}{\boxed{\bullet\ \bullet\ \bullet}}\)

  3. TODO

Feas as as compact closed category(5)
CCC from profunctor category(2)

Let \(\mathcal{V}\) be a skeltal quantale. The category \(\mathbf{Prof}_\mathcal{V}\) can be given the structure of a compact closed category, with the monoidal product given by the product of \(\mathcal{V}\) categories.

Proof(1)

  • Monoidal product acts on objects:

    • \(\mathcal{X} \times \mathcal{Y}((x,y),(x',y'))\) := \(\mathcal{X}(x,x') \otimes \mathcal{Y}(y,y')\)

  • Monoidal product acts on morphisms:

    • \(\phi \times \psi((x_1,y_1),(x_2,y_2))\) := \(\phi(x_1,x_2)\otimes\psi(y_1,y_2)\)

  • Monoidal unit is the \(\mathcal{V}\) category \(1\)

  • Duals in \(\mathbf{Prof}_\mathcal{V}\) are just opposite categories

    • For every \(\mathcal{V}\) category, \(\mathcal{X}\), its dual is \(\mathcal{X}^{op}\)

    • The unit and counit look like identities

      • The unit is a \(\mathcal{V}\) profunctor \(1 \overset{\eta_\mathcal{X}}\nrightarrow \mathcal{X}^{op} \times \mathcal{X}\)

      • Alternatively \(1 \times \mathcal{X}^{op} \times \mathcal{X}\xrightarrow{\eta_\mathcal{X}}\mathcal{V}\)

      • Defined by \(\eta_\mathcal{X}(1,x,x'):=\mathcal{X}(x,x')\)

      • Likewise for the co-unit: \(\epsilon_\mathcal{X}(x,x',1):=\mathcal{X}(x,x')\)

Exercise 4-64(1)

TODO

Solution(1)

TODO

Exercise 4-65(1)

TODO

Solution(0)

TODO

Exercise 4-66(1)

Check that the proposed unit and counits do obey the snake equations.

Solution(0)

TODO

Linked by