[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.][1] 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. I am not sure if it's enough to have two well-orders, one for finite cardinals and one for infinite cardinals, and define the overall order by alternating between these: $1_f,1_i,2_f,2_i,3_f,\ldots$, where $1_f$ and $1_i$ are the the least elements of the finite and infinite orders, respectively, and so on.


  [1]: http://mathlesstraveled.files.wordpress.com/2007/12/rational-grid-diag-enum.png