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: learning: questions

Topic: × in Rel

Spencer Breiner (Apr 15 2021 at 16:05):

Is there a good (self-explanatory) name for the product $A\times B$ in $\mathbf{Rel}$?

It feels wrong to call it a the ``Cartesian product'', given that it's not a product in the categorical sense, but I don't know of any other name for it.

Cole Comfort (Apr 15 2021 at 16:09):

Spencer Breiner said:

Is there a good (self-explanatory) name for the product $A\times B$ in $\mathbf{Rel}$?

It feels wrong to call it a the ``Cartesian product'', given that it's not a product in the categorical sense, but I don't know of any other name for it.

It is more like the bilinear tensor product of vector spaces. In fact, in spans of finite sets seen through the equivalence with natural number matrices, it's the Kronecker product.
I would call it the multiplicative tensor product.

Tom Hirschowitz (Apr 15 2021 at 16:30):

You mean because $\mathbf{Rel}$, as a model of linear logic, interprets both multiplicative conjunction and disjunction as $\times$?

John Baez (Apr 15 2021 at 16:33):

I thought Cole was hinting at the fact that a relation is a matrix valued in the rig $2 = \{0,1\}$, so $\mathsf{Rel}$ is the category of free $2$-modules and module homomorphisms. So we're doing linear algebra here, of a sort, and the product Spencer was talking about is the tensor product of free $2$-modules. I'd say it deserves to be called the "tensor product". You could even write it as $\otimes$ to avoid fooling yourself into thinking it's the cartesian product in $\mathsf{Rel}$.

Tom Hirschowitz (Apr 15 2021 at 16:38):

But then in what sense does the tensor product of free $2$-modules deserve to be called "multiplicative"?

Jade Master (Apr 15 2021 at 16:41):

It multiplies dimension

Jade Master (Apr 15 2021 at 16:41):

At least for finite sets...

John Baez (Apr 15 2021 at 16:45):

When you're taking the tensor product of modules (e.g. vector spaces) you don't say "multiplicative" tensor product: that's implicit in the symbol $\otimes$. But when we do abstract monoidal category theory we use $\otimes$ to mean any monoidal structure and then sometimes you feel the need to pound your fist on the table and emphasize it when you have a $\otimes$ that's really really a tensor product in the classic sense of module theory.

Reid Barton (Apr 15 2021 at 16:53):

It's also multiplicative in the sense that it distributes over finite coproducts (which is not unrelated to the points raised earlier of course).

Tom Hirschowitz (Apr 15 2021 at 20:15):

That's a lot of answers! Thanks @Jade Master , @John Baez , @Reid Barton , @Cole Comfort.

Jade Master (Apr 15 2021 at 21:28):

Yw

Todd Trimble (Apr 16 2021 at 03:26):

Spencer Breiner said:

Is there a good (self-explanatory) name for the product $A\times B$ in $\mathbf{Rel}$?

It feels wrong to call it a the ``Cartesian product'', given that it's not a product in the categorical sense, but I don't know of any other name for it.

You could call it, accurately, coproduct.

Mike Shulman (Apr 16 2021 at 03:38):

@Todd Trimble Isn't it the disjoint union of sets $A+B$ that's both the categorical product and the categorical coproduct in $\mathbf{Rel}$? I thought the question was about the cartesian product of sets, which is the cartesian-bicategory tensor product on $\mathbf{Rel}$.

Todd Trimble (Apr 16 2021 at 03:44):

Whoops! Silly me. That was a brain fart.

John Baez (Apr 16 2021 at 03:50):

It's taken me a weirdly long time to internalize this myself. I think it's easiest if I just remember $\mathsf{Rel}$ is the category of free modules of a rig, namely $2 = \{0,1\}$. Then we've got a tensor product $\otimes$ of free modules, which corresponds to the product of the sets they're free on, and a biproduct $\oplus$, which corresponds to the coproduct of the sets they're free on.

John Baez (Apr 16 2021 at 03:52):

This way of thinking activates my "linear algebra" intuition, where I'm used to products being coproducts and tensor products being something else that distributes over those, and deactivates my "set theory" intuition, where I'm used to products distributing over coproducts.

Oscar Cunningham (Apr 16 2021 at 10:33):

The category $\mathbf{Rel}$ should instead be called '$\mathbf{FreeSupLat}$'

Oscar Cunningham (Apr 16 2021 at 10:34):

John Baez said:

It's taken me a weirdly long time to internalize this myself. I think it's easiest if I just remember $\mathsf{Rel}$ is the category of free modules of a rig, namely $2 = \{0,1\}$.

This isn't quite true is it? In a free module you can only do finite sums, not infinite ones.

Tom Hirschowitz (Apr 16 2021 at 13:14):

Aha! The intuition remains valid though, doesn't it?

John Baez (Apr 16 2021 at 14:02):

Oscar Cunningham said:

John Baez said:

It's taken me a weirdly long time to internalize this myself. I think it's easiest if I just remember $\mathsf{Rel}$ is the category of free modules of a rig, namely $2 = \{0,1\}$.

This isn't quite true is it? In a free module you can only do finite sums, not infinite ones.

Darn, you're right. A description like the one I wanted works for the category $\mathsf{FinRel}$ of finite sets and relations between these. $\mathsf{FinRel}$ is equivalent to the category of finitely generated free $2$-modules and 2-module homomorphisms.

John Baez (Apr 16 2021 at 14:05):

So yes, more generally $\mathsf{Rel}$ is equivalent to the category of free suplattices, where a suplattice is a poset where any subset has a supremum, or least upper bound, and a suplattice morphism is an order-preserving map that preserves least upper bounds.

John Baez (Apr 16 2021 at 14:06):

The free suplattice on a set $X$ is its powerset $2^X$, and a suplattice morphism $f: 2^X \to 2^Y$ is the same as a relation from $X$ to $Y$.

John Baez (Apr 16 2021 at 14:08):

There's some good stuff on the category of suplattices in the nLab, in addition to their article on suplattices.

John Baez (Apr 16 2021 at 14:10):

I think one thing going on here is that if you have a rig R where addition is idempotent, it's interesting to consider "infinitary modules" where besides taking finite R-linear combinations we can take arbitrary R-linear combinations. I believe that $\mathsf{Rel}$ is then equivalent to the category of free infinitary modules of the rig of truth values, $2 = \{0,1\}$.

Mike Shulman (Apr 16 2021 at 15:17):

John Baez said:

a rig R where addition is idempotent

otherwise known as a monoidal join-semilattice

it's interesting to consider "infinitary modules" where besides taking finite R-linear combinations we can take arbitrary R-linear combinations. I believe that $\mathsf{Rel}$ is then equivalent to the category of free infinitary modules of the rig of truth values, $2 = \{0,1\}$.

Is it clear that in such an infinitary module the infinitary sums must also be idempotent? If they are idempotent, then we just have a suplattice whose underlying join-semilattice is an $R$-module (in the monoidal category of semilattices). Since $2$ is the unit object in the latter monoidal category, a $2$-module structure is trivial, so these infinitary modules are just suplattices, and then $\rm Rel$ is the free ones. But it's not clear to me that an "infinitary module" structure must always be idempotent.

Mike Stay (Apr 20 2021 at 19:13):

Spencer Breiner said:

Is there a good (self-explanatory) name for the product $A\times B$ in $\mathbf{Rel}$?

It feels wrong to call it a the ``Cartesian product'', given that it's not a product in the categorical sense, but I don't know of any other name for it.

I think some of the confusion is that when you write $\times$, it's ambiguous as to whether you're taking the categorical product in Set or in Rel. If in Set, it corresponds to the tensor product, relative to which Rel is symmetric monoidal closed. If in Rel, it is both the categorical product and the coproduct.