Return to Answer

Yes, indeed, there is such an injective reduction of $E$ to $F$. And one can give a recursive construction. (And I have now edited to simplify the argument.)

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, as there is no infinite descending sequence of ordinals, it follows that there are only finitely many values for $\delta_\kappa^E$.

Let us temporarily consider just the parts of $E$ and $F$ consisting of the equivalence classes of size at least $\kappa_0$. If the stabilized value $\delta$ is finite, then there are finitely many $E$ classes of largest size, and we may map these classes into the $F$ classes in any injective manner to classes of equal or larger size and thereby reduce to a smaller instance of the problem (for which $\kappa_1$ is now strictly smaller), which can therefore be solved by induction.

So we may assume $\delta$ is an infinite cardinal. We now map the classes of $E$ of size at least $\kappa_0$ to corresponding $F$ classes of equal or larger size in a transfinite process of length $\delta$. Enumerate the $E$ classes of size at least $\kappa_0$ in a $\delta$ sequence. 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$; this is strictly fewer than $\delta$ many so far, and so we may map the  $\alpha^{\rm th}$ class to a corresponding $F$ class of the right size.

Continuing by transfinite recursion, we therefore succeed in mapping the $E$ classes of size at least $\kappa_0$ to corresponding $F$ classes of equal or larger size. Thus, we have reduced the problem to mapping the lower portion of $E$, where all classes now have size strictly less than $\kappa_0$, to the remaining part of $F$.

  Notice that this smaller instance of the problem still satisfies the 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, and so for these $\kappa$ we retain the hypothesis on the unused part of $F$, since we used up only $\delta$ many $F$ classes so far.

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$. 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. On so on for finitely many steps, thereby completing the entire reduction.

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$.

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 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.

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 an interval of cardinals $\kappa$ where $\delta_\kappa^E$ is constant value $\delta$. 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 next smaller interval of cardinals $\kappa$, which will have a different and strictly larger constant value for $\delta_\kappa^E$. 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. On so on for finitely many steps, thereby completing the entire reduction.

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$. 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. On so on for finitely many steps, thereby completing the entire reduction.

Yes, indeed, there is such an injective reduction of $E$ to $F$. And one can give a recursive 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 so actually there are only finitely many values for  $\delta_\kappa^E$. In this sense, we can restrict $E$ to finitely many parts, on which the number of classes above any given size is constant (until it becomes zero). Let us therefore focus on the part of $E$ with the largest classes, where $\delta_\kappa$ stabilizes on some final nonzero value $\delta$, with $\delta_\kappa^E=\delta$ for all $\kappa$ in some interval $[\kappa_0,\kappa_1)$, with finally $\delta_{\kappa_1}=0$, meaning that there are no $E$ classes of that size or larger.

So we may assume $\delta$ is an infinite cardinal. Since $\delta\cdot 2=\delta$, let us first reserve $\delta$ many $F$ classes of size at least $\kappa_0$, in such a way that $\delta\leq \delta_\kappa^{F'}$ for the part of the partition $F'$ that remains, for each $\kappa\in[\kappa_0,\kappa_1)$. This can be done by removing "half" of the classses of any given size above $\kappa_0$ from $F$.

We now map the classes of $E$ of size at least $\kappa_0$ to corresponding $F'$ classes of equal or larger size in a transfinite process of length $\delta$. Enumerate the $E$ classes of size at least $\kappa_0$ in a $\delta$ sequence. 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$; this is strictly fewer than $\delta$ many so far, and so we may map the $\alpha^{\rm th}$ class to a corresponding $F'$ class of the right size.

Continuing by transfinite recursion, we therefore succeed in mapping the $E$ classes of size at least $\kappa_0$ to corresponding $F'$ classes of equal or larger size, while reserving $\delta$ many unused $F$ classes of size at least $\kappa_0$. Thus, we have reduced the problem to mapping the lower portion of $E$, where all classes now have size strictly less than $\kappa_0$, to the remaining part of $F$, that is, the small classes of $F$ together with the reserved part of $F$, and this still satisfies the hypothesis. This instance of the problem, which now has strictly smaller $\kappa_0$, can therefore be handled by induction. And so the proof is complete.

You mentioned that you wanted to understand the reduction constructively, and in this case, I would suggest that you view it as operating separately on each of the finitely many intervals of cardinals on which the values of $\delta_\kappa$ are constant, applying the method of the previous paragraphs within each segment. That is, you reduce the problem to finitely many problems, for each of which $\delta_\kappa^E$ is constant.

Yes, indeed, there is such an injective reduction of $E$ to $F$. And one can give a recursive construction. (And I have now edited to simplify the argument.)

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, as 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)$.

So we may assume $\delta$ is an infinite cardinal. We now map the classes of $E$ of size at least $\kappa_0$ to corresponding $F$ classes of equal or larger size in a transfinite process of length $\delta$. Enumerate the $E$ classes of size at least $\kappa_0$ in a $\delta$ sequence. 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$; this is strictly fewer than $\delta$ many so far, and so we may map the $\alpha^{\rm th}$ class to a corresponding $F$ class of the right size.

Continuing by transfinite recursion, we therefore succeed in mapping the $E$ classes of size at least $\kappa_0$ to corresponding $F$ classes of equal or larger size. Thus, we have reduced the problem to mapping the lower portion of $E$, where all classes now have size strictly less than $\kappa_0$, to the remaining part of $F$.

Notice that this smaller instance of the problem still satisfies the 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, and so for these $\kappa$ we retain the hypothesis on the unused part of $F$, since we used up only $\delta$ many $F$ classes so far.

(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 an interval of cardinals $\kappa$ where $\delta_\kappa^E$ is constant value $\delta$. 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 next smaller interval of cardinals $\kappa$, which will have a different and strictly larger constant value for $\delta_\kappa^E$. 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. On so on for finitely many steps, thereby completing the entire reduction.