Constructing an injective reduction of equivalence relations

Question

[Metastuff: I asked this question in a slightly different way on mathSE last week, and it didn't go anywhere, which is why I am asking here. I added the DST tag because it's basically a problem about Borel equivalence relations stripped of all the Borelness constraints. I do need help, so helpful redirection is appreciated.]

I am trying to give a somewhat constructive definition of a function. It's somewhat constructive because I'll freely assume that I can well-order any set. Aside from that, I want to say what the function looks like.

I have two equivalence relations $E$ and $F$ on spaces $X$ and $Y$, respectively. There are no restrictions on the sizes of anything. I want to define a function $f : X \to Y$ such that $$ x E y \Leftrightarrow f(x) F f(y)\;\;\;\text{ and }\;\;\;f(x) = f(y) \Rightarrow x = y $$ for all $x,y \in X$. This makes $f$ send all points in an $E$-class to the same $F$-class and also be injective on equivalence classes (i.e., injective as $X/E \to Y/F$) and on the underlying space.

Let $I$ be the class of nonzero cardinals. For every $i \in I$, the number of $F$-classes of size at least $i$ is greater than or equal to the number of $E$-classes of size at least $i$. I want to give a mostly-constructive proof that this is sufficient for there to be a function as described above (from $E$ to $F$), i.e., I want to describe the function.

I have been struggling with this on and off for several weeks. Below are some possible time-savers for you guys. If you already have a solution, you can skip it.

---

The problem is extremely easy in the slightly nicer situation where, for every $i \in I$, the number of $F$-classes of size exactly $i$ is greater than or equal to the number of $E$-classes of size exactly $i$. Just partition the set of $E$-classes by size and put a well-order on each set in the partition. Do the same for $F$-classes. Then send the $n$th $E$-class of size $i$ to the $n$th $F$-class of size $i$.

The complication for the original case is that you might have to send an $E$-class of size $i$ to an $F$-class of size $j$ with $i < j$. Two problems arise this way.

First, you can't use the larger classes wastefully by sending relatively small classes to them. E.g., if $E$ has solely two classes, one of size $2$ and one of size $5$, and $F$ has solely two classes, one of size $4$ and one of size $6$, you cannot send the class of size $2$ to the class of size $6$. The only way that I can think to avoid this problem is inductively: (i) well-order the classes in some way, (ii) send the least $E$-class to the least $F$-class that is big enough, (iii) remove these, and (iv) repeat from step (ii).

This creates the second problem: how to choose the well-order for step (i). If you try, e.g., to order the classes by increasing size with an arbitrary order among classes of the same size, you run into the following problem (as Brian Scott pointed out to me on mathSE a week ago). Suppose $E$ has $\omega$ many classes of size $1$ and one class of size $2$. Suppose $F$ has one class each of every finite size. Then the above won't work because $F$ has order-type $\omega$, but $E$ has order-type $\omega+1$.

You can fix this case with the same trick that you use to well-order the rationals. Put the $E$-classes of size $i$ into a column and well-order each column. Then move along the diagonals like so. But it's not clear to me what this looks like when you have any number of columns and rows rather than just countably many.

---

Edit to explain potential solution: It sounds plausible to me that sending an $E$-class to an $F$-class of the smallest available size that is large enough will avoid fatally wasteful assignments regardless of the order in which you make assignments. E.g., given an $E$-class of size $5$, if $F$-classes of sizes $4,7,$ and $9$ are available, choose one of size $7$.

The problem then is just how to iterate through the $E$-classes. This sounds problematic generally, but my knowledge of ordinals is weak. E.g., is there always some sense in which you can iterate through all the members of an initial ordinal?

Put the $E$-classes into an array like this one so that an $E$-class has an index (column,row). Let the index $(s,p)$ mean that $s$ is the size of the $E$-class and $p$ is its arbitrarily-assigned position in the column.

Consider the case where you have at most countably many $E$-classes of each size and only countably many possible infinite sizes. That is, $p \in \omega$ and $s \in \omega \times \lbrace 0,1\rbrace$. That is, you have countably many finite sizes (tagged with $0$) and countably many infinite sizes (tagged with $1$). Then you just have two copies of the above array; one for finite sizes and one for infinite sizes.

Separately snake through each of them in the way depicted in the linked picture. For the array of finite sizes, this hits indices in this order: $((1,0),1), ((1,0),2), ((2,0),1), ((1,0),3), \ldots$, where the $0$ indicates that you're in the "finite" array. For the array of infinite sizes, this hits the indices in this (analogous) order: $((1,1),1), ((1,1),2), ((2,1),1), ((1,1),3), \ldots$. Here, $(1,1)$ denotes some infinite size such as $\omega$; $(2,1)$ might be $2^\omega$, and so on.

Finally, interleave the two orders that you got from snaking through each array. Most simply, you can take one member from each order at a time. This gives: $$((1,0),1), ((1,1),1), ((1,0),2), ((1,1),2), ((2,0),1), ((2,1),1), ((1,0),3), \ldots$$

I apologize for the somewhat cumbersome notation, but I hope that the pattern becomes clear.

Incidentally, you won't necessarily have an $E$-class for all of the points in the above arrays. E.g., you might not have any $E$-classes of size $2$. I am assuming the fullest possible case for simplicity, as it still defines a well-order when you remove some of the points.

Answer 1

This is a very nice problem, which I like very much.

The answer is that yes, indeed, there is such an injective reduction of $E$ to $F$. And one can give a recursive construction. (This answer now incorporates several simplifications to my original construction.)

Specifically, let $\delta_\kappa^E$ be the number of $E$ equivalence classes of size at least $\kappa$, and similarly $\delta_\kappa^F$ for $F$. Your assumption is that $\delta_\kappa^E\leq\delta_\kappa^F$ for any cardinal $\kappa$. As $\kappa$ increases, this number is non-increasing, and since it can drop only finitely many times, because there is no infinite descending sequence of ordinals, it follows that there are only finitely many values for $\delta_\kappa^E$.

Let $\kappa_1$ be the least cardinal such that $E$ has no class of size $\kappa_1$ or larger, and so $\delta_{\kappa_1}^E=0$. Below this, there is some minimal $\kappa_0\lt\kappa_1$ where $\delta_\kappa=\delta$ has constant nonzero value $\delta$ for all $\kappa\in[\kappa_0,\kappa_1)$.

Consider the largest classes of $E$, those of size at least $\kappa_0$. We may enumerate them in a sequence of length $\delta$. We shall map them to corresponding $F$ classes of equal or larger size in a recursive procedure. Specifically, at stage $\alpha<\delta$, consider the $\alpha^{\rm th}$ class of $E$ of size at least $\kappa_0$; it has some size $\kappa$; we've used up only $|\alpha|$ many $F$ classes of size at least $\kappa$; since this is less than $\delta$, we still have $F$ classes of size at least $\kappa$ remaining, and so we may map the $\alpha^{\rm th}$ class to any unused $F$ class of equal or larger size (and there is no need to be optimal or to minimize size here).

Thus, we are able to map all the $E$ classes of size at least $\kappa_0$ to distinct corresponding $F$ classes of equal or larger size. Consider the $E$ and $F$ classes that remain, a smaller instance of the problem. Notice that this smaller instance of the problem still satisfies the size hypothesis, using the minimality of $\kappa_0$, since for $\kappa<\kappa_0$ we have $\delta^E_\kappa$ is strictly larger than $\delta$, and hence also $\delta^F_\kappa$ is that large. Since we used up exactly $\delta$ many $F$ classes of size at least $\kappa_0$, there are still sufficient $F$ classes of size at least each $\kappa\lt\kappa_0$.

(To illustrate with the example from your question, where you had infinitely many $E$ classes of size $1$ and only one of size $2$, my algorithm proceeds here by mapping the size $2$ class first, and then realizing that the hypothesis is still true for what remains.)

Furthermore, this smaller instance of the problem now has a strictly smaller version of $\kappa_0$, and it can therefore be handled by induction. So the proof is complete.

To understand the reduction constructively, without induction, one should imagine it working like this. The reduction breaks into finitely many pieces. The first piece consists of the largest classes, on a maximal interval of cardinals $\kappa$ where $\delta_\kappa^E$ is constant value $\delta$, whether finite or infinite. Since there are $\delta$ classes here, we enumerate them in a $\delta$ sequence, and so we never run out of classes on the $F$ side during the course of this $\delta$ process. Then, we move to the preceeding maximal interval of cardinals $\kappa$ on which $\delta_\kappa^E$ has a new strictly larger constant value. Our previous part of the reduction does not interfere with this part, precisely because the new $\delta$ value is now strictly larger than on the first piece, and so there are plenty of $F$ classes of the desired size. And so on for finitely many steps, thereby completing the entire reduction.