¿No sería el conjunto real más pequeño que el conjunto entero?

Question

Esto está relacionado con Conjuntos de números naturales y reales, ¿cuál es mayor que otro? pero está claro que mi pregunta es de otra naturaleza.

Hola,

Me gustaría hacer una pregunta a la comunidad: ¿Por qué se dice que los "reales" son "más grandes" que los "enteros"?

---

Ahora bien, conozco bien el argumento de la diagonal, pero me parece que no hay ninguna conexión lógica con mayor, e incluso que el conjunto real es efectivamente menor que el conjunto entero. Voy a tratar de explicar, utilizando sólo argumentos lógicos, porque no sé mucho acerca de las matemáticas, pero espero que mediante el uso de la lógica voy a ser capaz de comunicarse con la comunidad matemática y ser capaz de entender lo que está mal en mi comprensión.

---

En primer lugar, me gustaría intentar definir algunas palabras que voy a utilizar: Supongamos que existe un lenguaje completo de turing L, con el que se pueden escribir programas, de tal manera que el programa puede procesar una cadena finita, y producir otra cadena finita, y tiene una instrucción terminal (es decir, los programas pueden terminar).

Entonces llamemos Programa, a algo escrito en L, que toma como entrada un entero (digamos como una cadena finita de 0/1), y da como salida 0 o 1 (pero no tiene garantía de terminar). Llamemos "Lista" a un programa que toma como entrada un entero, y como salida una cadena finita, y se garantiza que termina para cualquier entero de entrada. Llamemos "Subparte del Conjunto Entero" (abreviado como SI) a un Programa que de alguna manera está garantizado que termina para cualquier entrada entera. (Así que cualquier SI es a la vez una lista y un programa)

Llamemos Lista maximal (de un criterio C), a una lista (si existe) que dado el criterio C lista todas las cadenas de salida que cumplen C.

---

Así que ahora podemos decir que efectivamente existe una lista máxima de Programas (trivial de explicitar), y que no existe una Lista máxima de SI (porque si existiera, entonces serías capaz de tener un programa que respondiera al problema de terminación para cualquier entrada).

Ahora bien, hay otra forma de darse cuenta de que no existe una Lista máxima de SI, y es aplicar la "estrategia diagonal".

Supongamos que existe una Lista explícita de todos los SI llamada Lista_SI, entonces se puede construir un nuevo SI : nuevo_SI (n) : - let a = Lista_SI (n) (n). Si a = 0 devuelve 1, si no devuelve 0; nuevo_SI está en 0/1 y termina, por lo que es definitivamente un SI.

Ahora bien, esto me parece exactamente el argumento diagonal utilizado por Cantor, que permite concluir que el "Conjunto Real" es "Más Grande" que el "Conjunto Entero". Sólo que sustituimos el conjunto real por la lista de programas que representan una subparte de N, y el conjunto entero por una generalización a programas que representan una subparte de N pero que pueden dejar algún entero ni dentro ni fuera de la subparte que representa.

Por lo tanto, tenemos que concluir que el Programa que termina Conjunto (SI) es Mayor que el conjunto de todos los programas (Programa). Wich me parece un poco contra intuitivo. De hecho, yo tendería a suponer que el conjunto de programas que terminan es, de hecho, más pequeño.

---

Y ahí estoy yo, preguntando a la comunidad matemática: ¿no sería el "conjunto real" efectivamente "más pequeño" que el "conjunto entero"?

Answer 1

Perdón: utilizaré la palabra "programa" en su significado correcto, es decir, algo que tiene como entrada un número y como salida un número, o no termina.

Te recuerdo la noción de enumerable recursivamente conjunto: un subconjunto $A \subseteq \Bbb{N}$ es recursivamente enumerable si existe un programa $L(n)$ tal que $$\{ L(n): n \in \Bbb{N} \} = A$$

Es cierto que se pueden listar todos los programas: así se obtiene una lista universal $U(n)$ enumerando todos los programas. En particular $$\{ n \in \Bbb{N} : U(n) \mbox{ is a program} \} = \Bbb{N}$$ es recursivamente enumerable.

Ahora, lo que has probado es que $$\{ n \in \Bbb{N} : U(n) \mbox{ is a SI (i.e. it always terminates with $ 0 $ or $ 1 $)} \}$$ no es recursivamente enumerable. Este es un resultado importante en la teoría de la computabilidad, debido al propio Turing.

A pesar de ser recursivamente enumerable, $\Bbb{N}$ tiene algunos subconjuntos no enumerables recursivamente. Pero esto no significa que la colección de SI sea mayor que la colección de programas. En absoluto.

Este resultado significa que puede listar todos los programas, pero no tiene forma alguna de Decidir cuál de ellos es un SI y cuál no. Así que, en particular, no hay manera de asegurar que un programa es una lista (esto se refiere a su frase "se garantiza que termina para cualquier entrada de enteros": no se puede tener una garantía).