Teorema de incompletitud de Gödel


Kurt F. Gödel, en «Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas afines» [paráfrasis]:

«Existen argumentos lógicos imposibles de ser deducidos verdaderos o falsos; entre ellos, la coherencia de dichos razonamientos.»

La existencia verdadera o falsa de algo (por ejemplo, las piedras; al contrario, las hadas), no implica que la misma sea demostrable así, ni que deba o no tenerse fe en cualquiera de estas posibilidades.

·

La creatividad surge de hallar –pensando diferente del resto– ideas absurdas, para así nuevamente pensarlas y darles coherencia.

Ahí la importancia de la Lógica: porque sólo con ella es posible tanto hallar los absurdos como obtener la coherencia.

·

viernes, 10 de octubre de 2014

SOBRE LA NATURALEZA DE LA FUNCIÓN DE COLLATZ Y OTRAS AFINES. DEMOSTRACIÓN DE LA CONJETURA DE COLLATZ

de Alfredo Salvador C. García
Ciudad de México
 
Lothar Collatz, quien propuso la conjetura
que lleva su nombre y que se pretende
demostrar en la siguiente exposición.


DEFINICIONES Y ACOTACIONES

Antes de comenzar la exposición pretendida, se manifestará la siguiente definición:

Número de Collatz: Aquel número natural obtenido a partir de
un número de Collatz con la función de Collatz.

Por ello se indicará cuál es la función de Collatz:

C(x)={1. p(x), si C(x) es par; 2. q(x), si C(x) es impar.
y p(x)=2·x; q(x)=·(x-1)

Dado que p(x) admite en su dominio a cualquier número natural, el dominio de C(x) incluirá también a cualquier número natural, independientemente del dominio restringido de q(x) –que sólo está dado para sucesores de múltiplos de 3 cuya tercera parte es impar–.

Aparte, el contradominio de C(x) incluye a todos los naturales, pues considera tanto C(x) siendo par como C(x) siendo impar, y no hay restricción para ello.


DEMOSTRACIONES

Ahora se demostrará el siguiente

Teorema I. Todos los números naturales son números de Collatz.

Dado que los números se obtienen a partir de la función de Collatz (según la definición correspondiente) y el contradominio de aquélla está dado por todos los números naturales, basta para demostrar el Teorema I que el dominio esté compuesto por números de Collatz. Y bien, como el dominio de la función de Collatz es idéntico al contradominio de la misma, el Teorema I queda demostrado inmediatamente.

El Teorema I permitirá demostrar el

Teorema II. Todo número natural arrojará como resultado el número 1 al emplearse en sucesivas y suficientes ocasiones la función inversa de Collatz.

Este teorema es equivalente al

Teorema III. Todo número de Collatz arrojará como resultado el número 1 al emplearse en sucesivas y suficientes ocasiones la función inversa de Collatz.

Esto porque el Teorema I permite reemplazar las palabras «número natural» por las palabras «número de Collatz» sin impedimento alguno. La función inversa de Collatz es la siguiente:

C-1(x)={1. p-1(x), si x es par; 2. q-1(x), si x es impar.
y p-1(x)=½·x; q-1(x)=3·x+1

El dominio de esta función está dado por todos los números naturales (o todos los números de Collatz). Dado que el contradominio de p-1(x) no está restringido a los números naturales en general, el contradominio de la función inversa de Collatz también está dado por todos los números naturales (o todos los números de Collatz), independientemente del contradominio de q-1(x).

Así, la función inversa de Collatz puede emplearse con cualquier número de Collatz y se obtendrá siempre un número de Collatz. Es, pues, dicha función –al igual que la función de Collatz– generadora de todos los números de Collatz. Entonces, en la definición del número de Collatz pueden reemplazarse las palabras «función de Collatz» por las palabras «función inversa de Collatz».

Por la forma algebraica tanto de p-1(x) como de q-1(x), es posible observar que cada número de Collatz es generado sólo por un único número de Collatz a partir de la función inversa de Collatz. Concretamente, primero, a cada número le corresponde una sola opción sea p-1(x) ó q-1(x); luego, toda función del tipo f(x)=m·x+b genera un resultado único. Esto igualmente se reconoce por los mismos argumentos para la función de Collatz, es decir, que cada número de Collatz es generado sólo por un único número de Collatz a partir de la función de Collatz.

Con ello, partiendo del número 1 (que es un número de Collatz) y empleando en sucesivas ocasiones la función de Collatz se obtendrán todos los números de Collatz sin excepción: el 1 genera otro número de Collatz, luego el resultante genera otro, luego otros, y así sucesivamente con el potencial de generar todos los números de Collatz pues ha de cubrirse todo el contradominio de la función de Collatz sin dejar un sólo número faltante. Con la función inversa ocurre lo mismo: un número de Collatz debe generar otro número de Collatz, el resultante genera otro, luego otro, y así sucesivamente hasta completar todo el contradominio que pueda cubrir. De tal forma, entre todos los números de Collatz (o entre todos los números naturales) se debe cubrir todo el contradominio de la función inversa sin dejar un sólo número faltante.

El número 1 es tal que ningún número de Collatz lo generaría de inmediato, salvo el número 2. Si se toman todos los números de Collatz para emplear la función inversa en sucesivas ocasiones, se terminarían generando todos los números de Collatz excepto 1 por esa condición especial. En cualquier caso siempre sería el último número en ser generado, no importando el número de partida. Y podría preguntarse si realmente todos los números de Collatz terminan generando tarde o temprano al número 1 de forma individual. La respuesta es afirmativa porque tras sucesivas ocasiones de emplear la función inversa, se generará un número de Collatz, luego otro, luego otro, hasta llegar o bien a generar todos los números de Collatz excepto 1, o bien a generar 1, pues para completar el contradominio de la función inversa es necesario generar dicho número.

En otras palabras,

  1. Todos los números de Collatz que no sean 1 son generados para cubrir por completo el contradominio de la función inversa de Collatz.
  2. Todos los números generados podrán generar otros números de Collatz que siendo distintos de 1 estén en las mismas condiciones propuestas en la frase anterior.
  3. Sin embargo, las dos frases anteriores no permiten generar todos los números de Collatz necesarios para cubrir por completo el contradominio de la función inversa de Collatz, pues siempre faltaría el número 1.
  4. Luego, ha de admitirse que en la naturaleza misma de la función inversa de Collatz está dado el generar el número 1 a partir de todos los números de Collatz restantes, pues se ha visto con las frases anteriores que la existencia misma de todos ellos no implica necesariamente la generación del número 1.

Y es por el argumento 4 que el Teorema III queda demostrado. Los argumentos 1 y 2 constituyen lo que en el Teorema III se menciona como «al emplearse en sucesivas y suficientes ocasiones la función inversa de Collatz [para todo número de Collatz]». El argumento 3 se refiere a la naturaleza matemática de la función inversa de Collatz. Finalmente, el argumento 4 es consecuencia de los tres anteriores y declara la validez del Teorema III.



OBSERVACIONES

La demostración propuesta es un equivalente en palabras de lo que podría ser formalmente, empleando lógica de primer orden. Esperando que no sea necesario la implementación de lógica formal explícita (porque sí ha sido empleada de forma implícita en la retórica), queda generalizar el resultado en cuestión.

La validez del Teorema III (cuya demostración es aquélla para la conjetura de Collatz) radica en la definición de la función inversa y en las características que llevan de la misma a que el número 1 no pueda generarse de forma inmediata si no es con el número 2. Es más, empleando la función de Collatz para el número 1, es hasta 8 donde siguen obteniéndose resultados que de ninguna otra forma podrían obtenerse, es decir, que 8 sólo puede obtenerse a partir de 16, 4 únicamente a partir de 8, y 2 únicamente a partir de 4. Esto significa que el Teorema III podría enunciarse reemplazando el número 1 por el número 2, ó el 4, ó el 8, e incluso el 16, porque todos los números tendrían que desembocar en éste para generar los mencionados.

Defínase, aparte, una función que dé pie a dos opciones de cálculo, y que en conjunto tengan como dominio y contradominio a los números naturales. También que las opciones de cálculo sólo generen un resultado cada una y que un número dado sólo genere un resultado al emplearse la función inversa, la cual también tendrá como dominio y contradominio a los números naturales. Entonces el Teorema III podrá enunciarse con plena validez como sigue

Todos los números naturales arrojarán como resultado el número dado al emplearse en sucesivas y suficientes ocasiones la función definida.

Esto porque los argumentos 1, 2, 3 y 4 se observarán de la misma forma que con la función inversa de Collatz. Por ejemplo, sea la función inversa siguiente:

f(x)={1. p(x), si x no es múltiplo de 3; 2. q(x), si x es múltiplo de 3.
y p(x)=x+1; q(x)=⅓·x

El dominio está dado por todos los números naturales, porque entre los múltiplos de 3 y el resto de los naturales los conforman. El contradominio es idéntico al dominio porque q(x) permite calcular todos los números naturales.

Asimismo, la función inversa a la anterior:

f-1(x)={1. p-1(x), si f-1(x) no es múltiplo de 3; 
2. q-1(x), si f-1(x) es múltiplo de 3

 y p-1(x)=x-1; q-1(x)=3·x

El contradominio de esta función abarca todos los números naturales, porque entre los múltiplos de 3 y el resto de los naturales lo conforman. También el dominio abarca todos los números naturales (con p-1(x) se calculan todos los números naturales, aun cuando con q-1(x) se calculan sólo múltiplos de 3). Cada forma de cálculo, p(x) y q(x), sólo permite obtener un resultado único, lo mismo que sus correspondientes formas de cálculo inversas, p-1(x) y q-1(x). Entonces, según lo propuesto es posible enunciar el siguiente teorema:

Todos los números naturales arrojarán como resultado el número 1 al emplearse en sucesivas y suficientes ocasiones la función f(x).

Nuevamente el número final será 1 porque su única procedencia es f-1(3). Si se intentare que, aparte, sea p(x)=x+10, algún dominio o contradominio de cualquiera de las funciones (inversa o no) no abarcaría todos los números naturales y no podría enunciarse el Teorema III en ese caso siendo que los argumentos de su demostración sólo son válidos si el dominio y el contradominio se conforman por todos los números naturales.

En resumen, para que la demostración presentada valide un teorema semejante al Teorema III dada una función, esta última debe de presentar los siguientes rasgos:

  1. Que su dominio y su contradominio estén conformados por todos los números naturales.
  2. Que lo mismo ocurra con la función inversa.
  3. Que ambas funciones generen dos opciones de cálculo con una sola respuesta posible cada una.
  4. Que la función inversa sólo genere un resultado al ser empleada.

Porque, insistiendo, sólo así se garantiza tanto que los argumentos 1 y 2 puedan establecer cálculos consecutivos y suficientes, y que por la naturaleza de la función los números naturales sólo den pie a la obtención de números naturales hasta completar todo el contradominio de la función, incluyendo al número que finalmente sea de procedencia única.

10 de Octubre de 2014
 
 

No hay comentarios:

Publicar un comentario en la entrada