# Help me construct a transfinite bijective enumeration, with restrictions

Let $E$ be an infinite set of cardinality $\aleph_\alpha$, and let $\mathfrak{F}\subset\mathfrak{P}(E)$ such that $\bigcup\mathfrak{F}=E$, $|\mathfrak{F}|=\aleph_\alpha$, and $|A|=\aleph_\alpha$ for any $A\in\mathfrak{F}$. Furthermore, I have a mapping $f$ of $\omega_\alpha$ onto $\mathfrak{F}$ such that $|f^{-1}(A)|=\aleph_\alpha$ for any $A\in\mathfrak{F}$. I would like to define a bijection $g$ of $\omega_\alpha$ onto $E$ such that $g(\xi)\in f(\xi)$. (Maybe not all assumptions are necessary.)

How can this be done? It is easy to define an injection $g$ of that form by transfinite induction, but how can I make sure that "no element of $E$ is left after the last step". I had the idea of starting with an arbitrary bijection of $\omega_\alpha$ onto $E$, and only modifying it at each step of the induction (e.g. by exchanging pairs of elements). But I really don't know what to do at the limit ordinal steps. Any kind of help is welcome.

It would also be great for intuition if someone could prove the $\alpha=0$ case.

-
Does someone know a better title or a more specific tag? – Stefan Jun 12 '11 at 8:07
I think that this question may rise to the level of "set-theory," rather than "elementary-set-theory", according to the usage here. As for a title, how about, "Help me construct a transfinite bijective enumeration, with restrictions". – JDH Jun 12 '11 at 11:26
Since two answers were given, and you have seen them and commented, is there anything missing from them? – Asaf Karagila Jun 12 '11 at 14:24
@Asaf: No, my question is answered. I just didn't find the time to check that until now. – Stefan Jun 12 '11 at 16:52

Obviously you need to add an assumption that $\bigcup\mathfrak F=E$, otherwise no such bijection exists.

I will try the case $\alpha=0$, which is the same as $E=\omega_0$ (the set of all non-positive integers). I hope I haven't overseen something.

We can define $g$ inductively by $g(n)=\min\{k\in f(n); k\notin g[\{0,1,\dots,n-1\}]\}$. (The smallest $k$ from $f(n)$ that we have not used yet.)

Every $k$ is member of some $A$ (if we assume $\bigcup\mathfrak F=E$). For this $A$ the set $f^{-1}(A)$ is inifinite, i.e., there are infinitely many numbers $a_1<a_2<\dots<a_n<\dots$ such that $f(a_i)=A$. It can be easily shown that $k\in g(n)$ for some $n\le a_k$.

-
I have added the assumption. That error is also present in the source of that statement, I hope that it is the only one. – Stefan Jun 12 '11 at 9:39
Thanks for your answer. I can't verify it yet, since I think you meant something else instead of your last sentence. We already know that $k\in f(a_k)$. – Stefan Jun 12 '11 at 9:43
Ah, I see: The sequence $g(a_n)$ is strictly increasing, and it can't possibly jump over $k$. – Stefan Jun 12 '11 at 9:59
@Stefan: I meant $k\in g(n)$. I have corrected this typo in my attempted proof. BTW if your studying some book or paper where this is claimed or it used in a step of some proof, it might be good to mention the source. – Martin Sleziak Jun 12 '11 at 10:00

Let $E=\omega_\alpha$. Define $g(\beta) =$ the least element of $f(\beta) \setminus g[\beta]$. Since $|f(\beta)| = \aleph_\alpha$ the set $f(\beta) \setminus g[\beta]$ is not empty. By definition $g$ is an injection. Let us show that it is a bijection. Let $\gamma \in E$. By the assumption $\bigcup \mathfrak F = E$, $\gamma \in A$ for some $A \in \mathfrak F$. Since $|f^{-1}(A)| = \aleph_\alpha$ and $\gamma < \omega_\alpha$, there is snome $\beta$ such that $g(\beta) = \gamma$.