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: community: our work

Topic: Jade Master

Jade Master (Jul 28 2023 at 10:08):

Hi, I don't usually post here but I wanted to advertise a couple of blog posts I just wrote about graph decompositions:

• https://jadeedenstarmaster.wordpress.com/2023/07/27/what-is-a-graph-decomposition/
• https://jadeedenstarmaster.wordpress.com/2023/07/27/the-fibrational-perspective-on-graph-decompositions/
  I'm working up to a big spiel about compositional algorithms for the algebraic path problem. I will try to keep you updated on here :)

John Baez (Jul 28 2023 at 10:45):

Yesterday I started reading your second post (without having read the first) and I got stuck here:

Let $G: X \times X \to R$ be a B-graph where B is the boolean semiring.

I didn't know what it means for a function $G: X \times X \to R$ to be a B-graph.

John Baez (Jul 28 2023 at 10:46):

Now I'm thinking you meant to write $G: X \times X \to B$ and any such function is, by definition, a B-graph.

John Baez (Jul 28 2023 at 10:53):

Is that right?

Jade Master (Jul 28 2023 at 11:24):

John Baez said:

Is that right?

Yes, that's right. Fixing the typo now.

Spencer Breiner (Jul 28 2023 at 12:25):

In the fibrational decompositions, you are allowed to have nonzero edges in the base graph, but only the zero-length edges lift. Is that correct?

Jade Master (Jul 28 2023 at 15:12):

Yes,

Spencer Breiner said:

In the fibrational decompositions, you are allowed to have nonzero edges in the base graph, but only the zero-length edges lift. Is that correct?

Yes, except the nonzero edges must have weight $\infty$. This is because the base must be the free $[0,\infty]$-graph on B-graph. I never said this: but $[0,\infty]$ is equipped with the reverse of the usual ordering, so the condition necessary to be an R-graph morphism is that $H(x,y) \geq G_{[0,\infty]} (f(x),f(y))$ which is always true if the latter weight is 0 and never true if the latter weight is $\infty$. Therefore, only the 0-weigted edges lift.

David Egolf (Jul 28 2023 at 17:53):

Thanks for sharing your blog posts!
I was reading the first one, and was wondering if there is a typo here:

A $R$-graph morphism with source $G: X \times X \to R$ and target $H: X \times X \to R$ is a function $f: X \to Y$...

I was wondering if instead of $H: X \times X \to R$ it should be $H: Y \times Y \to R$.

Jade Master (Jul 29 2023 at 07:51):

David Egolf said:

Thanks for sharing your blog posts!
I was reading the first one, and was wondering if there is a typo here:

A $R$-graph morphism with source $G: X \times X \to R$ and target $H: X \times X \to R$ is a function $f: X \to Y$...

I was wondering if instead of $H: X \times X \to R$ it should be $H: Y \times Y \to R$.

Yes thank you. Typo is fixed now.

Jade Master (Aug 17 2023 at 00:07):

Just wrote this: https://www.localcharts.org/t/embrace-negativity/6532 I hope you enjoy :)

Matteo Capucci (he/him) (Aug 17 2023 at 08:44):

Really nice! Short posts are great, I should write more of those...

Matteo Capucci (he/him) (Aug 17 2023 at 08:45):

So is $\sf Bool^{\rm op}$ the decategorificiation of $\bf Set^{\rm op}$?

John Baez (Aug 17 2023 at 09:00):

Hey, great Jade! I want more people to start blogging with LocalCharts. So I was going to tell you and @Joe Moeller to give it a try.

John Baez (Aug 17 2023 at 09:53):

Matteo Capucci (he/him) said:

So is $\sf Bool^{\rm op}$ the decategorification of $\bf Set^{\rm op}$?

I guess it's well known , but $\mathsf{Bool}^{\rm op}$ is the category of [[Stone spaces]]: compact Hausdorff spaces where the only connected subsets are the singletons.

John Baez (Aug 17 2023 at 09:55):

On the other hand $\mathsf{CABA}^{\rm op}$, the opposite of the category of [[complete atomic Boolean algebras]], is $\mathsf{Set}$.

John Baez (Aug 17 2023 at 09:56):

So to me $\mathsf{Bool}^{\rm op}$ is a lot more like $\mathsf{Set}$ than "the decategorification of $\mathsf{Set}^{\rm op}$".

Joe Moeller (Aug 17 2023 at 13:29):

Yeah, it’s being encouraged to be used at this workshop. I was planning to write something today out tomorrow (today is hiking day).

Matteo Capucci (he/him) (Aug 17 2023 at 21:57):

John Baez said:

Matteo Capucci (he/him) said:

So is $\sf Bool^{\rm op}$ the decategorification of $\bf Set^{\rm op}$?

I guess it's well known , but $\mathsf{Bool}^{\rm op}$ is the category of [[Stone spaces]]: compact Hausdorff spaces where the only connected subsets are the singletons.

There has been a notational mixup: in her post, Jade is calling Bool the walking arrow (I guess we spent too much time at MSP :stuck_out_tongue_wink:)

Todd Trimble (Aug 17 2023 at 22:03):

Matteo Capucci (he/him) said:

So is $\sf Bool^{\rm op}$ the decategorificiation of $\bf Set^{\rm op}$?

So what's the question, exactly?

I'm not really following this, but on a guess, is the question whether $\mathsf{Bool} = \mathbf{2}$ the posetal reflection of the category of sets? Because it is.

Jade Master (Aug 18 2023 at 03:45):

Haha yes John, I meant the walking arrow category by $\mathsf{Bool}$. @Matteo Capucci (he/him) yes it is, but the interesting thing is how catastrophically things fail when you try to enrich in $\mathsf{Set}^{op}$.

Matteo Capucci (he/him) (Aug 18 2023 at 06:31):

Uh, even when you use the cocartesian structure?

John Baez (Aug 18 2023 at 13:54):

Okay, sorry. I should probably use $\mathsf{BoolAlg}$ to mean the category of boolean algebras. But somehow $\mathsf{Bool}$ sounds a bit over-fancy as a name for this thing:

$\bullet \to \bullet$

A lot of category theorists call it 2 - the ordinal 2, not the 2-element set. Maybe a better name is $\bullet \to \bullet$.

Mike Shulman (Aug 18 2023 at 14:22):

"Bool" is probably more common in CS.

John Baez (Aug 18 2023 at 15:34):

I may have even used it myself. I may have also tried $\mathbb{B}$ to put it on par with $\mathbb{N}, \mathbb{Z}, \mathbb{R}$ etc.

Oscar Cunningham (Aug 18 2023 at 17:16):

I guess intuitionistically the category you map into to take the powerset should have the subobject classifier as its set of objects, whereas the walking arrow should have 2 objects. I guess these categories should be called $\mathbb{B}$ and $\mathbb{2}$.

Oscar Cunningham (Aug 18 2023 at 17:17):

(That's a blackboard bold 2, but it didn't render properly for me.)

Mike Shulman (Aug 18 2023 at 17:22):

The subobject classifier in an intuitionistic context shouldn't be called $\mathbb{B}$, as the word "Boolean" is associated with classical logic. It's more often called $\Omega$ or $\mathrm{Prop}$.

Oscar Cunningham (Aug 18 2023 at 17:37):

So maybe we should consider maps out of $\mathbb{\Alpha}$ (for 'arrow') and into $\mathbb{\Omega}$? That has a pleasing symmetry to it.

Jade Master (Aug 18 2023 at 18:29):

I am not meaning to be overly classical-minded...I just think it's sort of a seperate issue and I want to talk about truth values in their most basic and well-understood form.

Jade Master (Aug 18 2023 at 18:31):

I've had people tell me not to use this classical perspective but I've never been convinced. My only goal is to present my ideas in the least confusing way possible.

Matteo Capucci (he/him) (Aug 18 2023 at 18:34):

Todd Trimble said:

Matteo Capucci (he/him) said:

So is $\sf Bool^{\rm op}$ the decategorificiation of $\bf Set^{\rm op}$?

So what's the question, exactly?

I'm not really following this, but on a guess, is the question whether $\mathsf{Bool} = \mathbf{2}$ the posetal reflection of the category of sets? Because it is.

Yeah, I was trying to get Jade to tell me a bit more about the categorified contraposets, i.e. contracategories, i.e. categories enriched in $(\bf Set^{\rm op}, \it 0, +)$

Jade Master (Aug 18 2023 at 19:02):

Matteo Capucci (he/him) said:

Uh, even when you use the cocartesian structure?

Yes. Consider the counit law here. This requires the decomposition along the source or target to be the identity.

Mike Shulman (Aug 18 2023 at 19:02):

I don't think there's anything wrong with doing things classically if that's the context you're interested in. I just meant if one is being constructive, one shouldn't call the subobject classifier "Bool".

Jade Master (Aug 18 2023 at 23:23):

Jade Master said:

Matteo Capucci (he/him) said:

Uh, even when you use the cocartesian structure?

Yes. Consider the counit law here. This requires the decomposition along the source or target to be the identity.

And then I haven't worked out the details but I'm pretty sure that coassociativity forces the other decomposition maps to be trivial. I Should work this out in more detail soon.

Matteo Capucci (he/him) (Aug 19 2023 at 07:54):

Matteo Capucci (he/him) said:

Yeah, I was trying to get Jade to tell me a bit more about the categorified contraposets, i.e. contracategories, i.e. categories enriched in $(\bf Set^{\rm op}, \it 0, +)$

Ha, so am I wrong here? Contracategories are not a thing?

Jade Master (Aug 20 2023 at 15:46):

Matteo Capucci (he/him) said:

Matteo Capucci (he/him) said:

Yeah, I was trying to get Jade to tell me a bit more about the categorified contraposets, i.e. contracategories, i.e. categories enriched in $(\bf Set^{\rm op}, \it 0, +)$

Ha, so am I wrong here? Contracategories are not a thing?

What @Alexander Gietelink Oldenziel and I figured out was that $\mathsf{Vect}^{op},\otimes$-enrichment is a nice replacement. I think we can get one from any category C by taking the free vector space $\mathbb{k}hom(x,y)$ as the enriched homs. The decomposition map has type
$\mathbb{k}hom(x,z) \to \mathbb{k}hom(x,y) \otimes \mathbb{k}hom(y,z)$
and is given by
$f: x \to y \mapsto \sum_{h \circ g= f} g: x \to y \otimes h: y \to z$.

John Baez (Aug 21 2023 at 09:06):

This is interesting because people have already written a million papers on one-object $(\mathsf{Vect}^{\rm op}, \otimes)$-enriched categories: they're called coalgebras. (Coalgebra means something else to computer scientists - that's not what I'm talking about now.)

John Baez (Aug 21 2023 at 09:08):

If we restrict to finite-dimensional vector spaces, we get an equivalence of symmetric monoidal categories

$(\mathsf{Vect}^{\rm op}, \otimes) \simeq (\mathsf{Vect}, \otimes)$

so coalgebras are only really new in the infinite-dimensional case, and presumably this is true for linear cocategories too!

John Baez (Aug 21 2023 at 09:11):

On the other hand, finite-dimensional coalgebras are already interesting when you look at bialgebras. A bialgebra is both an algebra and a coalgebra. To be precise, it's an algebra in the category of coalgebras - or equivalently, a coalgebra in the category of algebras.

Bialgebras are really important in combinatorics, group representation theory and other subjects.

John Baez (Aug 21 2023 at 09:12):

So you might try looking at linear categories in the category of linear cocategories.

You can call them 'bicategories'. :upside_down:

Oscar Cunningham (Aug 21 2023 at 10:28):

('coalgebra in the category of bialgebras' should be 'coalgebra in the category of algebras'.)

Graham Manuell (Aug 21 2023 at 10:33):

It's possibly worth remembering that $\mathsf{Vect}^\mathrm{op}$ is equivalent to the category of linearly compact vector spaces.

John Baez (Aug 21 2023 at 11:14):

Oscar Cunningham said:

('coalgebra in the category of bialgebras' should be 'coalgebra in the category of algebras'.)

Thanks, fixed.

Jade Master (Aug 27 2023 at 15:04):

John Baez said:

So you might try looking at linear categories in the category of linear cocategories.

You can call them 'bicategories'. :upside_down:

Thanks John that's a really interesting idea. We sort of got this idea from @Joe Moeller who mentioned a Hopf algebra related to decompositions of graphs. I suppose I should figure out the difference between Hopf algebras and bialgebras, but for both structures I am interested in the connection to combinatorics.

Jade Master (Aug 27 2023 at 15:04):

Graham Manuell said:

It's possibly worth remembering that $\mathsf{Vect}^\mathrm{op}$ is equivalent to the category of linearly compact vector spaces.

Thanks. Yes this is very interesting and potentially relevant. I have much to read.

John Baez (Aug 27 2023 at 15:54):

Jade Master said:

I suppose I should figure out the difference between Hopf algebras and bialgebras, but for both structures I am interested in the connection to combinatorics.

A bialgebra is a just an algebra in the category of coalgebras. A Hopf algebra is a bialgebra with an extra unary operation called the 'antipode', obeying some stuff.

It goes like this: the free vector space on a set is a coalgebra. The free vector space on a monoid is a bialgebra. The free vector space on a group is a Hopf algebra.

John Baez (Aug 27 2023 at 15:54):

If you understand these 3 examples you are well on the road to understanding the difference between a bialgebra and a Hopf algebra.

John Baez (Aug 27 2023 at 15:56):

My friend Bill Schmitt wrote one of the fundamental papers on Hopf algebras in combinatorics: Hopf algebras of combinatorial structures.

Jade Master (Sep 12 2023 at 12:33):

John Baez said:

This is interesting because people have already written a million papers on one-object $(\mathsf{Vect}^{\rm op}, \otimes)$-enriched categories: they're called coalgebras. (Coalgebra means something else to computer scientists - that's not what I'm talking about now.)

I think @Alexander Gietelink Oldenziel and I are confused because we seemed to have proved that one object $(\mathsf{Vect}^{\rm op}, \otimes)$-enriched categories are sort of trivial. Take a look at the unit law here obtained by taking the usual unit law for a $(\mathsf{Vect},\otimes)$-enriched category and reversing the arrows. Suppose a basis element $f \in hom(x,x)$ decomposes into the tensor $d(f)_1 \otimes d(f)_2$. Then the equation says that $e(d(f)_2) \cdot d(f)_1 = f$. Because $f$ is a basis element, this means that $e(d(f)_2)=1$ and $d(f)_1=f$. So in other words, the decomposition map must always decompose a basis element into itself in the first component of the tensor. I don't think this condition is usually required from coalgebras. Is there something wrong with the above argument or are coalgebras as you mean them usually defined differently?

John Baez (Sep 12 2023 at 13:03):

That's an interesting "paradox". Instead of figuring out the flaw in your logic I think I'd rather convince you there has to be a flaw. I hope you believe that

1) There are nontrivial $(\mathsf{FinVect}, \otimes)$-enriched categories, e.g. $\mathsf{FinVect}$ itself. Here $\mathsf{FinVect}$ is the category of finite-dimensional vector spaces over your favorite field $k$.

2) $(\mathsf{FinVect}, \otimes)$ is equivalent, as a monoidal category, to $(\mathsf{FinVect}^{\mathrm{op}}, \otimes)$. An easy way to see this is to use the equivalence between $\mathsf{FinVect}$ and the skeleton $\mathsf{Mat}$ where objects are objects are natural numbers (i.e. vector spaces $k^n$) and a morphism from $n$ to $m$ is an $m \times n$ matrix. Then there is an equivalence between $\mathsf{Mat}$ and $\mathsf{Mat}^{\mathrm{op}}$ sending any object to itself and any matrix to its transpose. I leave it to you to check that all these equivalences are monoidal.

John Baez (Sep 12 2023 at 13:04):

Given 1) and 2) we conclude that there are nontrivial $(\mathsf{FinVect}^{\mathrm{op}}, \otimes)$-enriched categories: indeed, these are essentially the same as $(\mathsf{FinVect}, \otimes)$-enriched categories!

John Baez (Sep 12 2023 at 13:05):

TL;DR:

You can think of linear maps as matrices and take their transposes to turn all morphisms in $\mathsf{FinVect}$ into morphisms in $\mathsf{FinVect}^{\mathrm{op}}$ (or vice versa). So, if you've shown $(\mathsf{FinVect}^{\mathrm{op}}, \otimes)$-enriched categories are trivial in some way, the same is true for $(\mathsf{FinVect}, \otimes)$-enriched categories - but these aren't trivial.

Martti Karvonen (Sep 12 2023 at 13:25):

Another way to see that there has to be a flaw is as follows: one-object $V$-categories are exactly monoids in $V$, so in this case the one-object categories are monoids in the opposite category of vector spaces= comonoids in vector spaces=coalgebras.

John Baez (Sep 13 2023 at 08:52):

As to the flaw in the argument, it's around here:

Jade Master said:

I think Alexander Gietelink Oldenziel and I are confused because we seemed to have proved that one object $(\mathsf{Vect}^{\rm op}, \otimes)$-enriched categories are sort of trivial. Take a look at the unit law here obtained by taking the usual unit law for a $(\mathsf{Vect},\otimes)$-enriched category and reversing the arrows. Suppose a basis element $f \in hom(x,x)$ decomposes into the tensor $d(f)_1 \otimes d(f)_2$. Then the equation says that $e(d(f)_2) \cdot d(f)_1 = f$.

This is correct, not only for 'basis elements' - whatever you mean by that - but for all elements of $hom(x,x)$.

I assume the subscripts here are Sweedler notation.

Because $f$ is a basis element, this means that $e(d(f)_2)=1$ and $d(f)_1=f$.

I think this is where you go wrong. It's hard to see why you're concluding this, but noticed that nothing in the definition of $(\mathsf{Vect},\otimes)$-enriched category says anything about 'basis elements'. There is no particular privileged basis for the hom-spaces $\hom(x,x)$. So, it doesn't make sense to assume $e$ and $d$ have some particular behavior on 'basis elements'.

Jade Master (Sep 13 2023 at 21:59):

Thanks @John Baez. Yes, I think I understand that. I was thinking that if you expand $d(f)_1$ as a linear combination of basis elements $\sum_i a_i \cdot f_i$ the equation becomes $\sum_{(f)} e(d(f)_2) \sum_{i} a_i \cdot f_i=f$. By linear independence, the coefficients in front of the basis elements of this sum must be $0$ unless $f_i=f$. However, this doesn't mean the coalgebra is trivial. I am now un-confused so thank you :)

John Baez (Sep 14 2023 at 11:40):

Good! I know there are tons of interesting monoids in $(\mathsf{Vect}^{\textrm{op}}, \otimes)$, and they're important in combinatorics, so there should also be tons of interesting many-object categories enriched in $(\mathsf{Vect}^{\textrm{op}}, \otimes)$, and I hope you have fun with them!

Jade Master (Oct 09 2023 at 08:57):

https://arxiv.org/abs/2310.03445 inb4 someone finds a glaring error on page 1 :) It's too late, we've just submitted it

John Baez (Oct 09 2023 at 09:00):

It looks really cool!

Jade Master (Oct 09 2023 at 14:54):

Thanks John! For advertisement purposes the title and abstract are:

Relative fixed points of functors
Ezra Schoen, Jade Master, Clemens Kupke

We show how the relatively initial or relatively terminal fixed points for a well-behaved functor F form a pair of adjoint functors between F-coalgebras and F-algebras. We use the language of locally presentable categories to find sufficient conditions for existence of this adjunction. We show that relative fixed points may be characterized as (co)equalizers of the free (co)monad on F. In particular, when F is a polynomial functor on Set the relative fixed points are a quotient or subset of the free term algebra or the cofree term coalgebra. We give examples of the relative fixed points for polynomial functors and an example which is the Sierpinski carpet. Lastly, we prove a general preservation result for relative fixed points.

Jade Master (Oct 09 2023 at 14:58):

And also I've just published another blog post: Fibrational and Dependent Decompositions are Equivalent. This post is very technical, but I need it for where I'm going :)

John Baez (Oct 09 2023 at 20:30):

Where are you going? What strange land?

Jade Master (Oct 10 2023 at 20:15):

John Baez said:

Where are you going? What strange land?

:P In this post I proved an isomorphism
$\mathsf{dep}(P) \cong \mathsf{fib}(P)$
between dependent and fibrational graph decompositions over a fixed partition $P: X \to \mathsf{Set}$. In the next post I will upgrade it to an isomorphism of semirings $(\mathsf{dep}(P), +_{d}, \bullet_d) \cong (\mathsf{fib}(P), +_f, \bullet_f)$. The semiring operations on both sides will correspond to the usual matrix sum and product on the total graph but on the dependent side the product is nontrivial and sort of compositional. You can use the dependent product to design compositional graph algorithms and the isomorphism of semirings proves their correctness.

John Baez (Oct 10 2023 at 21:14):

Nice!