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: Bell numbers

Daniel Geisler (Apr 14 2024 at 15:35):

I try to understand all major application of the Bell numbers and their related Bell polynomials, but it's coverage in Is there a notion dual to that of subobject classifier? and Is there a notion dual to that of subobject classifier? is over my head. I think of Bell numbers as the number of set partitions of $n$ objects. That is a decategorized version of the sum of the coefficients of $D^nf(g(x))$. Is the appearance of the Bell numbers from the derivatives of composite functions $D^nf(g(x))$, or is something different happening? Thanks.

John Baez (Apr 14 2024 at 15:39):

Daniel Geisler said approximately:

I try to understand all major application of the Bell numbers and their related Bell polynomials, but its coverage here is over my head.

A 'subobject' of a finite set $X$ is the same as a subset of $X$ so there are $2^{|X|}$ subobjects of $X$, where $|X|$ is the cardinality of $X$. I hope this makes sense.

A 'quotient object' of a finite set $X$ is what you get when you choose an equivalence relation on $X$ and form the set of equivalence classes. Thus there is one quotient object of $X$ for each partition of $X$. Thus there are $B_{|X|}$ quotient objects of $X$, where $B_n$ is the nth Bell number and again $|X|$ is the cardinality of $X$.

I think of Bell numbers as the number of set partitions of $n$ objects.

Right; that's what I'm using here.

Jorge Soto-Andrade (Apr 14 2024 at 20:55):

John Baez said:

Daniel Geisler said approximately:

I try to understand all major application of the Bell numbers and their related Bell polynomials, but its coverage here is over my head.

A 'subobject' of a finite set $X$ is the same as a subset of $X$ so there are $2^{|X|}$ subobjects of $X$, where $|X|$ is the cardinality of $X$. I hope this makes sense.

A 'quotient object' of a finite set $X$ is what you get when you choose an equivalence relation on $X$ and form the set of equivalence classes. Thus there is one quotient object of $X$ for each partition of $X$. Thus there are $B_{|X|}$ quotient objects of $X$, where $B_n$ is the nth Bell number and again $|X|$ is the cardinality of $X$.

I think of Bell numbers as the number of set partitions of $n$ objects.

Right; that's what I'm using here.

Jorge Soto-Andrade (Apr 14 2024 at 20:58):

A naive question on the fly: the set of all subsets of a set $X$ of cardinality $n$ is an $n$ -cube, in a natural way (you know what does it mean that two subsets are "adjacent").
What is the analogue geometric visualization for the set of quotient objects of $X$ ?

Jorge Soto-Andrade (Apr 14 2024 at 21:11):

Jorge Soto-Andrade said:

A naive question on the fly: the set of all subsets of a set $X$ of cardinality $n$ is an $n$ -cube, in a natural way (you know what does it mean that two subsets are "adjacent").
What is the analogue geometric visualization for the set of quotient objects of $X$ ?

for $n = 3$ the power set is a cube but for the set of partitions you seem to get a "fake octahedron" as a "dual'' : a south pole, a north pole and an equator consisting of three nodes, not four nodes. Poles have valence 3 and equatorial nodes have valence 4

Peva Blanchard (Apr 14 2024 at 21:14):

In this geometric realization, what does it mean for two partitions of $n$ to be adjacent?

David Egolf (Apr 14 2024 at 23:00):

I had an initial guess regarding a notion of adjacency for partitions, which I very roughly sketch below.

View subsets of a set $X$ as corresponding to monomorphisms (injective functions) to $X$. The condition of one subset being a subset of another I think can be translated to a condition involving the existence of a function that relates the two corresponding monomorphisms in an appropriate way. Use this to define a preorder on subsets, and in that preorder define a notion of adjacency. (A notion of adjacency in a preorder could maybe be something like: $a$ is adjacent to $b$ if $a$ is not isomorphic to $b$ and [$a \leq b$ and there is no $c$ so that $a < c < b$, or $b \leq a$ and there is no $c$ so that $b < c < a$].)

Then turn around all the arrows to get "dual" notions that then have to do with epimorphisms (surjective functions) from $X$. (Partitions of a set are closely related to surjective functions from that set). I hope we'd then get some condition relating epimorphisms from $X$ that we can use to define a preorder of those epimorphisms, and that then we could use the above-described notion of adjacency in a preorder to talk about adjacency of epimorphisms from $X$.

John Baez (Apr 15 2024 at 08:45):

Yes, David is right:

There's a [[preorder]], in fact a [[poset]], in fact even a [[lattice]], of subsets of a given set $X$, and also a lattice of quotient sets of $X$. This allows us to define a notion of adjacency as David described, and also notions like "biggest subset contained in two subsets" or "smallest subset containing two subsets", and dual notions for quotient sets.

John Baez (Apr 15 2024 at 08:52):

The lattice of subsets of an n-element can be visualized as a n-dimensional hypercube:

John Baez (Apr 15 2024 at 08:54):

The lattice of quotient sets of an n-element is a lot more complicated and interesting, and it's spawned some very deep combinatorics problems! Usually people describe these quotient sets as partitions.

John Baez (Apr 15 2024 at 08:55):

Here is the lattice of partitions of a 4-element set:

John Baez (Apr 15 2024 at 08:58):

It has 15 elements since the 4th Bell number is 15, but more interesting is its structure: it does not have up-down symmetry like the lattice of subsets of a set!

John Baez (Apr 15 2024 at 08:59):

To learn a tiny bit more about this, try these 'lectures' of mine:

• The logic of partitions.
• The poset of partitions.

John Baez (Apr 15 2024 at 09:08):

For a taste of how deep this subject gets: the lattice of partitions typically lacks the Sperner property. In other words, the largest possible set of partitions of a finite set $X$, none of which is finer than any other, does not consist of all partitions with a specific number of blocks. However, the first proof of this, due to E. R. Canfield, only constructed counterexamples when $X$ has more than about $6.5 \cdot 10^{24}$ elements!

My colleague Larry Harper at U.C. Riverside, who alas recently died, spent years trying to improve this number, seeking the exact number of elements at which the Sperner property fails.

Eric M Downes (Apr 15 2024 at 11:17):

@Daniel Geisler Two things related to Bell's numbers I find it fun to think about, so you may also, if you weren't already aware:

• a combinatorial open problem: count the number of topologies of a finite set (contains $X,\empty$ and is closed under unions and finite intersections). Because of the connection to partitions, bell's numbers show up (along with sterling numbers) often in bounds I have seen, and this is a nice example of a monotonic function (in this case $\mathsf{FinSet}\to\mathbb{N}$) preserving meets (intersection) but not joins (unions).
• There is a nice way to rewrite $n^k$ as a weighted sum over bell's numbers, which is related to this business of fusions vs. functions from $[k]\to[n]$. Might be fun to look into that and connect the members in the sum to certain kinds of functions for small $n$... I seem to recall the terms have some relation to grouping functions by many-to-oneness classes.

Jorge Soto-Andrade (Apr 15 2024 at 18:34):

Peva Blanchard said:

In this geometric realization, what does it mean for two partitions of $n$ to be adjacent?

that is exactly the question ... For n = 3, I suggested a sort of "natural" adjacency: South Pole (first, because I am writing from Chile) is $\{ a \}, \{ b \}, \{ c \}$, North Pole is
$\{ a, b, c \}$ and the equator consists of the (2,1) partitions.

Jorge Soto-Andrade (Apr 15 2024 at 18:45):

Jorge Soto-Andrade said:

Peva Blanchard said:

In this geometric realization, what does it mean for two partitions of $n$ to be adjacent?

that is exactly the question ... For n = 3, I suggested a sort of "natural" adjacency: South Pole (first, because I am writing from Chile) is $\{ a \}, \{ b \}, \{ c \}$, North Pole is
$\{ a, b, c \}$ and the equator consists of the (2,1) partitions.

Jorge Soto-Andrade (Apr 15 2024 at 18:54):

Jorge Soto-Andrade said:

Jorge Soto-Andrade said:

Peva Blanchard said:

In this geometric realization, what does it mean for two partitions of $n$ to be adjacent?

that is exactly the question ... For n = 3, I suggested a sort of "natural" adjacency: South Pole (first, because I am writing from Chile) is $\{ a \}, \{ b \}, \{ c \}$, North Pole is
$\{ a, b, c \}$ and the equator consists of the (2,1) partitions.

However, looking at John's nice example (Thanks, John), it seems that I was allowing a too big symmetry group: the three equatorial nodes should not be connected to each other, they should be connected just to the two poles. This one seems to be the last one to have up-down symmetry though.

John Baez (Apr 15 2024 at 19:01):

Jorge Soto-Andrade said:

Peva Blanchard said:

In this geometric realization, what does it mean for two partitions of $n$ to be adjacent?

that is exactly the question

David Egolf gave a good answer to this question, though he didn't use all the standard jargon: partially order partitions by refinement, then say a partition $b$ covers if $a < b$ and there is no $c$ so that $a < c < b$. He then said $a$ and $b$ are 'adjacent' if either $b$ covers $a$ or $a$ covers $b$.

Peva Blanchard (Apr 15 2024 at 21:39):

And what happens if we consider, say, the category of finite abelian groups instead of the finite sets? It seems that we get less wild lattices.

If I remember my group theory correctly, we have an epic $G \twoheadrightarrow H$ precisely when there exists a subgroup $K$ of $G$ such that $H \cong G/K$. So quotient objects would be in bijection with iso classes of subgroups of $G$. So it seems that the lattice of quotient objects is the dual of the lattice of subobjects of $G$ (???).

I don't know how if it helps for the case of $FinSet$, but since any finite group is a finite set, there might be some interesting angles. For instance, I guess that the lattice of quotient objects of $G$ in $FinAbGroup$ is a sub-lattice of the lattice of quotient objects of $G$ in $FinSet$.

John Baez (Apr 15 2024 at 21:45):

Peva Blanchard said:

And what happens if we consider, say, the category of finite abelian groups instead of the finite sets? It seems that we get less wild lattices.

If I remember my group theory correctly, we have an epic $G \twoheadrightarrow H$ precisely when there exists a subgroup $K$ of $G$ such that $H \cong G/K$. So quotient objects would be in bijection with iso classes of subgroups of $G$. So it seems that the lattice of quotient objects is the dual of the lattice of subobjects of $G$ (???).

Yes, that's right! Or we can use the word "opposite": there's a poset of subobjects of any abelian group, and its opposite category is the poset of its quotient objects!

John Baez (Apr 15 2024 at 21:45):

This happens not just for abelian groups, but for objects in any [[abelian category]].

John Baez (Apr 15 2024 at 21:47):

Examples include the category of modules of any ring R. Every quotient object of an R-module determines a subobject (the kernel of the quotient map) and every subobject K of an R-module determines a quotient object R/K.

Peva Blanchard (Apr 15 2024 at 21:47):

Oh ! I was about to ask. There could be other categories $C$ with a forgetful functor $C \rightarrow FinSet$ such that the lattice of quotient objects is more well-behaved. That could be a strategy to probe partitions of finite sets.

John Baez (Apr 15 2024 at 21:49):

Yes, "abelian categories" are the much-beloved world where subobjects and quotient objects get along very nicely.