Usando la existencia del número de Hartogs para demostrar la no numerabilidad de los números reales, y si este enfoque es equivalente al método de la diagonal

Question

Esta será mi última pregunta en una serie sobre la incuantificabilidad de los números reales. Mi conocimiento de la teoría de conjuntos es limitado, pero leí en algún lugar que la existencia del número de Hartogs se puede usar para demostrar el teorema de Cantor. Aquí limitaré el alcance a la incuantificabilidad del conjunto de números reales.

Mi pregunta:

1. ¿Cómo la existencia del número de Hartogs lleva a la incuantificabilidad? (preguntando por la prueba)
2. ¿Es esta prueba básicamente un enfoque de diagonalización?

Answer 1

Sea $\omega_1$ el menor ordinal incontable (garantizado por el resultado de Hartogs y la buena ordenación de los ordinales), y supongamos que $\mathbb{R}$ fuera numerable. Entonces obtenemos una sobreyección $\sigma$ de $\mathbb{N}$ a $\omega_1$, ya que los ordinales numerables pueden ser codificados por números reales (ver abajo para más detalles). Pero para cada $n\in\mathbb{N}$, el ordinal $\sigma(n)$ es numerable ya que $\omega_1$ es el menor ordinal incontable, lo que significa que $\omega_1$ puede ser escrito como una unión numerable de conjuntos numerables, lo que implica que $\omega_1$ es numerable, a través del Axioma de Elección.

Esto no es un argumento de diagonalización; sin embargo, es absolutamente terrible, ya que requiere tanto Reemplazo (mucho más fuerte que Separación, que es suficiente para la innumerabilidad de $\mathbb{R}$ mediante el argumento habitual) como Elección (ya que sin Elección es consistente que $\omega_1$ sea una unión numerable de conjuntos numerables).

---

Aquí tienes cómo codificar ordinales numerables como reales:

• Un ordinal numerable tiene el mismo tipo de orden que alguna relación binaria $R$ en $\mathbb{N}$ (ejercicio).

• Cualquier relación binaria $R$ en $\mathbb{N}$ puede ser codificada como un conjunto de números naturales - es decir, como $S_R=\{\langle a, b\rangle: aRb\}$, donde "$\langle\cdot,\cdot\rangle$" es tu función de emparejamiento favorita en $\mathbb{N}$ (digamos, la función de emparejamiento de Cantor).

• Finalmente, usa alguna de las inyecciones habituales $i$ de $\mathcal{P}(\mathbb{N})$ a $\mathbb{R}$, y decimos que un real $r$ codifica un ordinal numerable $\alpha$ si $r$ es la imagen bajo $i$ del conjunto que codifica a $R$ para algún $R$ de tipo de orden $\alpha$.

Answer 2

Aquí hay una prueba que no utiliza el axioma de elección.

Supongamos que $\mathbb{R}$ fuera numerable. Entonces $\mathscr{P}(\omega\times\omega)$ sería numerable, por un simple argumento de codificación. Se sigue que el conjunto $W$ de bien-ordenamientos de $\omega$ sería numerable, ya que $W\subseteq\mathscr{P}(\omega\times\omega).$

Sea $\langle w_n \mid n\lt\omega\rangle$ una enumeración de $W.$ Construye un bien-ordenamiento $w$ comenzando con $w_0,$ agregando $w_1,$ luego agregando $w_2,$ etc. Luego $w$ es un bien-ordenamiento de $\omega$ de tipo de orden mayor que cualquier ordinal numerable, lo cual es una contradicción. [Estrictamente hablando, construirías $w$ como un bien-ordenamiento de $\omega\times\omega,$ donde $\langle\langle m,a\rangle,\langle n,b\rangle\rangle\in w$ si $m\lt n$ o $(m=n \text{ y } \langle a,b\rangle\in w_m).$ Pero luego $w$ puede ser fácilmente codificado como un bien-ordenamiento de $\omega.]$

¿Cuál es la conexión con el teorema de Hartogs? Podrías ver la contradicción anterior como una contradicción al teorema de Hartogs (ya que $w$ sería un bien-ordenamiento de $\omega$ de tipo de orden al menos $\omega_1,$ que está garantizado de existir por el teorema de Hartogs), o, tal vez mejor, podrías verlo como una prueba inspirada por el teorema de Hartogs.

Para responder también a tu segunda pregunta, esto es realmente diferente de la diagonalización y no puede reformularse de esa manera.

Edición: Veo que esto es similar en espíritu a la respuesta de @NoahSchweber, pero está configurado para evitar el uso del axioma de elección (ya que no tomo un desvío a través de una unión numerable de ordinales numerables, sino que trato directamente con los bien-ordenamientos).