Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Below is a generalization of a few theorems that I am trying to prove. I am trying to make the proofs as easy as possible to understand (for, say, a math undergrad).

Setup. I have two sets $X$ and $Y$ whose members can be thought of as (atomic) points. Each point $x$ within each set has been assigned a cardinal $s(x)$ (not necessarily all the same cardinal; can be finite, infinite, successor, limit, anything), which I will call a point's size. The goal is to explicitly construct an injection $f : X \hookrightarrow Y$ that sends a point to a point of equal or greater size. That is, we want $s(x) \leq s(f(x))$.

Below, case 1 is a warmup and will hopefully make clear what I mean by "explicitly construct" (it's not about AC or the like). Case 2 is the question.

Say that a (strict) well-order $<_s$ on a set $A$ is size-respecting iff $s(a) < s(b) \rightarrow a <_s b$ for all $a,b \in A$. That is, to define such an order, first partition the points into classes by size and order these classes using the order on cardinals. Then within each class, the order can be arbitrary.

Case 1. Suppose we are given that $|\{x : x \in X \land s(x) = i\}| \leq |\{y : y \in Y \land s(y) = i\}|$ for every size $i$. That is, $Y$ has at least as many points of size $i$ as $X$ has, for all $i$. Then we can put size-respecting well-orders on $X$ and $Y$ such that we can think of the order on $Y$ as an extension of the order on $X$. Then for each size $i$, we can send the $n$th $x$ of size $i$ to the $n$th $y$ of size $i$. I think it is clear that we have enough $y$s of each size for this to work.

Case 2. Suppose we are given that $|\{x : x \in X \land s(x) \geq i\}| \leq |\{y : y \in Y \land s(y) \geq i\}|$ for every size $i$. That is, $Y$ has at least as many points of size at least $i$ as $X$ has, for all $i$. What is a good, clear way to construct our desired type of injection and see that it works?

We must avoid making assignments wastefully. For example, if $X$ contains (only) a point of size $2$ and one of size $5$ and $Y$ contains (only) a point of size $4$ and one of size $6$, then we cannot send the point of size $2$ to the point of size $6$. We can avoid making this kind of mistake by putting well-orders on the sets as above and inductively sending the largest points in $X$ to the largest points in $Y$, and I think this is the clearest approach. Unfortunately, the set of sizes will not always have a largest member, so it will not work generally.

The second option is to inductively send the smallest points in $X$ to the smallest points in $Y$. That is, send the least element in $X$ to the least element in $Y$ that will work, i.e., whose size is at least as large; then remove these points and repeat. I think it's not perfectly clear that this option works. Perhaps I am rare in thinking this. The problem is that we might have to send a point of size $i$ to a point of size $j$ where $i < j$. How do we know that we will not wastefully use up the larger points in $Y$ this way? I am looking for an explanation more detailed than just repeating the assumption.

Final questions. How would you explain why the second approach here works? Or would you take an entirely different approach instead? Or would you cast the problem in different terms, such as forgetting the points and just working with bags/multisets or sequences of cardinals?

Also, I might easily be mistaken about something above because, in the question, I have removed all restrictions on $X$ and $Y$ except that they be sets, but my mind has not quite implemented this, so I am still thinking of everything as relatively small and simple. I am especially worried that I am not considering some unusually-structured well-orders. So please of course correct me.

share|cite|improve this question
The hypothesis that for each $x\in X$ there is at least one $y\in Y$ such that $s(x)=s(y)$ does not ensure that $Y$ has more than one element of each size occurring in $X$. You need a stronger hypothesis for your Case 1. – Brian M. Scott Aug 20 '12 at 23:50
Why does such an injection exist? I don't believe it always does unless you have some other properties to use. – i. m. soloveichik Aug 20 '12 at 23:53
@BrianM.Scott: Ah, my explanation wasn't clear enough. I will edit. – Rachel Aug 21 '12 at 0:01
Are the sizes finite, or are you allowing arbitrary cardinals? – Brian M. Scott Aug 21 '12 at 22:22
@BrianM.Scott: In the motivating theorems that I have thought more about, they're continuum or smaller. But I would like to allow arbitrary sizes here if possible. This shouldn't cause proper-class complications for $f$ because $X$ and $Y$ are still sets. – Rachel Aug 22 '12 at 2:16

If you allow the size classes to be infinite, there are counterexamples to Case 2. Let $X$ have $\omega$ elements of size $0$, one of size $1$, and nothing else, and let $Y$ have one element of size $n$ for each $n\in\omega$. Then $$|\{x\in X:s(x)\ge 0\}|=\omega=|\{y\in Y:s(y)\ge 0\}|$$ and $$|\{x\in X:s(x)\ge 1\}|=1<\omega=|\{y\in Y:s(y)\ge 1\}|\;,$$ so the hypothesis of Case 2 is satisfied. However, the only size-respecting well-ordering of $Y$ has order-type $\omega$, while every size-respecting well-ordering of $X$ has a last element that has infinitely many predecessors and therefore has order-type greater than $\omega$. It follows that there is no map $f:X\to Y$ such that $s(f(x))\ge s(x)$ for all $x\in X$.

share|cite|improve this answer
Hm. This might be a problem indeed, but perhaps I was too careless with my generalization. Originally, $X$ and $Y$ were equivalence relations (on poss. different sets), and their "points" are their equivalence classes. So: (1) This isn't important for part of your example, but I should have excluded $0$ as a cardinal. (2) The underlying set of $X$ cannot have cardinality greater than the underlying set of $Y$ (orig. constraint). So when you sum up the sizes of the points, the sum for $X$ can't be greater than that for $Y$. I will rethink a modification of your example to see if it is avoided. – Rachel Aug 22 '12 at 2:43
@Rachel: Note that in this example $|X|=|Y|=\omega$, so (2) isn’t violated. – Brian M. Scott Aug 22 '12 at 2:46
Right, the constraint in (2) is not on $|X|$ and $|Y|$ but on the sums of the sizes of their points. In case it is familiar to you, the $f$ that I am looking for is an injective reduction of Borel equivalence relations. So (re)think of $X$ and $Y$ as relations $E$ and $F$. Of course, I have also dropped all of the Borel constraints here. – Rachel Aug 22 '12 at 2:50
@Rachel: The (cardinal) sum of the sizes of their points is also $\omega$ for both $X$ and $Y$ once you replace $0$ by $1$ and $1$ by $2$ for $X$ and delete the size $0$ point for $Y$. (I’ve not yet had a chance to think about the rest of the comment.) – Brian M. Scott Aug 22 '12 at 2:52
For your example, you can send the point of size 2 to a point of size 2 (or whatever) and then make the assignments for the points of size 1. Perhaps you can always get around this type of example by making only finitely many assignments for each size at a time. – Rachel Aug 22 '12 at 3:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.