2
$\begingroup$

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.

  • 0
    The difficulty is that the result in Case 2 is false if you allow the size classes to be infinite; see the answer that I’m just about to post. – 2012-08-22

1 Answers 1

1

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

  • 0
    Yes, the proof that I wanted won't work. And yes to the second question, with the added bit that$f$is Borel (there isn't always such a Borel $f$). Here, I am quite sure that if the cardinalities are all right (in the sense above), then there exists such a function since I have no constraints on $f$ above. But I want as constructive a proof as possible for this case, i.e, I want to postpone using AC until necessary so that I know more about what to do when I don't have it (when I add Borelness constraints). – 2012-08-22