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: mathematics

Topic: equivalence relation puzzle

John Baez (Jan 01 2026 at 23:19):

Here's a puzzle I ran into today. I know an answer that I like, but there are a lot of other answers, so it requires some sense of taste to find a 'interesting' answer:

Puzzle. Find a canonical way to take an equivalence relation $\sim$ on a set $X$ and get an equivalence relation $\approx$ on the quotient $X /\sim$.

By 'canonical' I mean that any bijection $f: X \to X$ preserving the equivalence relation $\sim$ sends equivalence classes to equivalence classes in a way that preserves the equivalence relation $\approx$ on the set of equivalence classes, $X/\sim$.

There are plenty of answers that aren't very 'interesting': for example, we can take $\approx$ to be the equivalence relation $=$ (the finest equivalence relation), or the equivalence relation where everything is equivalent to everything else (the coarsest equivalence relation). I can think of many other choices. But the answer I like uses the equivalence relation $\sim$ in a more substantial way.

If I were smarter maybe I could pose my question in a way that had a unique correct answer. But maybe this sloppy statement will trigger some nice thoughts.

T. Murrills (Jan 02 2026 at 00:15):

(Hello all, happy new year! I haven’t posted here very much, hence the hello—but got a notification for this, and thought it sounded fun. :) )

The simple answer that jumps out at me is that elements of $X/\sim$ can be considered equivalent if their associated equivalence classes are the same size. But this can be phrased more nicely by considering the orbits on $X$ of all those $\sim$-preserving bijections $f$ on $X$ that you mentioned (which then induces an equivalence relation on $X/\sim$). Or, if you like, we can induce an action on $X/\sim$ first, then form equivalence classes by looking at the orbits there. I suspect this can be unrolled into a nice uniqueness condition… :)

It makes me wonder what happens if we iterate this procedure, starting over with $(X/\sim, \approx)$. It seems we always get smaller or hit $=$ in the finite case, and thus wind up at a point. But, without having thought about it too much, I wonder if there’s e.g. an infinite set and equivalence relation which is stable under this operation? It feels like the kind of thing which can be constructed explicitly via some nice recursive construction.

This is ultimately rather straightforward, though; I’d be curious to see a more unusual answer. :)

T. Murrills (Jan 02 2026 at 02:28):

Perhaps understanding iteration of the construction above is not too difficult in the case where all equivalence classes are finite, and there are a finite number of classes of any given cardinality (and so on, but let’s not get stuck here!).

Encode the equivalence classes of $X$ under $\sim_0$ with a given cardinality as a map $q_0 : \mathbb{N}_{> 0} \to \mathbb{N}$, where the domain represents cardinalities equivalence classes can have, and the value at a point counts how many exist. Then, running our procedure and looking at the map associated to the resulting set and equivalence classes, we find that $q_1(n) = \lvert q_0^{-1}\{n\}\rvert$ (with $n \neq 0$).

There are many stable $q$’s: if we want $q(n)$ to be some nonzero value $c$, we must simply ask for $c$ values of $q$ to be $n$ (and this value must be unique among other values $q$ takes).

The most straightforward way to do this is to pack all these values as close to zero as possible! We may as well start with $q(1) = 0$; that means 0 points take the value 1. Whatever $q(2)$ is, there must be that many points that take the value 2 (and it cannot be 1, since nothing can). It could be 0, but that would be uninteresting, so use 2 and set $q(2) = 2$. So there must be 2 (rhs) points that take the value 2 (argument of $q$). The second point that takes the value 2 may as well be the next available point: $q(3) = 2$. In turn, that means there must be 2 points that take the value 3; use the next available ones and say $q(4) = q(5) = 3$. There then must be 3 points that take the value 4, so give 6,7,8 the value 4; 3 points that take the value 5, so use 9,10,11; keep going in this manner.

I wonder if this is the “only” other stable one that avoids infinite cardinalities at all stages, up to a suitable sense of isomorphism—which would be what, exactly? It feels like this explosion has to proceed in “essentially the same way” on its support whatever numbers you use, even if you intersperse some gaps. (Or maybe those gaps can make room for more explosions…but then are all such stable $q$ composed of disjoint explosions? This is all gestural, so don’t worry if I’m not making sense…!)

I also wonder what the other possible (non-stable) trajectories are, and if the space of trajectories as a whole has some interesting properties.

Mike Shulman (Jan 02 2026 at 07:32):

More generally, any equivalence relation on ob(Set) induces such an operation by applying it to the equivalence classes. For instance, you could define two equivalence classes to be $\approx$-related if they are both singletons or both nonsingletons.

More generally still, any family of equivalence relations on ob(Set) indexed by ob(Set) $\times$ ob(Set) induces such an operation. For instance, you could do "both singletons or both nonsingletons" if $X$ has cardinality $\aleph_2$ and $X/\sim$ has cardinality $\aleph_1$, and "same size" otherwise.

I suppose even more generally still, any family of equivalence relations on ob(Set) indexed by ob(Setoid) induces such an operation. For instance, you could do "both singletons or both nonsingletons" if $\sim$ has exactly two equivalence classes of every cardinality below $\aleph_2$, and "same size" otherwise.

John Baez (Jan 02 2026 at 10:30):

Hi!

T. Murrills said:

The simple answer that jumps out at me is that elements of $X/\sim$ can be considered equivalent if their associated equivalence classes are the same size. But this can be phrased more nicely by considering the orbits on $X$ of all those $\sim$-preserving bijections $f$ on $X$ that you mentioned (which then induces an equivalence relation on $X/\sim$). Or, if you like, we can induce an action on $X/\sim$ first, then form equivalence classes by looking at the orbits there. I suspect this can be unrolled into a nice uniqueness condition… :)

Yes, that's the answer I bumped into - I first noticed your first formulation, and then your second, nicer formulation. @Todd Trimble and I are studying the representation theory of the symmetric group, and Young diagrams, and this idea seems to be relevant, though I'm still confused about what's really going on.

Here's a more "unusual" answer to my question, which is really just a worse answer in my opinion:

Given an equivalence relation $\sim$ on a set $X$, we define two elements of $X/\sim$ to be equivalent iff their associated equivalence classes have the same cardinality and the cardinality is either less than 17 or it equals 256.

Mike Shulman (Jan 02 2026 at 17:00):

Interestingly, the two formulations aren't equivalent any more in the absence of excluded middle, where you may not be able to define an automorphism of $X$ that swaps two bijective equivalence classes and leaves the others alone. It won't even be true for the identity equivalence relation in general.