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

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
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

Generalising the answer of Martin.

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

share|cite|improve this answer

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.