Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Define $R(0)=0=\emptyset, R(n+1)=P(R(n))$ and $R(\omega) = \cup_{n < \omega} R(n)$. Thus $R(\omega)$ is the set of all sets, which are build out of finitely many braces and $0$.

Consider the following relation $E$ on $\omega$: If and only if the $n$th number in the binary representation of $m$ is $1$, then $n E m$. Now I want to construct an isomorphism $(R(\omega),\in) \cong (\omega,E)$ [This is an exercise in Kunen's set theory]. After some playing around I've come up with the following definition:

$g : R(\omega) \to \omega, g(x) = \sum_{y \in x} 2^{g(y)}$.

This is a well-defined recursion, since $rank(y) < rank(x)$. If $g$ is injective, then it is easy to see that $x \in y \Leftrightarrow g(x) E g(y)$. However I don't see this; neither why $g$ is surjective.

share|cite|improve this question
Which exercise in Kunen's book is this? – Carl Mummert Sep 3 '10 at 14:47
There are other ways to define a well ordering on $R(\omega)$ which are simpler, in my opinion. However this one is real nice. – Asaf Karagila Sep 3 '10 at 14:58
up vote 3 down vote accepted

Take the minimal $n$ such that there are $x,y \in R(\omega)$ for which $x \not= y$ and $g(x)=g(y)=n$.

If $g(x) = g(y)$ then we know the following: $|x| = |y|$ and $\forall u \in x \exists v \in y (g(u) = g(v))$ but since it is clear that $u \in v \Rightarrow g(u) < g(v)$ we have that there is some $u \in x, v\in y$ for which $g(u) = g(v) < g(y) = n$ which contradictions the assumption.

I've got no idea about the surjective part. Seems slightly tricky, but I'll get back to you when I have an answer.

We know that $g(\emptyset) = 0$.

Let $n$ be the minimal number that is not in the range of $g$, we can write $n = 2^{n_0}+\ldots +2^{n_k}$ where $n_0 < n_1 < \ldots < n_k$. Since $n_i < n$ we have that there is $x_i \in R(\omega)$ for which $g(x_i) = n_i$. So now we can take $x = \{x_i |0\le i\le k\}$ and it is a simple argument that $x \in R(\omega)$ and clearly $g(x) = n$.

share|cite|improve this answer
Thanks you for this nice proof. :) – Martin Brandenburg Sep 3 '10 at 17:10
I've come a long way. That was my ninth answer on this site... – Asaf Karagila Oct 20 '12 at 21:27

It is easier to build the isomorphism in the other direction, and indeed we can see that the map is forced upon us. There is a unique isomorphism.

Specifically, you want a map $h:\mathbb{N}\to R(\omega)$ such that $n\mathrel{E} m\iff h(n)\in h(m)$. This very equivalence tells you that you must define $h(m)=\{ h(n) \mid n\mathrel{E} m\}$. This function is defined by recursion, and obviously preserves $E$ to $\in$. Thus it is injective. It is surjective because your function $g$ is the inverse. QED

If one knows about the Mostowski collapse, then you can see immediately that $h$ is precisely the Mostowski collapse of $(\mathbb{N},E)$, which is a well-founded extensional relation. This provides another way to see that $h$ is an isomorphism.

share|cite|improve this answer
Thank you! This makes it very clear. – Martin Brandenburg Sep 4 '10 at 11:11

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.