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: cartesian decompositions

John Baez (Jan 09 2025 at 02:56):

Everyone knows how many ways you can write an $n$-element set as the coproduct of a $k$-element set and an $\ell$-element set when $n = k + \ell$: it's the binomial coefficient

$\displaystyle{ \frac{n!}{k! \ell!} }$

But for some reason, few people talk about the number of ways you can write an $n$-element set as the product of a $k$-element set and an $\ell$-element set when $n = k \ell$. It's

$\displaystyle{ \frac{n!}{k! \ell!} }$

but now this is something new.

John Baez (Jan 09 2025 at 02:59):

When you start thinking about this it can quite confusing, perhaps because we're really used to writing a set $X$ as the coproduct of a subset $Y$ and the complement $X - Y$, but we're not at all used to writing a set $X$ as the product of a set $Y$ and the 'quotient' $X/Y$.

John Baez (Jan 09 2025 at 03:07):

Indeed that's a pretty confusing way to talk about what's going on here!

Here's a way that's clear, but not maximally slick. When $n = k \ell$, I claim the number

$\displaystyle{ \frac{n!}{k! \ell!} }$

counts the 'cartesian decompositions' of an $n$-element set $X$ into a $k$-element set $Y$ and an $\ell$-element set $Z$.

What's a cartesian decomposition? One lowbrow way to say it is this:

Form the product $Y \times Z$, and draw it like a rectangle of dots. Now label the dots with elements of $X$, making sure to label every dot and use each element of $X$ just once. Then say two such labelings are equivalent if they differ by permuting rows and/or columns in your rectangle. An equivalence class of labelings is a cartesian decomposition of $X$ into $Y$ and $Z$.

John Baez (Jan 09 2025 at 03:16):

There are some good ways to think about this stuff using category theory, e.g. coproduct cocones versus product cones. I could explain it in more detail, but I think it's more fun to reinvent this subject yourself... and I bet some of you will have ideas I haven't thought of.

To conclude, I'll just say that we usually write

$\displaystyle{ \binom{n}{k} = \frac{n!}{k! (n-k)!} }$

for the number of ways to write an $n$-element set as the union of two disjoint subsets, one with $k$ elements and one with $n - k$ elements, when $k \le n$. Similarly, some people write

$\displaystyle{ { n \brace k} = \frac{n!}{k! (n/k)!} }$

for the number of cartesian decompositions of an $n$-element set into a $k$-element set and an $(n/k)$-element set, when $k$ divides $n$.

(But beware: this sort of mutant binomial coefficient has nothing to do with Stirling numbers of the second kind, which are written using the same brace notation.)

Todd Trimble (Jan 09 2025 at 04:35):

This is a fun observation! Bit it also feels capable of great generalization. For example, for any functor $F: \mathsf{FinSet} \times \mathsf{FinSet} \to \mathsf{FinSet}$, we could look at the category whose objects (call them $F$-structures) are tuples $(S, T, U, \phi: U \overset{\sim}{\to} F(S, T)$ and whose morphisms consist of triples of isos $(S \to S', T \to T', U \to U')$ satisfying the obvious compatibility with the isos $\phi, \phi'$. Then in how many ways can a set $U$ be endowed with an isomorphism of type $U \cong F(S, T)$, where two such structures on $U$ are considered the same if there is an isomorphism between them as $F$-structures? Unless I'm being silly (always possible), it seems the answer will be

$\frac{U!}{S!T!}$

if there is any such structure on $U$, and $0$ if not. It helps to know that an $F$-structure iso is uniquely determined by the pair of $S$- and $T$-components!

Mike Shulman (Jan 09 2025 at 05:35):

I don't think that can be quite right, because the product formula (unlike the coproduct one) doesn't work when $k=0$ but $\ell\neq 0$.

Mike Shulman (Jan 09 2025 at 06:19):

I think the isomorphisms modulo which we count have to be the identity on $U$.

Mike Shulman (Jan 09 2025 at 06:42):

John Baez (Jan 09 2025 at 08:22):

Mike Shulman said:

I don't think that can be quite right, because the product formula (unlike the coproduct one) doesn't work when $k=0$ but $\ell\neq 0$.

That's a nice observation. Luckily the application I'm using this for avoids that case, basically because math is smarter than I am.

John Baez (Jan 09 2025 at 08:24):

I should have I'm only working with cartesian decompositions of nonempty sets (so $n \ne 0$, and thus $k, \ell \ne 0$).

Mike Shulman (Jan 09 2025 at 15:51):

I guess it also works when $k=0$ and $\ell=1$.

John Baez (Jan 09 2025 at 16:28):

Mike knows tons of category theory, but there are many ways to engage with the concept of 'cartesian decomposition'. Here is one discussed by Manuel Maia and Miguel Mendez.

Given a set $X$, say a cartesian decomposition is a pair of partitions of $X$ such that each block of the first partition intersected with each block of the second partition contains exactly one element of $X$.

Or if you don't like partitions and their 'blocks':

Given a set $X$, say a cartesian decomposition is a pair of equivalence relations on $X$ such that each equivalence class of the first intersected with each equivalence class of the second contains exactly one element of $X$.

(It took me way too long to notice that a 'partition' is the same thing as an 'equivalence relation'. They still bring up different mental images: the first has disjoint nonempty sets called 'blocks' whose union is our whole set, while the second focuses my attention on the relation saying two elements are in the same block.)

If we let $Y$ be the set of blocks of our first partition (or equivalence classes of our first equivalence relation), and $Z$ be the set of blocks of the second, then a cartesian decomposition gives a bijection

$X \stackrel{\sim}{\longrightarrow} Y \times Z$

so true to its name, it decomposes $X$ as a cartesian product of sets.