El argumento diagonal de Cantor: la coherencia de la secuencia construida para demostrar que 2[N] tiene una cardinalidad mayor que N

Question

Creo que entiendo bien cómo funciona el argumento de Cantor para demostrar cardinalidades mayores; pero tengo un problema continuo con una parte del mismo, a saber, la construcción del elemento (secuencia) que sirve para demostrar esa misma diferencia de cardinalidad, por ejemplo mostrando que dicha secuencia no está en la imagen de ninguna función de $N$ . Siguiendo la respuesta previamente publicada y muy detallada e informativa aquí: ¿Cómo funciona el argumento diagonal de Cantor? consideraré también el argumento para el caso de una función $f$ de $N$ a $2^N$ donde este último es un conjunto de todas las secuencias binarias.

La clave está en demostrar que para cualquier $f: N \to 2^N$ de modo que $f(n) = (a_{1n}, a_{2n}, ..., a_{kn}, ...)$ donde todos $a$ son $0, 1$ existe alguna $s_f$ una tupla binaria infinita, que no es igual a $f(n)$ para cualquier $n$ . La forma estándar de hacerlo parece ser "construir" $s_f$ por la siguiente regla:

$s_f = (s_1, s_2, ..., s_k, ...)$ tal que para el $f(n)$ en estudio,

$s_k = 1$ si $a_{kn} = 0$ y $s_k = 0$ si $a_{kn} = 1$

Ahora bien, esta definición por construcción nos da una tupla que es una inversa perfecta de la tupla devuelta por $f(n)$ para cualquier $n$ que nos importa considerar. En otras palabras, para cualquier $n$ , $s_f \neq f(n)$ por lo que concluimos que $s_f$ no es la imagen de $f$ y, por tanto $f$ no es suryectiva.

Ahora, la pregunta que me hago es ¿por qué no vamos un paso más allá? Si podemos definir una tupla deliberadamente frustrante $s_f$ ¿por qué no definir ahora una función $g(n): N \to 2^N = (b_{1n}, b_{2n}, ..., b_{kn}, ...)$ tal que $b_{kn} = s_{k}$ para $n = 1$ y $b_{kn} = a_{k(n-1)}$ para todos los demás $n$ ? Incluso se puede generalizar para cualquier $k$ tuplas que has conseguido que no estén en la imagen de $f(n)$ Enumere estas tuplas y defina $g$ añadiendo la imagen de $f(n)$ a la enumeración. Si definimos $g$ de esta manera, no $g$ sea suryectiva por construcción, al igual que $s_f$ no es a imagen y semejanza de $f(n)$ por la construcción?

Sin embargo, en términos más generales, me molesta esta pregunta: ¿realmente se puede intentar evaluar una igualdad entre un objeto, en este caso? $f(n)$ y otro objeto, en este caso, $s_f$ definido enteramente en términos del primer objeto? ¿No es $s_f$ un objeto de orden superior, o un tipo superior a $f(n)$ ? Parece que tratamos $s_f$ como si fuera una secuencia binaria infinita cualquiera, pero no lo es, ni siquiera podemos enderezarla en sus propios términos, hasta que sepamos $f$ . Se podría decir que $s_f$ es sólo un nombre para una secuencia binaria que está en algún lugar en $2^N$ sino porque definimos $s_f$ sea una secuencia que no esté en la imagen de $f(n)$ la propia afirmación de que $s_f$ se refiere a una secuencia existente en $2^N$ está afirmando nuestro mismo resultado - que hay elementos de $2^N$ que no son a imagen y semejanza de $f(n)$ . Sin embargo, no parece que hayamos hecho ningún trabajo para demostrar realmente que la secuencia que pretendemos construir mediante las reglas que definen $s_f$ es construible o que está en $2^N$ . ¿Es así? tienen estar en $2^N$ ¿sólo porque formulamos una regla sobre otra, indefinida, de cómo mapear los naturales en {0, 1}? ¿No supondría eso que $2^N$ se cierra bajo todas las operaciones insondables, lo que parece mucho pedir y, en cualquier caso, no está demostrado?

Answer 1

Por suerte, la teoría de conjuntos no es teoría de tipos. Así que no hay problema de "tipos". Y como tampoco estamos limitados a objetos definibles por tipos particulares de fórmulas (como la comparación de conjuntos recursivos y recursivamente enumerables), no hay problema aquí.

Sólo usamos $f$ como parámetro en la definición de $s_f$ . En concreto, tenemos una fórmula $\varphi(x,y)$ en el lenguaje de la teoría de conjuntos, que siempre que pongamos una función $f\colon\Bbb N\to2^\Bbb N$ el único $y$ que la satisface con $f$ es tal que $y\neq f(n)$ para todos $n$ .

¿Cómo se define esta fórmula? A grandes rasgos, algo así como "Si $x$ es una función cuyo dominio es $\Bbb N$ y para cada elemento del dominio, $x(n)$ es una función de $\Bbb N$ en $\{0,1\}$ Entonces $y$ es una función de $\Bbb N$ a $\{0,1\}$ tal que para todo $n\in\Bbb N$ se cumple que $1-y(n)=x(n)(n)$ ".

Así que si usted cree que este $\varphi$ es posible escribirlo en el lenguaje de la teoría de conjuntos, entonces los axiomas de la teoría de conjuntos te dicen que si fijamos $f$ entonces existe $y$ tal que $\varphi(f,y)$ es cierto. ¿Cómo es posible? Bueno, hay varias maneras, aquí hay una que es lo suficientemente general como para mantener cuando nos movemos de $\Bbb N$ a dominios más amplios:

Dado $n\in\Bbb N$ existe (un único) $t$ tal que $(n,t)\in f$ y existe (una única) $t_n$ tal que $(n,t_n)\in t$ . Esto se debe a que $f$ y $t$ son funciones. Por lo tanto, existe un valor único $y_n$ tal que $1-y_n=t_n$ . La fórmula:

$$\psi(n,u,f)=\exists t\exists v\exists w\Big((n,t)\in f\land (n,v)\in t\land w=1-v\land u=(n,w)\Big)$$

Si es funcional para $\Bbb N$ después de fijar $f$ como parámetro. Así que su rango es un conjunto. Pero su rango es exactamente $s_f$ que queríamos.

De hecho, podemos ir más allá y definir una fórmula que funcione uniformemente para cada $X$ no sólo $\Bbb N$ . Simplemente exigiendo que $f$ es una función de $X$ a $2^X$ etc.