Pruebas de la incontabilidad de los reales

Question

Recientemente, aprendí en mi clase de análisis la prueba de la incontabilidad de los reales a través de la Teorema del intervalo anidado ( La máquina del retroceso ). Al principio, me entusiasmó ver una prueba variante (ya que no utilizaba el argumento diagonal explícitamente). Sin embargo, a medida que pasaba el tiempo, empecé a ver que la prueba no era más que la antigua velada bajo una nueva terminología. Así que, hasta ahora, creo que cualquier prueba de la incontabilidad de los reales debe utilizar el argumento diagonal de Cantor.

¿Está justificada mi creencia?

Gracias.

Answer 1

Las matemáticas aún no están preparadas para demostrar resultados de la forma "Toda demostración del teorema T debe utilizar Argumento A". Piensa detenidamente en cómo podrías intentar demostrar algo así. Tendrías que establecer algunos sistema plausible para las matemáticas en la que el argumento diagonal de Cantor está bloqueado y los reales son contables . Nadie tiene idea de cómo hacerlo.

Lo mejor que puedes esperar es mirar cada prueba caso por caso y decidir, subjetivamente, si es "esencialmente el argumento diagonal disfrazado". Si tienes suerte, te encontrarás con una que tu intuición te diga que es una prueba fundamentalmente diferente, y eso resolverá la cuestión a tu satisfacción. Pero si eso no ocurre, lo máximo que podrás decir es que cada conocido la prueba parece a usted para ser el mismo. Como se ha explicado anteriormente, no podrá concluir definitivamente que todos los argumentos posibles debe utilizar la diagonalización.

ADDENDUM (agosto de 2020). Normann y Sanders tienen un un documento muy interesante que arroja nueva luz sobre la incontabilidad de $\mathbb R$ . En particular, estudian dos formulaciones específicas de la incontabilidad de $\mathbb R$ :

$\mathsf{NIN}$ : Para cualquier $Y:[0,1] \to \mathbb{N}$ existe $x,y \in [0,1]$ tal que $x\ne_{\mathbb{R}} y$ y $Y(x) =_{\mathbb{N}} Y(y)$ .

$\mathsf{NBI}$ : Para cualquier $Y[0,1] \to \mathbb{N}$ o bien existe $x,y \in [0,1]$ tal que $x\ne_{\mathbb{R}} y$ y $Y(x) =_{\mathbb{N}} Y(y)$ o existe $N\in\mathbb{N}$ tal que $(\forall x\in [0,1])(Y(x) \ne N)$ .

Uno de sus resultados es que un sistema llamado ${\mathsf Z}_2^\omega$ no demuestra $\mathsf{NIN}$ . Su modelo de $\neg\mathsf{NIN}$ puede interpretarse, por tanto, como una situación en la que los reales son contables. No obstante, aún estamos lejos de demostrar que el argumento diagonal de Cantor es necesario para probar que los reales son incontables. Otra advertencia es que Normann y Sanders sostienen que la incomprobabilidad de $\mathsf{NIN}$ en ${\mathsf Z}_2^\omega$ -lo que a primera vista podría sugerir que $\mathsf{NIN}$ es un axioma fuerte- es un resultado artificial, y que el marco adecuado para estudiar $\mathsf{NIN}$ y $\mathsf{NBI}$ es lo que llaman una "escala no normal", en la que $\mathsf{NIN}$ y $\mathsf{NBI}$ son muy débiles. En particular, su documento da muchos ejemplos de afirmaciones que implican $\mathsf{NIN}$ y $\mathsf{NBI}$ . Sospecho, sin embargo, que probablemente sentirás que las pruebas de esos otros enunciados introducen a escondidas el argumento diagonal de Cantor de una manera u otra.

Answer 2

Los lógicos matemáticos suelen bromear diciendo que el método diagonal es el único método de prueba que tenemos en lógica. Este método es la idea principal detrás de un gran número de resultados fundamentales, entre ellos:

• La incontabilidad de los reales.

• De manera más general, el hecho de que el conjunto de la potencia $P(X)$ de un conjunto es estrictamente mayor en cardinalidad.

• La paradoja de Russell.

• La indecidibilidad del problema de detención.

• El teorema de la recursión.

• De forma más general, grandes partes de la teoría de la computabilidad se basan en la diagonalización, como los usos del método de la prioridad.

• El lema del punto fijo y su uso para demostrar el teorema de Incompletitud.

• El rigor de la jerarquía aritmética, la jerarquía proyectiva, etc.

• etc. etc.

Answer 3

¿Y si se utiliza la medida exterior de Lebesgue? El intervalo $[0,1]$ tiene la medida exterior de Lebesgue 1, mientras que los conjuntos contables tienen la medida exterior de Lebesgue $0$ .

A efectos de la demostración, defino la medida exterior de Lebesgue $\mathcal{L}(E)$ de un conjunto $E\subset\mathbb{R}$ como el mínimo de las sumas $\sum_i (b_i-a_i)$ , donde $E\subset \bigcup_i (a_i,b_i)$ (por ejemplo, el mínimo es sobre todas las coberturas contables por intervalos abiertos).

Es una consecuencia directa de la definición que cualquier conjunto contable tiene la medida exterior de Lebesgue 0. Esto se puede demostrar incluso en el espíritu de la primera sugerencia de Gowers: supongamos que $f:\mathbb{Q}\cap (0,1)\to A$ es una biyección. Entonces, dado $\varepsilon>0$ la familia $$\{ ( f(p/q)-\varepsilon/q^3, f(p/q)+\varepsilon/q^3): p/q\in [0,1], \text{g.c.d.}(p,q)=1\}$$ es una cubierta de $A$ por intervalos, tal que la suma de las longitudes es $O(\varepsilon)$ .

Para demostrar que $\mathcal{L}([0,1])=1$ La afirmación clave es la siguiente: Sea $\{ (a_i,b_i)\}$ sea una cobertura finita del intervalo $[c,d]$ sin una subcubierta adecuada. Entonces $\sum_i (b_i-a_i) > d-c$ .

La afirmación se demuestra por inducción en el número de elementos de la cubierta. Es claramente cierta si la cubierta tiene un solo intervalo. Ahora bien, si $[c,d] \subset \bigcup_{i=1}^n (a_i,b_i)$ con $n>1$ entonces $[c,d]\backslash (a_1,b_1)$ es un intervalo cerrado $I$ o la unión $I\cup I'$ de dos intervalos cerrados disjuntos. En el primer caso $\bigcup_{i=2}^n (a_i,b_i)$ es una cubierta de $I$ y le aplicamos la hipótesis inductiva. En caso contrario, $\{(a_i,b_i)\}_{i=2}^n$ puede dividirse en dos subfamilias disjuntas, una que abarca $I$ y una que cubre $I'$ . A continuación, aplicamos la hipótesis inductiva a estas familias. (Utilizamos la propiedad de que la cubierta original no tiene una subcubierta adecuada para asegurarnos de que las cubiertas de $I$ y $I'$ son disjuntos).

Ahora bien, la reivindicación y la compacidad de $[0,1]$ (es decir, Heine-Borel) producen que $\mathcal{L}([0,1])\ge 1$ .

Por lo tanto, $[0,1]$ es incontable y también lo es $\mathbb{R}$ .

Answer 4

Alternativamente,

Demuestra que los reales están conectados.

Demostrar que todo subconjunto denso contable $X$ de los reales debe ser de orden isomorfo a los racionales.

Demuestra que los racionales no están conectados.

Answer 5

Pensé en esta cuestión hace un tiempo, mientras impartía un curso sobre temas. Dado que se puede comprobar fácilmente que $${}|{\mathbb R}|=|{\mathcal P}({\mathbb N})|$$ mediante una construcción directa que no implique la diagonalización, la cuestión puede replantearse como

¿Existe una prueba del teorema de Cantor que ${}|X|<|{\mathcal P}(X)|$ ¿que no es un argumento diagonal?

Sospecho que lo siguiente funciona. Incluso si no lo hace, creo que puede haber algún interés en esta presentación (Por favor, hágamelo saber si usted ve la diagonalización en alguna parte).

Un comentario de François Dorais me ayudó a (re)localizar el argumento en la prensa. Se presenta en A. Kanamori-D. Pincus. "Does GCH imply AC locally?", en Paul Erds y sus matemáticas, II (Budapest, 1999) 413-426, Bolyai Soc. Math. Stud. 11, János Bolyai Math. Soc., Budapest, 2002. Creo que en realidad se remonta al artículo de Zermelo de 1904 sobre el buen ordenamiento. (Ahora creo que aprendí el argumento de Kanamori-Pincus, ya que ciertamente utilicé el documento en el curso de temas).

a. Es evidente que hay una inyección $g:X\to{\mathcal P}(X)$ . Basta con demostrar que no hay suryección. Supongamos que la hay, y llamémosla $f$ . Entonces $f^{-1}:{\mathcal P}^2(X)\to{\mathcal P}(X)$ es 1-1.

(Si $h:A\to B$ , $h^{-1}:{\mathcal P}(B)\to{\mathcal P}(A)$ es el mapa que a $C\subseteq B$ asigna $\{a\in A\mid h(a)\in C\}$ . Desde $f$ es suryente, tenemos que $f^{-1}$ es inyectiva).

(Por supuesto, podríamos utilizar simplemente una inyección $g:{\mathcal P}(X)\to X$ e invocar a Schröder-Bernstein en este punto, pero este camino parece más corto).

b. No hay inyección $F:{\mathcal P}(Y)\to Y$ para cualquier conjunto $Y$ . La razón es que para cualquier $F$ podemos (definitivamente de $F$ ) producen un par $(A,B)$ con $A\ne B$ y $F(A)=F(B)$ . En efecto, Zermelo demostró que:

Para cualquier $F:{\mathcal P}(Y)\to Y$ hay un ordenamiento único $(W, \lt)$ con $W\subseteq Y$ tal que:

1. $\forall x\in W (F (\{y W \mid y \lt x\}) = x)$ y
2. $F (W )\in W$ .

Podemos entonces tomar $A=W$ y $B=\{y\in W\mid y\lt F(W)\}$ .

c. Teorema de Zermelo se puede demostrar de la siguiente manera: Basta con observar que $W=\{a_\alpha\mid \alpha\lt \beta\}$ donde $$ a_\alpha= F(\{a_\gamma\mid \gamma\lt \alpha\}) $$ y $\beta$ es mayor para que esta secuencia sea inyectiva.

Que $\beta$ existe es una consecuencia de Teorema de Hartogs que para cualquier conjunto $A$ hay un mínimo ordinal $\alpha$ no se inyecta en $A$ .

La singularidad de $W$ se muestra considerando el primer lugar donde dos candidatos potenciales para $(W, \lt)$ no está de acuerdo.

d. El teorema de Hartogs se demuestra observando que si $\alpha$ es un ordinal y se inyecta en $A$ entonces hay un subconjunto $B$ de $A$ y una relación binaria $R$ en $B$ tal que $(B,R)$ es de orden isomorfo a $\alpha$ . De esto se desprende fácilmente que la colección de $\alpha$ s que se inyectan en $A$ forma un conjunto, que es de hecho un ordinal $\beta$ . Entonces $\beta$ es lo mínimo que no inyecta en $A$ .

---

Permítanme terminar con un comentario y una pregunta: La prueba anterior es formalizable en ZF, sin elección. De hecho, el teorema de Zermelo es demostrable sin utilizar la sustitución, aunque el argumento que he esbozado la utiliza.

La cuestión se menciona en Kanamori-Pincus: Demostramos que si $F:{\mathcal P}(Y)\to Y$ entonces $F$ no es inyectiva al presentar un par $(A,B)$ con $F(A)=F(B)$ . Si en lugar del argumento de Zermelo hubiéramos utilizado en este punto la construcción a partir del argumento de la diagonal, habríamos tomado $$ A=\{y\in Y\mid \exists Z(y=F(Z)\notin Z)\}, $$ y comprobado que debe haber un $B\ne A$ con $F(A)=F(B)$ .

¿Podemos definir tal $B$ de $F$ ?

( Actualización: En general, la respuesta a la pregunta es no. Véase aquí .)

---

Actualización, 6 de septiembre de 2017: Permítanme añadir algunas observaciones adicionales. En primer lugar, en los comentarios, Martin Brandenburg preguntó por qué había que molestarse en intentar obtener una prueba "sin diagonalización". El hecho de que la prueba anterior evite la diagonalización es quizás simplemente una curiosidad (aunque uno se queda con la pregunta de cómo definir precisamente "libre de diagonalización"); lo que importa es que el argumento da un poco más que el de Cantor: Como señalé en un comentario, la prueba que acabamos de dar muestra que 1) La colección de subconjuntos bien ordenables de $X$ tiene un tamaño estrictamente mayor que $X$ . Esto supone una mejora respecto al resultado de Cantor en el contexto de $\mathsf{}$ . 2) Dado cualquier $f\!:\mathcal P(X)\to X$ podemos encontrar $A\subsetneq B$ con $f(A)=f(B)$ . Esto también es un refuerzo de la combinatoria, y se puede llevar más allá. Stevo Todorcevic, en particular, obtuvo varias extensiones de esta idea, véase esta respuesta en Math.Stackexchange.

En segundo lugar, el teorema de Hartogs puede utilizarse para proporcionar una prueba diferente (también "sin diagonalización") del resultado de Cantor, y establecer de hecho una generalización en el contexto de los conjuntos cuasi-ordenados, debida a Gleason y Dilworth. Para el bonito argumento y las referencias apropiadas, véase aquí .