Una bonita enumeración de $R(\omega)$

Question

Definir $R(0)=0=\emptyset, R(n+1)=P(R(n))$ y $R(\omega) = \cup_{n < \omega} R(n)$ . Así, $R(\omega)$ es el conjunto de todos los conjuntos, que se construyen a partir de un número finito de llaves y $0$ .

Considere la siguiente relación $E$ en $\omega$ : Si y sólo si el $n$ número en la representación binaria de $m$ es $1$ entonces $n E m$ . Ahora quiero construir un isomorfismo $(R(\omega),\in) \cong (\omega,E)$ [Es un ejercicio de teoría de conjuntos de Kunen.] Después de jugar un poco he llegado a la siguiente definición:

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

Se trata de una recursión bien definida, ya que $rank(y) < rank(x)$ . Si $g$ es inyectiva, entonces es fácil ver que $x \in y \Leftrightarrow g(x) E g(y)$ . Sin embargo no veo esto; tampoco por qué $g$ es suryente.

Answer 1

Tome el mínimo $n$ de manera que haya $x,y \in R(\omega)$ para lo cual $x \not= y$ y $g(x)=g(y)=n$ .

Si $g(x) = g(y)$ entonces sabemos lo siguiente: $|x| = |y|$ y $\forall u \in x \exists v \in y (g(u) = g(v))$ pero como está claro que $u \in v \Rightarrow g(u) < g(v)$ tenemos que hay algo de $u \in x, v\in y$ para lo cual $g(u) = g(v) < g(y) = n$ lo que contradice la suposición.

No tengo ni idea de la parte subjetiva. Parece un poco complicado, pero te contestaré cuando tenga una respuesta.

Sabemos que $g(\emptyset) = 0$ .

Dejemos que $n$ sea el número mínimo que no está en el rango de $g$ podemos escribir $n = 2^{n_0}+\ldots +2^{n_k}$ donde $n_0 < n_1 < \ldots < n_k$ . Desde $n_i < n$ tenemos que hay $x_i \in R(\omega)$ para lo cual $g(x_i) = n_i$ . Así que ahora podemos tomar $x = \{x_i |0\le i\le k\}$ y es un simple argumento que $x \in R(\omega)$ y claramente $g(x) = n$ .

Answer 2

Es más fácil construir el isomorfismo en la otra dirección, y de hecho podemos ver que el mapa es forzado. Hay un isomorfismo único.

En concreto, quiere un mapa $h:\mathbb{N}\to R(\omega)$ tal que $n\mathrel{E} m\iff h(n)\in h(m)$ . Esta misma equivalencia le dice que debe definir $h(m)=\{ h(n) \mid n\mathrel{E} m\}$ . Esta función está definida por recursión, y obviamente preserva $E$ a $\in$ . Por tanto, es inyectiva. Es suryectiva porque su función $g$ es la inversa. QED

Si uno conoce el colapso de Mostowski, entonces puede ver inmediatamente que $h$ es precisamente el colapso Mostowski de $(\mathbb{N},E)$ que es una relación extensional bien fundada. Esto proporciona otra forma de ver que $h$ es un isomorfismo.