# A nice enumeration of $R(\omega)$

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.

-
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

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

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

-
Thank you! This makes it very clear. – Martin Brandenburg Sep 4 '10 at 11:11