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