Download - Consecuencias raras
Algunas consecuencias extrañas del método de
diagonalización
2 de noviembre de 2011
Resumen
1. Si no se dice otra cosa, se entenderá por método de diagonalización o
simplemente diagonal una construcción de tipo matricial en la que cada
línea consiste en una secuencia in�nita enumerable de expresiones ob-
tenidas de un vocabulario enumerable previamente determinado. Esta
matriz es capaz de generar grá�camente nuevas secuencias que pueden
coincidir o no con las ya existentes. Una de ellas, la antidiagonal �que
representaremos como δ∗� tiene la propiedad, como es bien sabido, de
no pertenecer nunca a la matriz en la que se genera. Esta peculiaridad
es la que ha servido para hacer progresar los más diversos argumentos
por diaginalización. Existen, como es obvio, versiones algebraicas del
método diagonal que minimizan el componente grá�co del argumento,
pero en este caso y para lo que nos ocupa es preferible tenerlo bien
presente.
2. Una de las principales características de los argumentos diagonales es
que se aplican a conjuntos de entidades como un medio de demostrar
de manera conclusiva que tales conjuntos no son enumerables, ya sea de
forma efectiva o en términos de cardinalidad. Es decir, se emplean para
concluir negativamente lo que en muchas ocasiones comenzó siendo
una conjetura favorable acerca de la enumerabilidad del conjunto en
cuestión. En el caso de los números reales, lo esperable, al menos a
juzgar por lo encontrado en el caso de otros conjuntos in�nitos con
propiedadades muy distintas �N,E,Q� era que se pudiera establecer su
enumerabilidad de algún modo. La prueba diagonal de Cantor resuelve
la ausencia de un resultado positivo demostrando su imposibilidad. Es
esta característica la que hace que rara vez se nos ocurra aplicar el
método de diagonalización sobre conjuntos que sí son enumerables ya
que en ese caso no hay nada que dirimir. En tales casos, el método
diagonal no puede concluir teniendo que fracasar obligatoriamente en
1
algún punto de su construcción. Es precisamente aquí donde surgen
algunas hipótesis curiosas que merece la pena analizar.
3. Tomaremos como conjunto experimental el formado por todos los sub-
conjuntos �nitos de las naturales y lo representaremos como Pf (N).Sabemos que se trata de un conjunto enumerable y además de ma-
nera efectiva y en consecuencia el método diagonal tiene que fracasar
en algún punto. Primero probaremos, no obstante, la enumerabilidad
efectiva de Pf (N). Considérese la secuencia in�nita p0, p1, p2, ...pi, ...formada por los primos en su orden natural. Sirviéndonos del teorema
fundamental de la Aritmética podemos hallar la descomposición facto-
rial de cualquier número en términos de potencias de primos. Despre-
ciaremos aquellos que dan lugar a series en las que algún primo está
elevado a un exponente distinto de la unidad. Es obvio que los naturales
cuyas descomposiciones factoriales son secuencias de primos elevados a
la unidad pueden usarse para representar secuencias binarias in�nitas
que contengan a lo sumo un número �nito de 1's. Esto se aprecia en el
siguiente grá�co:
p0 p1 p2 · · · pi · · ·0 1 1 · · · 0 · · ·
Por otra parte cada secuencia binaria que contenga a lo sumo un nú-
mero �nito de unos dará lugar a un producto de primos que sirve como
base para la enumeración efectiva de Pf (N).
4. Con este recurso podemos asegurar la existencia de una matriz binaria
del tipo
0 1 2 · · · i · · ·0 1 1 · · · 0 · · ·
. . .
0 1 1 · · · 1 · · ·
que enumera completamente el conjunto Pf (N). Como es habitual, usa-
remos el término diagonal �δ� para referirnos a la secuencia binaria
〈x00, x11, · · · , xii, · · ·〉 y antidiagonal �δ∗� para la secuencia 〈x∗00, x∗11, · · · , x∗ii, · · ·〉obtenida al permutar los 0'1 y 1's de δ. Puesto que Pf (N) es efecti-
vamente enumerable por un argumento independiente y δ∗ no puede
ser una de las secuencias sn en M, no importa lo que esta represente,
llegamos a la conclusión de que la secuencia δ∗ no puede representar
una secuencia binaria que conste de un número �nito de 1's.
5. Lo que resulta extraño en esta conclusión, por otra parte perfecta-
mente esperable, es la aparente existencia de una conexión entre la
2
existencia de una forma de enumerar, ordenar, colecciones de secuen-
cias binarias �el resultado se puede generalizar a cualesquiera tipos de
secuencias� y ciertas propiedades combinatorias de la secuencia anti-
diagonal. No importa cómo se obtenga la enumeración del conjunto
original, ni el principio representacional aplicado en la obtención de la
matriz, siempre existirá un rasgo combinatorio de la antidiagonal que
viola el principio de representación compartido por las secuencias de la
serie. Podemos enunciar el resultado de forma máximamente general
del siguiente modo:
Teorema 1 Sea C un conjunto efectivamente enumerable. Sea MC una
matriz obtenida a partir de C mediante algún criterio de representación
c. Si MC es una enumeración completa de C entonces
a) la secuencia δ∗ obtenida partir de la matriz MC de�ne un objeto
según c que no pertenece a C.
b) La secuencia δ∗ posee propiedades combinatorias que no corres-
ponden a ninguna de las secuencias en MC.
Conjetura 1 Sea M una matriz binaria. Entonces para que M re-
presente un conjunto enumerable según un criterio c es necesario y
su�ciente que exista una propiedad combinatoria de la secuencia an-
tidiagonal δ∗ que viole el criterio representacional c característico de
todas las secuencias en M.
Este misterioso criterio representacional c no es otra cosa que la con-
vención que en cada caso se adopta para transformar un elemento en
C en una secuencia de aquellas que pueden pertenecer propiamente
a una matriz binaria o del tipo que sea. Lo sorprendente es que una
enumeración directa de C que, como es lógico no tendrá nada que ver
con el principio c, sea capaz de determinar, sea cual sea este principio,
una propiedad combinatoria de la antidiagonal δ∗.
6. Y una vez expuesto el problema, quizá lo que corresponde es analizar
si hay o no caso, es decir, si realmente hay algo de lo que sorprenderse.
Supongamos por un momento una matriz en la que hemos alojado de
forma ordenada todas las secuencias numéricas binarias que contienen
un número �nito de 1's. Como ya ha quedado claro esa enumeración es
completa y por tanto la secuencia δ∗ debe contener un número no �nito
de 1's. Ahora bien, ¾podríamos admitir la inexistencia de una prueba
directa de ese hecho a partir tan solo de la colocación de las secuencias
binarias en la matriz? Esta conjetura resume bastante bien el tipo de
extrañeza a que hace referencia este texto. Hay que reconocer por otra
parte que se trata de una hipótesis altamente improbable, ya que no se
3
re�ere a la di�cultad o no de una prueba sino a su posible inexistencia.
Pero aún es posible radicalizar esta hipótesis un poco más. Téngase en
cuenta que también sería muy extraño que existieran en general prue-
bas directas acerca de las propiedades combinatorias de δ∗ en un gran
número de matrices, pero no es todas. Parece que deberíamos exigir que
para cualquier posible forma de colocar en una matriz la serie completa
de las secuencias binarias mencionadas existiera siempre una prueba
directa de que la antidiagonal δ∗ viola el criterio de representación c
empleado para construir la matriz MC. Y esto no siempre parece fácil:
0 1 2 · · · i · · ·1 0 0 · · · 0 · · ·0 1 0 · · · 0 · · ·1 1 0 · · · 0 · · ·0 0 1 · · · 0 · · ·1 0 1 · · · 0 · · ·1 1 1 · · · 0 · · ·
Esta matriz se ha construido siguiendo una estrategia puramente com-
binatoria en la que vamos agotando las combinaciones de subsecuencias
�nitas de longitud n. La primera secuencia de la serie n+1 será una
secuencia del tipo 〈0, 0, · · · , 1, 0, 0, · · ·〉, donde el único 1 ocupa exacta-
mente la n+1-ésima posición. A la luz de esta matriz no es inmediato
ver que esa ordenación garantiza que δ∗ no contenga más 1's a partir
de un cierto modo, aunque tampoco es imposible.
7. En cualquier caso, resulta más llamativo exigir que sea cual sea la forma
de colocar las secuencias siempre podamos garantizar desde argumen-
tos puramente combinatorios la bondad de δ∗, por mucho que sepamos
que así debe ser. Supongamos que partimos de una matriz completa
para el conjunto de secuencias binarias con un número �nito de 1's
y consideremos ahora una matriz M′C obtenida eligiendo en un orden
cualquiera las secuencias de MC. Parece evidente que M′C también es
una representación completa de C y por tanto su antidiagonal debe in-
cumplir el criterio de representación de la matriz. Ahora bien, puesto
que no tenemos una norma para construir M′C es obvio que tampoco
podemos establecer de forma directa nada acerca del aspecto de δ∗.
Este ejemplo, no obstante, es algo truculento ya que apela indirecta-
mente al axioma de Elección y por tanto no puede considerar que en ese
caso tengamos una construcción de δ∗, sino a lo sumo una estipulación
sobre su existencia.
.........
4