Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: category theory

Topic: the type of mapping c to [c,c]

Christian Williams (Oct 30 2020 at 21:41):

How can we define $c\mapsto [c,c]$? Can this be made functorial?

Christian Williams (Oct 30 2020 at 21:43):

internal hom is $[-,-]:C^{op}\times C\to C$, and we have duplication $\Delta:C\to C\times C$. but most categories do not have any kind of involution $\ast: C\to C^{op}$. can the above map only be defined for categories with an involution?

sarahzrf (Oct 30 2020 at 22:30):

what do you want it for? i misread

sarahzrf (Oct 30 2020 at 22:41):

hmm, okay, im inclined to say that in most actual use cases you're going to actually want to hold onto [-, -] and compose it with other stuff

sarahzrf (Oct 30 2020 at 22:41):

and then eventually you take some end or coend

Christian Williams (Oct 30 2020 at 22:42):

hm, what do you mean? what would the end represent?

Christian Williams (Oct 30 2020 at 22:42):

@Stelios Tsampas and I might use such a map to describe the behavior of the $\lambda$-calculus.

sarahzrf (Oct 30 2020 at 22:43):

ummm, what i mean is like... my impression is that in most places where you'd actually see [c, c] written, and you'd care about some kind of functoriality beyond a literal mapping on objects, what's happening is that some end or coend is being taken, and the standard abuse of notation for [co]ends is happening where the two c's are actually distinct arguments to a bifunctor

sarahzrf (Oct 30 2020 at 22:44):

oh, are you solving domain equations or something?

Stelios Tsampas (Oct 30 2020 at 22:49):

sarahzrf said:

oh, are you solving domain equations or something?

It will involve domain solving but there's plenty of material for that!

Stelios Tsampas (Oct 30 2020 at 22:50):

Right now the challenge is to come up with a Turi-Plotkin-style distributive law (of whatever sort) that describes the semantics.

Stelios Tsampas (Oct 30 2020 at 22:51):

This kind of semantics was presented in a paper called "Towards a mathematical operational semantics" (http://homepages.inf.ed.ac.uk/gdp/publications/Math_Op_Sem.pdf).

Stelios Tsampas (Oct 30 2020 at 22:51):

But yeah, after this is done, some recursive domain equations will need to be solved :P.

Christian Williams (Oct 30 2020 at 22:52):

yeah Sarah, that's the weird thing. the concept of dinatural transformation already has the "duplication plus dualization" built into it, and hence so do co/ends. but you're right that this should probably be a sign that they are lurking whenever you see [c,c]...

sarahzrf (Oct 30 2020 at 22:53):

Stelios Tsampas said:

Right now the challenge is to come up with a Turi-Plotkin-style distributive law (of whatever sort) that describes the semantics.

hmmm, i dont know anything about this :sweat_smile:

sarahzrf (Oct 30 2020 at 22:53):

i guess i should probably read that paper

Christian Williams (Oct 30 2020 at 22:54):

but it's not an abuse of notation, right? all of the $P(c,c)$'s are a subdiagram of the limit which forms the end. that's why I'm confused, because we seem to be implicitly using a map $c\mapsto P(c,c)$ to even define ends.

Stelios Tsampas (Oct 30 2020 at 22:54):

sarahzrf said:

i guess i should probably read that paper

It's pretty awesome, esp. if you're interested in semantics. It's the closest you can get to "category theory as a metalanguage for semantics" imho.

Nathanael Arkor (Oct 30 2020 at 22:55):

There's not going to be an endofunctor with this property in general. A common "solution" is to instead take the domain of the functor to be the category whose objects are those of $\mathbf C$ and whose morphisms from $A \to B$ are pairs $f : A \rightleftarrows B : g$. (Sometimes one further restricts to isomorphisms.)

sarahzrf (Oct 30 2020 at 22:55):

Christian Williams said:

but it's not an abuse of notation, right? all of the $P(c,c)$'s are a subdiagram of the limit which forms the end. that's why I'm confused, because we seem to be implicitly using a map $c\mapsto P(c,c)$ to even define ends.

it's an abuse of notation, because the limit also involves a bunch of terms P(c₁, c₂) where c₁ ≠ c₂

sarahzrf (Oct 30 2020 at 22:55):

and you can't recover those if you don't have the ability to vary the arguments separately

Nathanael Arkor (Oct 30 2020 at 22:56):

This is essentially the same problem as with defining a reasonable notion of 2-cell for cartesian-closed categories.

Christian Williams (Oct 30 2020 at 22:57):

I understand, but when people write $\prod_c P(c,c)$ and then talk about the equaliser -- are you claiming that this product is not actually definable?

sarahzrf (Oct 30 2020 at 22:57):

it's perfectly definable, it's just that it's a product—the diagram shape is a discrete category

sarahzrf (Oct 30 2020 at 22:57):

the discretification of C

Christian Williams (Oct 30 2020 at 22:58):

Nathanael Arkor said:

There's not going to be an endofunctor with this property in general. A common "solution" is to instead take the domain of the functor to be the category whose objects are those of $\mathbf C$ and whose morphisms from $A \to B$ are pairs $f : A \rightleftarrows B : g$. (Sometimes one further restricts to isomorphisms.)

why does this category help? we were thinking about the "cofree self-dual" $C^{op}\times C$

sarahzrf (Oct 30 2020 at 22:59):

or if you prefer: you can certainly define the mapping of objects c ↦ [c, c] if you like; the problem is making it a functor, of course

Christian Williams (Oct 30 2020 at 22:59):

sarahzrf said:

it's perfectly definable, it's just that it's a product—the diagram shape is a discrete category

okay, sure. though I'm still a bit confused about how to describe the limit diagram as a whole. I should just go back to basics on my own.

Nathanael Arkor (Oct 30 2020 at 22:59):

Because then you can define a functor mapping $A \mapsto [A, A]$ on objects.

sarahzrf (Oct 30 2020 at 22:59):

well, that's the reason you write an end and not a limit

sarahzrf (Oct 30 2020 at 22:59):

actually though there is a nice description as a big limit uhh

sarahzrf (Oct 30 2020 at 23:00):

if you take the twisted arrow category Tw(C) and its projection to C^op × C, you can compose that with P and get a functor Tw(C) → D; then the limit of that is your end

Stelios Tsampas (Oct 30 2020 at 23:01):

sarahzrf said:

if you take the twisted arrow category Tw(C) and its projection to C^op × C, you can compose that with P and get a functor Tw(C) → D; then the limit of that is your end

That blew my mind when I first read it!

Christian Williams (Oct 30 2020 at 23:01):

ah yes, that's right.

Christian Williams (Oct 30 2020 at 23:01):

I was wondering if twisted arrows can help with $c\mapsto [c,c]$.

sarahzrf (Oct 30 2020 at 23:01):

yeah, i also almost brought it up heh

sarahzrf (Oct 30 2020 at 23:02):

but i couldnt figure out how to make it quite relevant

sarahzrf (Oct 30 2020 at 23:02):

i suppose composing the projection with [-, -] gives you a map Tw(C) → C

sarahzrf (Oct 30 2020 at 23:03):

but we don't have C → Tw(C)

sarahzrf (Oct 30 2020 at 23:03):

but we shouldn't want C → C for this anyway, i think

sarahzrf (Oct 30 2020 at 23:03):

it's a red herring

sarahzrf (Oct 30 2020 at 23:04):

...not in the nlab sense

Christian Williams (Oct 30 2020 at 23:04):

why not? what do you expect the type to be like, speculatively

sarahzrf (Oct 30 2020 at 23:05):

i expect that a type expression where a variable occurs in more than one variance should have semantics as a bifunctor rather than as a functor, with the variable becoming two different arguments—as in ends and coends

sarahzrf (Oct 30 2020 at 23:05):

which is basically what i said above

sarahzrf (Oct 30 2020 at 23:05):

so [c, c] isnt any different from just [-, -]

sarahzrf (Oct 30 2020 at 23:05):

it's just that you'd write it in certain contexts to indicate that some kind of operation like an end, coend, or solution to domain equation, is taking place

sarahzrf (Oct 30 2020 at 23:06):

that'd be my off the cuff speculation

sarahzrf (Oct 30 2020 at 23:06):

(having chewed a bit on this kind of thing before)

sarahzrf (Oct 30 2020 at 23:07):

sarahzrf said:

so [c, c] isnt any different from just [-, -]

actually, this is misleading, sorry—if im bringing reference to "semantics for type expressions" into the mix, i should phrase it more like...

sarahzrf (Oct 30 2020 at 23:08):

the semantics of the expression "[c, c]" should be the bifunctor [-, -], while the semantics of the expression "[c₁, c₂]" should be a 4-argument functor which is constant in two of the arguments

sarahzrf (Oct 30 2020 at 23:09):

(i think there are actually semantics like this in the literature already btw)

Stelios Tsampas (Oct 30 2020 at 23:12):

sarahzrf said:

(i think there are actually semantics like this in the literature already btw)

Is this work the "semantics for type expressions" that you mention above?

Christian Williams (Oct 30 2020 at 23:12):

yes, but I imagine there are situations where the map $c\mapsto [c,c]$ is useful on its own. unless it really is impossible to define.

Christian Williams (Oct 30 2020 at 23:14):

it's possible for categories with involution $\ast:C\to C^{op}$, such as star-autonomous.
$C\xrightarrow{\Delta} C\times C\xrightarrow{\ast\times id_C} C^{op}\times C\xrightarrow{[-,-]} C$

Nathanael Arkor (Oct 30 2020 at 23:18):

Do you have such involutions in the examples you're interested in?

Stelios Tsampas (Oct 30 2020 at 23:18):

Well, the category of relations is technically an extreme case of an involution.

Christian Williams (Oct 30 2020 at 23:19):

no, the substitution tensor on $Set^{\mathbb{F}}$ ($A\bullet B = \int A(n)\times B^n$) is only right-closed, and the unit $V$ is not a right dualizing object.

Christian Williams (Oct 30 2020 at 23:21):

but yes, if we zoom out to the context of profunctors, there is probably in some way a better story.

Stelios Tsampas (Oct 30 2020 at 23:21):

...so naturally $Rel^{\mathbf{F}}$ was brought up.

Reid Barton (Oct 30 2020 at 23:31):

Even if you have an involution ${-}^{*} : C \to C^{\mathrm{op}}$, that composition presumably has the disadvantage of not being $c \mapsto [c, c]$ but rather $c \mapsto [c^{*}, c]$. For example, it might be the same thing as $c \mapsto c \otimes c$.

Reid Barton (Oct 30 2020 at 23:31):

Unless $-^{*}$ happens to be the identity on objects, like in a dagger category.

sarahzrf (Oct 30 2020 at 23:35):

Stelios Tsampas said:

sarahzrf said:

(i think there are actually semantics like this in the literature already btw)

Is this work the "semantics for type expressions" that you mention above?

that stuff i mentioned above was mostly handwaving, but yeah, i mean that i think there's work in the literature that takes this kind of approach

John Baez (Oct 30 2020 at 23:35):

If you've got a closed category $C$ and you're trying to deal with $c \mapsto [c,c]$ all by itself you can treat it as a functor from $\mathrm{core}(C)$ to $C$ - I don't think it's more functorial than that.

John Baez (Oct 30 2020 at 23:36):

Here $\mathrm{core}(C)$ is the underlying groupoid of $C$.

sarahzrf (Oct 30 2020 at 23:36):

image.png

Christian Williams (Oct 30 2020 at 23:37):

thanks Reid, yes you're right.

John Baez (Oct 30 2020 at 23:37):

Another famous non-functor is $Z: \textsf{Grp} \to \textsf{Grp}$, the center of a group.

Christian Williams (Oct 30 2020 at 23:37):

oh interesting, why not?

Christian Williams (Oct 30 2020 at 23:38):

(the center of a category is the end of the hom)

sarahzrf (Oct 30 2020 at 23:39):

"natural transformations from the identity to itself"?

John Baez (Oct 30 2020 at 23:39):

You can map $\mathbb{Z}$ into any group $G$ by picking any element of $G$, but it won't give a map from the center of $\mathbb{Z}$ into the center of $G$.

Christian Williams (Oct 30 2020 at 23:39):

yeah, it's called the center. not sure of the best reference

John Baez (Oct 30 2020 at 23:39):

Both the center of a monoid and the endomorphisms of a set (or other obect) are examples of "generalized centers".

John Baez (Oct 30 2020 at 23:40):

James Dolan and I explained the generalized center in our paper HDATQFT.

John Baez (Oct 30 2020 at 23:40):

See the last page.

Dan Doel (Oct 30 2020 at 23:41):

Maybe this is relevant.

Christian Williams (Oct 30 2020 at 23:41):

We leave it to the reader to check that if C is a set, Z(C) is the monoid consisting of all functions F : C → C. Similarly, if C is a category, Z(C) is the monoidal category whose objects are functors F : C → C and whose morphisms are natural transformations between such functors. The monoidal structure here corresponds to composition of functors. A more interesting example was worked out by Kapranov and Voevodsky [46]. Suppose that we start with a monoidal category C and work in the semistrict context. The 2-morphisms in 2Cat are known as ‘quasinatural transformations’, since the square in eq. (4) is required to commute only up to a 2-isomorphism [38]. The 3-morphisms in 2Cat are known as ‘modifications’. The generalized center Z(C) thus turns out to be the braided monoidal category whose objects are quasinatural transformations α: 1 C ⇒ 1 C and whose morphisms are modifications between these.

John Baez (Oct 30 2020 at 23:41):

You're quoting the part after we explain what Z actually means in general.

Dan Doel (Oct 30 2020 at 23:42):

For instance, $c \mapsto [c,c]$ is a relator.

Dan Doel (Oct 30 2020 at 23:42):

The center of a group might be a relator, too.

Christian Williams (Oct 30 2020 at 23:44):

good reference, thanks! definitely relevant.

sarahzrf (Oct 30 2020 at 23:44):

god dammit @Dan Doel i have that paper in my zotero :persevere:

sarahzrf (Oct 30 2020 at 23:44):

i saw it once and i was like "omg i need to read this"

sarahzrf (Oct 30 2020 at 23:44):

and then i didnt

sarahzrf (Oct 30 2020 at 23:44):

of course

Christian Williams (Oct 30 2020 at 23:45):

John Baez said:

You're quoting the part after we explain what Z actually means in general.

ah yes, sorry --

The operation of ‘taking the center’ can also be generalized, in a subtle and striking manner. We can think of a k-tuply monoidal n-category C — strict, semistrict, or weak — as an object in the corresponding version of (n + k)Cat. Let Z(C) be the largest sub-(n + k + 1)-category of (n + k)Cat having C as its only object, 1 C as its only morphism, 1 1 C as its only 2-morphism, and so on, up to only one k-morphism. Thus Z(C) is a (k + 1)-tuply monoidal n-category.

In what sense is Z(C) the ‘generalized center’ of C? Consider first the case where C is a monoid, thought of as a category with one object. Then Z(C) is the largest sub-2-category of Cat having C as its only object, the identity functor 1 C as its only morphism, and natural transformations α: 1 C ⇒ 1 C as 2-morphisms. In other words, Z(C) is the commutative monoid consisting of all natural transformations α: 1 C ⇒ 1 C . Since there is only one object in C, such a natural transformation is simply a single morphism in C, and the the commutative square condition in eq. (4) implies this morphism must commute with all the other morphisms in C. Thus Z(C) is just the center of C as traditionally defined. This also shows that Z is not a functor.

sarahzrf (Oct 30 2020 at 23:45):

not gonna read it now either

John Baez (Oct 30 2020 at 23:47):

The operation of 'taking the center' can also be generalized, in a subtle and striking manner. We can think of a k-tuply monoidal n-category C - strict, semistrict, or weak -as an object in the corresponding version of (n+k)Cat. Let Z(C) be the largest sub-(n+k+1)-category of (n+k)Cat having C as its only object, $1_C$ as its only morphism, $1_{1_C}$ as its only 2-morphism, and so on, up to only one k-morphism. Thus Z(C) is a (k + 1)-tuply monoidal n-category.

John Baez (Oct 30 2020 at 23:47):

Okay, Christian posted it.

John Baez (Oct 30 2020 at 23:48):

So it pushes you one notch down the periodic table. The center of a set is a monoid - its endomorphisms. The center of a monoid is a commutative monoid - its usual center. The center of a monoidal category is a braided monoidal category - a famous construction. And so on.

Christian Williams (Oct 30 2020 at 23:49):

Dan Doel said:

For instance, $c \mapsto [c,c]$ is a relator.

Dan, could you expand on this?

Dan Doel (Oct 30 2020 at 23:51):

Well, they're not considering categories in that paper. They're considering reflexive graphs. So a relator is like a functor for those.

Stelios Tsampas (Oct 30 2020 at 23:54):

I haven't read that paper, but others consider a relator to be an endofunctor in $Rel$, the category of relations.

Christian Williams (Oct 30 2020 at 23:54):

okay; even without preserving composition, where do you send $f:c\to d$?

Christian Williams (Oct 30 2020 at 23:55):

yeah, it's nonstandard terminology.

Stelios Tsampas (Oct 30 2020 at 23:56):

Well, the funny thing is that $[-,-]$ is an endofunctor in $Rel$, aka a relator, which makes me suspect that both notions are related?

Dan Doel (Oct 30 2020 at 23:56):

There is no composition in a reflexive graph. There's only an identity.

Dan Doel (Oct 30 2020 at 23:56):

Yes, categories like Rel are one of their standard examples of reflexive graphs.

Christian Williams (Oct 30 2020 at 23:57):

yes, I'm asking where you send an edge $f:c\to d$ under the reflexive graph morphism $C\to C$ which sends $c\mapsto [c,c]$.

Dan Doel (Oct 31 2020 at 00:05):

Oh, well, it induces an edge $[c,c] → [d,d]$. The details would depend on the graph, because otherwise I think it's unclear what structure we'd even be discussing. If it were types and functions, I would think it would be something like $g : c → c$ is related to $h : d → d$ if when $x : c$ is related by $f$ to $y : d$ then $g(x)$ is related by $f$ to $h(y)$.

Dan Doel (Oct 31 2020 at 00:06):

And it's a relator because when $f$ is the identity relation, it yields the identity relation on functions.

Dan Doel (Oct 31 2020 at 00:09):

In the center case, the criterion would be that if $f : G → H$ is a relation that respects group structure, then it induces a relation $Z(f) : Z(G) → Z(H)$ on the centers, which is probably just restriction?

Dan Doel (Oct 31 2020 at 00:09):

I.E. is a relation that respects group structure required to take an element in the center of $G$ to an element in the center of $H$?

Dan Doel (Oct 31 2020 at 00:16):

I guess one high level detail to take away from the paper is that you can discuss how these things have certain 'nice' properties similar to functors, but you need some way to stop thinking about variance. One way to do that is with something groupoid/isomorphism like, but that can be too restrictive. So reflexive graphs instead get rid of composition.

Dan Doel (Oct 31 2020 at 00:19):

In some cases (like Rel), you might be able to make sense of composition still, but that might not always be the case.

John Baez (Oct 31 2020 at 00:22):

Category theory without composition! :flushed: They call it graph theory.

Dan Doel (Oct 31 2020 at 00:27):

I'm not sure if groupoid stuff is still too restrictive if you instead start talking about $\infty$-groupoids, though. Some people are hoping that the HoTT stuff becomes a better arena for this sort of thing than 'relational' stuff that people have been using. But I'm not sure exactly how things will shake out.

Dan Doel (Oct 31 2020 at 00:30):

Although I guess what I've seen so far is that they're still not the same. Just similar 'higher' generalizations of the two ideas.

Christian Williams (Oct 31 2020 at 00:36):

Dan Doel said:

Oh, well, it induces an edge $[c,c] → [d,d]$. The details would depend on the graph, because otherwise I think it's unclear what structure we'd even be discussing. If it were types and functions, I would think it would be something like $g : c → c$ is related to $h : d → d$ if when $x : c$ is related by $f$ to $y : d$ then $g(x)$ is related by $f$ to $h(y)$.

thanks. it seems in the paper that relators are graph homomorphisms, right? those are like functors, not profunctors. but here you seem to be introducing actual relations. (I probably just need to read more.)

Dan Doel (Oct 31 2020 at 00:45):

Yeah, they're reflexive graph homomorphisms, so they're graph homomorphisms that preserve the distinguished 'identity' edge on each node.

Dan Doel (Oct 31 2020 at 00:53):

At some point they start talking about "reflexive graph categories," too, which I think are kind of like proarrow equipments without the requirement that you can compose proarrows.

Christian Williams (Oct 31 2020 at 01:27):

I think it's important to remember that $Prof = \mathbb{Mod}(Span)$, and $op$ comes from $Span$ being dagger-compact: swapping the legs of a span; for a monad $C$ (a category), this gives $C^{op}$. This perspective makes $op$ much less mysterious and intimidating for me.

sarahzrf (Oct 31 2020 at 03:03):

Dan Doel said:

At some point they start talking about "reflexive graph categories," too, which I think are kind of like proarrow equipments without the requirement that you can compose proarrows.

all roads converge at virtual equipments, i guess

Dan Doel (Oct 31 2020 at 03:53):

I guess when you move to those, a groupoid like thing clearly isn't going to cut it, because you want to be able to promote any directed arrow into a 'relation', and expecting it to be an equivalence is probably not going to work. Equivalences are the opposite direction.

Oscar Cunningham (Oct 31 2020 at 10:48):

Since $\mathrm{End}$ can be thought of as the 'diagonal' of $\mathrm{Hom}$, can the centre of a group also be thought of as the diagonal of some functor involving groups and perhaps group homomorphisms?

Is there a functor $F:\mathbf{Grp}\times\mathbf{Grp}^\mathrm{op}\times\mathrm{Arr}(\mathbf{Grp})\times\mathrm{Arr}(\mathbf{Grp}^\mathrm{op})\times\mathrm{Tw}(\mathbf{Grp})\times\mathrm{Tw}(\mathbf{Grp}^\mathrm{op})\to\mathbf{Grp}$ such that $Z(G)\simeq F(G,G,\mathrm{id}_G,\mathrm{id}_G,\mathrm{id}_G,\mathrm{id}_G)$ for all $G$?