15.2.16
¿Coincidencia?
Comparen los lectores el texto en este enlace: Apolonio, de Miguel de Guzmán...
... con este otro: Apolonio, unos años más tarde.
... con este otro: Apolonio, unos años más tarde.
9.2.16
Todos los axiomas
Después de años de trabajo discontinuo, finalmente, esta misma tarde he terminado de escanear y subir al blog correspondiente todos los números publicados de la revista Axioma. Pueden descargarse desde este enlace.
8.2.16
Cómo visualizar la Hipótesis del Continuo
Una visualización de la Hipótesis del Continuo
(Basado fuertemente en una idea del filósofo Chris Freiling)
Tomemos un cuadrado... que en realidad puede ser cualquiera, pero, para facilitar la explicación, supondremos que es el cuadrado cuyos vértices son los puntos (0,0), (0,1), (1,0) y (1,1). A su vez, sobre cada punto (t, 0),con t entre 0 y 1, dibujaremos un segmento vertical de longitud 1, y en cada uno de esos segmentos pintaremos algunos puntos.
Aunque en el segmento que se muestra en el dibujo sólo hay "pintada" una cantidad finita de puntos, supondremos que, en realidad, en cada segmento vertical hemos pintado una cantidad numerable de puntos. Tenemos, entonces, el siguiente teorema:
La Hipótesis del Continuo es falsa si y sólo si, no importa cómo se decida pintar los puntos, siempre existirán números x e y (ambos entre 0 y 1) tales que los puntos (x,y) y (y,x) quedan sin pintar. En otras palabras, la Hipótesis del Continuo es equivalente a que existe una manera de pintar los puntos para la cual en toda pareja (x,y) y (y,x), al menos uno de ambos puntos queda pintado.
Vamos a demostrar este teorema.
Supongamos primero que la Hipótesis del Continuo es verdadera. Es posible, entonces, definir en el intervalo [0,1] un buen orden equivalente a $\Omega $ (para más detalles, véase "El Omegón y todo eso,.." en este mismo blog). Pintamos entonces todos los puntos (x,y) tales que y es menor o igual que x según el buen orden antes indicado. Por lo tanto, sobre cada x ha quedado pintada una cantidad numerable de puntos, y siempre sucede que, de (x,y) o (y,x), al menos uno de los dos queda pintado.
Recíprocamente, supongamos que la Hipótesis del Continuo sea falsa; y que los puntos han sido pintados de alguna manera. Como la Hipótesis del Continuo es falsa, podemos definir en [0,1] un buen orden equivalente a un ordinal mayor que $\Omega $.
Pensemos ahora en todos los puntos (x,y) pintados para los cuales x es, según el buen orden mencionado, menor que $\Omega $. Como las segundas coordenadas de estos puntos forman un conjunto de cardinal $\aleph _1$ entonces existe un $y_0$ que no pertenece a él (porque estamos suponiendo que [0,1] tiene cardinal mayor que $\aleph _1$). Es decir, para todo $x < \Omega $, $(x,y_0)$ no está pintado.
Pero el conjunto de todos los $x < \Omega $ tiene cardinal $\aleph _1$ y los puntos pintados sobre $y_0$ forman un conjunto numerable. Luego, existe un $x_0 < \Omega $ tal que $(y_0,x_0)$ no está pintado. Pero, por lo dicho más arriba, $(x_0,y_0)$ tampoco está pintado. Esto finaliza la demostración del teorema.
La Hipótesis del Continuo es falsa si y sólo si, no importa cómo se decida pintar los puntos, siempre existirán números x e y (ambos entre 0 y 1) tales que los puntos (x,y) y (y,x) quedan sin pintar. En otras palabras, la Hipótesis del Continuo es equivalente a que existe una manera de pintar los puntos para la cual en toda pareja (x,y) y (y,x), al menos uno de ambos puntos queda pintado.
Vamos a demostrar este teorema.
Supongamos primero que la Hipótesis del Continuo es verdadera. Es posible, entonces, definir en el intervalo [0,1] un buen orden equivalente a $\Omega $ (para más detalles, véase "El Omegón y todo eso,.." en este mismo blog). Pintamos entonces todos los puntos (x,y) tales que y es menor o igual que x según el buen orden antes indicado. Por lo tanto, sobre cada x ha quedado pintada una cantidad numerable de puntos, y siempre sucede que, de (x,y) o (y,x), al menos uno de los dos queda pintado.
Recíprocamente, supongamos que la Hipótesis del Continuo sea falsa; y que los puntos han sido pintados de alguna manera. Como la Hipótesis del Continuo es falsa, podemos definir en [0,1] un buen orden equivalente a un ordinal mayor que $\Omega $.
Pensemos ahora en todos los puntos (x,y) pintados para los cuales x es, según el buen orden mencionado, menor que $\Omega $. Como las segundas coordenadas de estos puntos forman un conjunto de cardinal $\aleph _1$ entonces existe un $y_0$ que no pertenece a él (porque estamos suponiendo que [0,1] tiene cardinal mayor que $\aleph _1$). Es decir, para todo $x < \Omega $, $(x,y_0)$ no está pintado.
Pero el conjunto de todos los $x < \Omega $ tiene cardinal $\aleph _1$ y los puntos pintados sobre $y_0$ forman un conjunto numerable. Luego, existe un $x_0 < \Omega $ tal que $(y_0,x_0)$ no está pintado. Pero, por lo dicho más arriba, $(x_0,y_0)$ tampoco está pintado. Esto finaliza la demostración del teorema.
14.4.15
Los axiomas de Peano: compilación y, por ahora, final.
Los axiomas de Peano
Estos axiomas se refieren a ciertos objetos a los que llamaremos números naturales y tienen como elementos primitivos al número 0, que es un número natural, a la función sucesor, que indicamos con la letra S, y a las operaciones de suma y producto. Los axiomas son:
Axioma 0: El sucesor de un número natural es siempre un número natural, la suma y el producto de dos números naturales es siempre un número natural.
Axioma 1: Para todo n, $S(n)\neq 0$.
Axioma 2: Si S(n) = S(m) entonces n = m.
Axioma 3: n + 0 = n.
Axioma 4: n + S(m) = S(n + m).
Axioma 5: n.0 = 0.
Axioma 6: n.S(m) = n.m + n.
Axioma 7 (Esquema de inducción): Para cada fórmula P(n), si puede probarse que vale P(0) y también que vale "P(n) $\Rightarrow $ P(S(n))" entonces P(n) vale para todo n.
Teoremas:
Estos son algunos teoremas que se deducen de los axiomas de Peano.
Teorema 1: 0 + n = n.
Demostración:
Aplicamos el esquema de inducción.
Para n = 0 la afirmación vale por el axioma 3.
Tenemos que probar que "0 + n = n $\Rightarrow $ 0 + S(n) = S(n)". Veamos que es así:
Si 0 + n = n entonces 0 + S(n) = S(0 + n) = S(n).
Teorema 2: n + S(m) = m + S(n).
Demostración:
Hacemos inducción en m.
Para m = 0 la afirmación vale porque:
n + S(0) = S(n + 0) = S(n) = 0 + S(n), esto último por el teorema 1.
Veamos que n + S(m) = m + S(n) implica n + S(S(m)) = S(m) + S(n).
S(m) + S(n) =
= S(m + S(n)) (ax. 4)
= S(n + S(m)) (hipótesis)
= n + S(S(m)) (ax. 4).
Teorema 3: n + m = m + n
(Es decir, la suma es conmutativa).
Demostración:
Fijamos n y hacemos inducción en m.
Para m = 0 vale ya que n + 0 = n = 0 + n, por axioma 3 y teorema 1.
Tenemos que probar que n + m = m + n implica n + S(m) = S(m) + n, veamos que es así:
n + S(m) =
= S(n + m) (ax. 4)
= S(m + n) (hipótesis)
= m + S(n) (ax. 4)
= S(m) + n (teo. 2).
Teorema 4: (n + m) + k = n + (m + k)
(Es decir, la suma es asociativa).
Demostración:
Fijamos n y m, y hacemos inducción en k.
Para k = 0 vale ya que:
(n + m) + 0 = n + m = n + (m + 0).
Tenemos que probar que (n + m) + k = n + (m + k) implica (n + m) + S(k) = n + (m + S(k)). Veamos que es así:
(n + m) + S(k) =
= S((n + m) + k) (ax. 4)
= S(n + (m + k)) (hipótesis)
= n + S(m + k) (ax. 4)
= n + (m + S(k)) (ax. 4).
Teorema 5: 0.n = 0
(Recuérdese que el axioma 5 afirma que n.0 = 0).
Demostración:
Hacemos inducción en n. Para n = 0 vale por el axioma 5. Tenemos que probar que 0.n = 0 implica 0.S(n) = 0. Veámoslo: 0.S(n) = 0.n + 0 = 0 + 0 = 0.
Teorema 6: S(n).m = n.m + m
Demostración:
Fijamos n y hacemos inducción en m. Para m = 0 vale porque: S(n).0 = 0 = 0 + 0 = n.0 + 0.
Tenemos que probar que S(n).m = n.m + m implica S(n).S(m) = n.S(m) + S(m). Veámoslo:
S(n).S(m) =
= S(n).m + S(n) (por el ax. 6)
= (n.m + m) + S(n) (hipótesis)
= n.m + (m + S(m)) (teo. 4)
= n.m + (S(m) + n) (teo. 2)
= n.m + (n + S(m)) (teo. 3)
= (n.m + n) + S(m) (teo. 4)
= n.S(m) + S(m) (ax. 6)
Teorema 7: n.m = m.n (el producto es conmutativo).
Demostración:
Fijamos n y hacemos inducción en m. Para m = 0 vale porque n.0 = 0 = 0.n.
Tenemos que probar que n.m = m.n implica n.S(m) = S(m).n. Veámoslo:
n.S(m) =
= n.m + n (ax. 6)
= m.n + n (hipótesis)
= S(m).n (teo. 6).
Teorema 8: n.(m + k) = n.m + n.k.
(Es decir, vale la propiedad distributiva).
Demostración:
Fijamos n y m, y hacemos inducción en k. Para k = 0 vale por los axiomas 3 y 5.
Tenemos que probar que n.(m + k) = n.m + n.k implica n.(m + S(k)) = n.m + n.S(k). Veámoslo:
n.m + n.S(k) =
= n.m + (n.k + n) (ax. 6)
= (n.m + n.k) + n (teo. 4)
= n.(m + k) + n (hipótesis)
= n.S(m + k) (ax. 6)
= n.(m + S(k)) (ax. 4)
Teorema 9: (n.m).k = n.(m.k).
(Es decir, el producto es asociativo).
Demostración:
Fijamos n y m, y hacemos inducción en k. Para k = 0 vale por el axioma 5.
Tenemos que probar que si (n.m).k = n.(m.k). entonces (n.m).S(k) = n.(m.S(k)).
Veámoslo:
(n.m).S(k) =
= (n.m).k + n.m (ax.6)
= n.(m.k) + n.m (hipótesis)
= n.(m.k + m) (teo. 8)
= n.(m.S(k)) (ax. 6).
Definición: 1 = S(0).
Teorema 10: $1\neq 0$.
(Es consecuencia inmediata del axioma 1.)
(Es consecuencia inmediata del axioma 1.)
Teorema 11: n + 1 = S(n).
Demostración:
n + 1 =
= n + S(0) (definición)
= S(n + 0) (Ax. 4)
= S(n) (Ax. 3)
Teorema 12: 1.n = n.
Demostración:
Por inducción. Para n = 0 vale por el axioma 5.
Veamos que 1.n = n implica 1.S(n) = S(n).
1.S(n) =
= 1.n + 1 (Ax. 6)
= n + 1 (por hipótesis)
= S(n) (Teo. 11).
Definiciones:
2 = S(1)
3 = S(2)
4 = S(3)
5 = S(4)
etc.
Definiciones:
2 = S(1)
3 = S(2)
4 = S(3)
5 = S(4)
etc.
Veamos ahora un nuevo teorema:
Teorema 13: Si $n\neq 0$ entonces existe m tal que S(m) = n.
Demostración:
El enunciado que queremos demostrar equivale a $\forall n (n=0 \vee \exists m(S(m)=n))$, y este último enunciado se prueba fácilmente por inducción. En efecto, para n = 0 vale, y supuesto que vale para n entonces es claro que también vale para S(n) ya que si n = S(m) entonces S(n) = SS(m).
Teorema 13 bis: Si $n\neq 0$ entonces n se obtiene aplicando al 0 la función S sucesivamente una cantidad finita de veces.
Demostración:
Por inducción. Para n = 0 vale (el antecedente de la implicación es falso). Supuesto que vale para n es inmediato que vale para S(n) ya que si n = SS...S(0) entonces S(n) = SSS...S(0) (una S más).
Teorema 13 ter: Si una afirmación vale para 0, S(0), SS(0), SSS(0), SSSS(0),... entonces la afirmación vale para todo n.
Demostración:
Sea n cualquiera, entonces, por el teorema anterior, o bien n = 0, o bien n = SS...S(0), en cualquiera de los dos casos, por hipótesis, la afirmación vale para n.
¿Cree usted que las tres versiones del teorema 13 son válidos?
Sucede que el enunciado y la demostración del primer teorema respetan las restricciones que impone la lógica de primer orden, mientras que los otros dos no las respetan (se enmarcan en la lógica de segundo orden). ¿Es importante esta distinción? En parte sí, porque el teorema de Gödel sólo vale en teorías basadas en la lógica de primer orden. De hecho, si se acepta la validez del teorema "13 ter" entonces el teorema de Gödel pasa a ser directamente falso (o, si se quiere, es falso si se acepta en la matemática ese tipo de razonamiento). Por así decirlo, la validez del teorema de Gödel termina en la delgada línea que separa el teorema 13 del teorema 13 bis. Vuelvo a preguntar: ¿cree usted que los tres teoremas son válidos?
Una primera conclusión es (o debería ser) que el teorema de Gödel involucra ciertas sutilezas que impiden que sea discutido a la ligera, y que refutan cualquier análisis que no tome en cuenta adecuadamente sus complejidades técnicas.
Por otra pare, yo sí creo que los tres teoremas son válidos, por lo que esta situación me convence (al menos a mí) de que la lógica que usan naturalmente los matemáticos no es (a diferencia de los que los lógicos suelen sostener) la lógica de primer orden, sino la lógica de segundo orden. La "verdadera lógica", digo yo, es la de segundo orden, la otra es una lógica muy apta para ser estudiada, pero no es la que usamos realmente para razonar.
¿Es falso entonces el teorema de Gödel? No, el teorema de Gódel sigue siendo válido en la teorías basadas en la lógica de primer orden, es decir, tiene una aplicación específica que, según yo lo veo, no alcanza a toda la matemática en su conjunto.
Teorema 14: Si n + m = 0 entonces n = 0 y m = 0.
Demostración:
Si $m\neq 0$ entonces, por el teorema 13, m = Sk para algún k, luego n + Sk = 0. Deducimos así, por el axioma 4, que S(n + k) = 0, pero esto es un absurdo porque contradice el axioma 1. Luego, debe ser m = 0; fácilmente, del axioma 3, se sigue que n = 0.
Teorema 15: Si n + m = n + k entonces m = k.
Demostración:
Lo hacemos por inducción en n. Para n = 0 es fácil ver que vale (por el axioma 3).
Paso inductivo:
Supongamos que Sn + m = Sn + k, entonces, por el axioma 3 y el teorema 3, tenemos que S(n + m) = S(n + k). Luego, por axioma 2, n + m = n + k, y por hipótesis inductiva m = k.
Otros teoremas que pueden probarse, las demostraciones que faltan se dejan como ejercicio para los lectores:
Teorema 16: Si n.m = 0 entonces n = 0 o m = 0.
Demostración:
La afirmación es equivalente a: Si n.m = 0 y $m\neq 0$ entonces n = 0. Probémoslo.
Si $m\neq 0$ entonces, por el teorema 13, existe k tal que S(k) = m. Luego:
0 = n.S(k) = n.k + n (por axioma 6).
Entonces n.k + n = 0 y, por el teorema 14, deducimos que n = 0, como queríamos probar.
Comentario: ¿No podríamos haber dicho que n.m = n + n + n + ... + n (m veces) para luego aplicar directamente el teorema 14? Una vez más, este razonamiento, perfectamente aceptable en la "matemática de todos los días", no lo es, en cambio, en el contexto de la lógica de primer orden (que es la que presupone el teorema de Gödel),
Teorema 17: Si n.m = n.k y $n\neq 0$ entonces m = k.
Demostración:
La afirmación a demostrar es:
Para todo m vale: Para todo n y k, si n.m = n.k y $n\neq 0$ entonces m = k.
Probémosla por inducción en m.
Para m = 0, hay que probar que si n.0 = n.k y $n\neq 0$ entonce k = 0; esto se deduce del teorema anterior.
Supuesto que vale para m vamos a probarlo para S(m). Tenemos entonces que n.S(m) = n.k.
Comencemos observando que $k\neq 0$, en efecto, si k = 0 entonces n.S(m) = 0, de donde se deduce que n = 0 o S(m) = 0, lo cual es absurdo. Por lo tanto, existe r tal que S(r) = k, y entonces:
n.S(m) = n.k
n.S(m) = n.S(r)
n.m + n = n.r + n
n.m = n.r (Teo. 15)
m = r (Hipótesis inductiva)
S(m) = S(r)
S(m) = k, que es lo que queríamos probar.
Teorema 18: Si n + m = 1 y $n\neq 0$ entonces m = 0.
(De este teorema se deduce inmediatamente que si la suma de dos números naturales es 1 entonces uno de de ellos es 0 y el otro es 1.)
Demostración:
Supongamos, por el absurdo, que $m\neq 0$, entonces existe k tal que S(k) = m. En consecuencia:
n + m = 1
n + S(k) = 1
S(n + k) = 1
S(n + k) = S(0)
n + k = 0
Entonces, por el teorema 14, n = 0, lo que contradice la hipótesis.
Teorema 19: Si n.m = 1 entonces n = m = 1.
Teorema 20: 1 + 1 = 2.
Demostración:
1 + 1 = 1 + S(0) = S(1 + 0) = S(1) = 2.
Teorema 21: $1\neq 2$.
Demostración:
Si 2 = 1 entonces S(S(0)) = S(0), luego (por el axioma 2), S(0) = 0, lo que contradice el axioma 1.
Teorema 22: No existe n tal que 2.n = 1.
Demostración:
Supongamos que sí. Luego:
2.n = 1
(1 + 1).n = 1 (teo. 20)
n + n = 1 (teo. 8 y 12)
Por el teorema 18, se sigue que n = 0 o n = 1,
Si n = 0, llegamos a que 0 = 1, lo que contradice el teorema 10.
Si n = 1, llegamos a que 2 = 1, lo que contradice el teorema 21.
Deducimos así que n no existe.
Teorema 23: Si n + m = 2 y $n\neq 0$ y $m\neq 0$ entonces n = m = 1.
Teorema 24: 2 es primo, es decir, si n.m = 2 y $m\neq 1$ entonces m = 2.
Teorema 25: $4\neq 2$.
(*) Teorema 26: n = SS....S(0), donde la S se repite n veces.
Como en el caso del teorema 13, bordeamos aquí las ideas del teorema de Gödel. El teorema 26 ni siquiera puede enunciarse en la lógica de primer orden de los axiomas de Peano, por lo que "escapa" a los métodos de demostración que supone el teorema de Gödel. De hecho, si intentan demostrarlo, verán que se debe hacer inducción, no sólo en n en tanto "número natural", sino también en n en tanto "cantidad de veces que aparece la letra S". ¿Pero acaso no son la misma cosa? ¿Los números naturales no son cantidades? En el contexto de los axiomas de Peano la respuesta es no, "número" no es "cantidad", sino que "número" es "símbolo que cumple los axiomas". Es por eso que, a mi modesto entender, como dije más arriba, la lógica de primer orden (tan defendida por los lógicos matemáticos) es insuficiente para abarcar la riqueza del razonamiento matemático.
Es también interesante notar que en la lógica de primer orden sí puede demostrarse que
1 = S(0)
2 = SS(0)
3 = SSS(0)
etc.
Es decir, puede probarse cada instancia del teorema 26, pero no el teorema en toda su generalidad.
Teorema 27: 3 es primo.
Teorema 28: 2.2 = 4 (luego, 4 no es primo).
Demostración:
2.2 = 2.S(1) = 2.1 + 2 = 2 + 2.
2 + 2 = 2 + S(1) = S(2 + 1) = S(S(2)) = S(3) = 4.
Teorema 29: Si $n\neq m$ entonces existe k tal que n + k = m o m + k = n.
Definición: $n\leq m$ si y sólo si existe k tal que n + k = m.
n < m si y sólo si $n\leq m$ y $n\neq m$.
Teorema 30: Para todo n y m vale que $n\leq m$ o $m\leq n$.
Teorema 31: Si $n\leq m$ y $m\leq n$ entonces n = m.
Teorema 32: Si $n\leq m$ entonces $Sn\leq Sm$.
Teorema 34: Para todo n, $0\leq n$.
Teorema 35: Para todo n, no existe k tal que n < k < Sn.
Teorema 37: Si $n\leq m$ entonces para todo k, $n + k\leq m + k$.
Teorema 38: Si $n\leq m$ entonces para todo k, $nk\leq mk$.
Fin (por ahora).
12.4.15
Adenda a "¿La mente humana?"
La frase en cuestión dice: "el teorema de Gödel implica que hay problemas que no son resolubles algorítmicamente". Ahora bien, en referencia a ella, en su mensaje privado Hernán agrega: eso aplica más para el teorema de Turing pero se entiende el punto. Quiero aprovechar este comentario de Hernán para hacer un agregado a la entrada original, un agregado que en aquel momento preferí omitir para no desviarme del tema central.
Es verdad que se le atribuye a Alan Turing (con justicia hay que decir) el descubrimiento de que existen problemas matemáticos que no son resolubles algorítmicamente; concretamente Turing probó que el Halting Problem es irresoluble. Pero no es menos cierto que la existencia de problemas matemáticos que no son resolubles algorítmicamente también se deduce (como dije en la entrada original) del teorema de incompletitud de Gödel. Veamos...
El teorema de Gödel dice que no es posible dar un sistema de axiomas para la Aritmética que sea al mismo tiempo consistente, recursivo y completo. "Consistente" significa que no existe un enunciado P tal que tanto P como su negación sean demostrables. "Recursivo" significa que existe un algoritmo que reconoce si un enunciado es, o no, un axioma. "Completo" es que para todo enunciado P, o bien él, o bien su negación, es demostrable.
Supongamos ahora que propongo como sistema de axiomas a todos los enunciados aritméticos verdaderos. No es difícil probar que este sistema es consistente y completo (ambas características se deducen del hecho de que todos los enunciados verdaderos, y sólo los verdaderos, resultan ser demostrables). Por el teorema de Gödel, entonces, el sistema no puede ser recursivo. En otras palabras, no existe un algoritmo que permita decidir si un enunciado es, o no, un axioma; es decir: no existe un algoritmo que permita decidir si un enunciado aritmético es, o no, verdadero. El problema de determinar la verdad de un enunciado aritmético no es resoluble algorítmicamente.
Ahora bien, si Gödel demostró su teorema en 1931 y el trabajo de Turing es de 1937 ¿por qué se le atribuye a Turing el descubrimiento? Porque en su artículo Gödel propone una definición posible de la idea de algoritmo "aritmético", pero reconoce que no está claro que su definición abarque todos los algoritmos posibles (de hecho, según se vio después, no los abarca). El gran mérito de Turing fue el haber dado una definición (una "modelización matemática", según la idea de la entrada anterior) de la idea de algoritmo lo suficientemente amplia como para abarcar (hasta donde se sabe) a todos los algoritmos posible. Es por eso que, recién después del trabajo de Turing pudo darse por demostrado la existencia de problemas no resolubles algorítmicamente; y fue asimismo después del trabajo de Turing (según Gödel reconoció en una posdata a su artículo) que pudo establecerse el alcance real del teorema de Gödel.
Un último comentario: así como la definición que dio Gödel para la idea de algoritmo resultó ser insuficiente, en el sentido de que hay algoritmos que la definición de Gödel no abarca, del mismo modo nada asegura que no haya algoritmos que queden "fuera" de la definición de Turing, aunque hasta el día de hoy nadie ha sido capaz de dar ni siquiera la insinuación de un ejemplo concreto.
2.4.15
¿La mente humana?
En esos comentarios sostuve la postura de que el teorema de Gödel no permite demostrar que la mente humana no es computable (a pesar de que lo contrario ha sido afirmado muchas veces por pensadores muy respetables). Algunos de mis interlocutores en aquel intercambio entendieron que yo estaba afirmando que no hay una diferencia esencial entre mente y computadora, cuando en realidad simplemente estaba afirmado que el teorema de Gödel no permite demostrar que esa diferencia existe. (En el mismo sentido, afirmar que el teorema de Gödel no permite demostrar la conjetura de Goldbach no es lo mismo que afirmar que la conjetura de Goldbach sea falsa).
Ahora bien... ¿por qué el teorema de Gödel no permite demostrar que la mente humana no es computable?
El teorema de Gódel es un teorema matemático que habla de entes matemáticos (ciertos conjuntos de enunciados) y que dice que si esos objetos cumplen ciertas hipótesis específicas entonces esos entes verifican ciertas propiedades claramente enunciadas. El punto a destacar aquí es que el teorema de Gödel es un teorema matemático que habla de ciertos objetos matemáticos. Por lo tanto, para que el teorema sea aplicable a una situación cualquiera, ésta debe haber sido, previamente, modelizada matemáticamente.
El teorema de Gódel, por ejemplo, permite demostrar que existen problemas matemáticos bien definidos que no puede ser resueltos algorítmicamente. ¿Por qué? Porque existe una definición matemática del concepto de algoritmo: matemáticamente, un "algoritmo" es una "máquina de Turing". En otras palabras, las máquinas de Turing modelizan matemáticamente el concepto de algoritmo. Si se acepta que este modelo es correcto (es decir, si se acepta que verdaderamente el concepto intuitivo de algoritmo está bien representado por la idea de máquina de Turing) entonces debe aceptarse que el teorema de Gödel implica que hay problemas que no son resolubles algorítmicamente Si hubiera algoritmos no representables por máquinas de Turing entonces esa conclusión no estaría justificada.
Creo que ahora puede verse hacia dónde voy... Para que el teorema de Gödel pueda decir algo acerca de la mente humana debería existir, previamente, una definición matemática (un modelo matemático) de la mente. Debería haber una definición que nos diga (o nos permita demostrar) qué puede hacer, o qué no puede hacer la menta humana. Todas las supuestas demostraciones de que mente humana no es computable suelen caer en la falacia de atribuirle a la mente, sin ninguna justificación, aquellas propiedades que el razonamiento necesita que verifique. (El razonamiento típico dice: un algoritmo no puede hacer H, pero la mente sí, luego mente y computadora son diferente. Pero.. ¿por qué la mente puede hacer H? Respuesta: porque sí.)
¿Cómo podría definirse matemáticamente la mente? Por ejemplo, podríamos decir que la mente es una máquina de Turing con un oráculo que resuelve el halting problem. Desde luego, si aceptáramos esta definición entonces podríamos deducir inmediatamente que existe una diferencia esencial entre mente y computadora, pero... ¿esa que hemos dado es una definición aceptable de la mente? La respuesta, creo, es "claramente no". Y mientras no haya una definición matemática, aceptable, del concepto de "mente humana" el teorema de Gödel no podrá (legítimamente, al menos) decir nada al respecto.
"Dénme un punto de apoyo y moveré el mundo", dicen que dijo Arquímedes. Parafraseando a Arquímedes, Gödel podría haber dicho; "Dénme una definición matemática de la mente y les diré si es computable o no".
25.10.14
Variaciones sobre una cáscara de banana
(Éste es el resumen de mi charla en el 5to. Encuentro para Celebrar el Ingenio de Martin Gardner y Jaime Poniachik.)
..............
Adenda del 8/11/14: Conjeturo que la suma máxima en el cuadrado de $n\times n$ es aproximadamente igual a $\frac{n^3}{2}$. Predigo en consecuencia que para 8x8 la suma máxima es aproximadamente igual a 256.
Comentario del 4/2/15: Marcos ha encontrado una suma máxima para 8x8 de 258, tal vez mi conjetura no sea tan acertada.
Adenda del 30/1/15: Al final de la entrada he agregado otra solución que me ha hecho llegar Marcos.
..............
En el movimiento cáscara de banana (1) una pieza resbala (hacia arriba, hacia abajo, hacia la derecha o hacia la izquierda) tanto como le sea posible, es decir, hasta que llega al borde del tablero o hasta que choca contra una casilla anulada. En el primer desafío elegimos una casilla inicial cualquiera, colocamos una pieza y marcamos allí un 0 (las casillas donde anotamos números se convierten en anuladas). A continuación, comenzamos a mover la pieza anotando, cada vez, en la casilla de llegada cuál ha sido la distancia recorrida. Por ejemplo:
Así seguimos hasta que la ficha ya no se puede mover. Para tableros de 3x3, 4x4, 5x5,… hay que lograr:
1) Que al trabarse el movimiento, la suma de los números sea la MENOR posible.
2) Que se complete el tablero y que a la vez la suma sea la MENOR posible.
3) Que se complete el tablero y que a la vez la suma sea la MAYOR posible.
Como segundo desafío transformamos este mecanismo en un juego para dos jugadores, digamos Alicia y Bruno. Alicia juega primero y elige una casilla inicial cualquiera (que queda anulada), luego Bruno desplaza la ficha y la casilla final queda igualmente anulada; así siguen hasta que el juego se traba. Quien haya hecho la última jugada, gana. Para tableros de 3x3, 4x4, 5x5,… la pregunta es: ¿Cuál de los dos jugadores tiene una estrategia ganadora? También podemos preguntarnos qué sucede en la versión de “el último que juega pierde”.
Nota:
(1) No sé si el mecanismo, pero sí su nombre, hasta donde conozco, se debe a Jaime Poniachik. [Según comentó Pablo Milrud en el propio encuentro, el mecanismo "cáscara de banana" -y tal vez también el nombre- serían en realidad creaciones de Iván Skvarca.]
Resumen de las soluciones recibidas hasta ahora (véanse más abajo los detalles):
Para la pregunta 1) la respuesta es 5 independientemente del tamaño del tablero, siempre que sea mayor que 2 (respuesta enviada por Rodolfo Kurchan).
Para las preguntas 2) y 3):
3x3: Mín = 12, Máx = 12. (Rodolfo Kurchan)
4x4: Mín = 23, Máx = 30. (Rodolfo Kurchan)
5x5: Mín = 41, Máx = 61. (Marcos Donnantuoni)
6x6: Mín = 68, Máx = 107. (Marcos Donnantuoni)
7x7: Mín = 99, Máx = 174. (Marcos Donnantuoni)
8x8: Mín = 142. Máx = 258. (Marcos Donnantuoni)
Para el juego de dos, Rodolfo demostró que en tableros de 3x3 y 5x5 gana el primero.
Detalles:
(26/10/14) Pocas horas después del evento, Rodolfo Kurchan envió estas soluciones:
Para la pregunta 1 me parece que para cualquier tablero de lado nxn (salvo 2x2 que es muy chico) se traba con suma 5:
.0.
11.
12.
Ésta es la "punta" de cualquier tablero, va de 0 a 2, al 1 de arriba, al 1 de la izquierda y al 1 de abajo.
1131 0313
Para el juego:
Tablero de 3x3 y 5X5 gana el primero
...
← ↑ ↓ → ↑ ← ↓ → ↑ ← ↓ → ← ↑ → ↓ ← ↓ → ↑ → ← ↑ ↓
2 3 1 1 1
1 1 2 2 4
1 0 1 2 1
4 1 1 2 1
1 1 4 1 2
5x5 max
61
↑ ← ↓ → ← → ↑ ↓ ← ↑ → ↓ ← → ↑ ← ↑ → ↓ ↑ ↓ ↑ ← ↓
4 1 1 4 3
2 2 3 1 4
4 1 1 3 1
3 1 2 3 0
4 3 4 2 4
6x6 min
68
→ ↑ ↓ ↑ ← ↑ → ↓ ↑ ← ↑ → ← ↓ → ↑ ← ↓ → ↑ ← ↓ → ← ↓ → ↓ ← ↑ ← ↑ → ↓ ← ↓
1 1 1 2 4 3
5 3 3 1 1 1
1 3 1 1 2 2
1 2 1 3 0 1
5 1 1 1 3 1
1 1 5 1 1 3
6x6 max
107
↓ ← → ↑ ← ↓ → ↑ ← → ↓ ↑ → ↓ ← → ← ↑ → ↓ ↑ ↓ ← ↓ → ↑ ↓ ↑ ↓ → ↑ ← → ← ↑
4 3 5 2 5 0
5 1 3 4 4 3
3 1 2 1 2 1
5 3 2 1 4 1
4 2 4 3 3 5
5 1 1 5 4 5
7x7 min
102
↓ → ← ↑ → ↓ ← ↑ → ↓ ↑ ↓ ← ↓ ↑ ↓ → ↓ ← → ↑ ← ↓ ↑ → ↑ ← ↓ → ← ↑ → ↓ ← ↑ ↓ ↑ → ← ↓ ← ↑ → ↑ ↓ → ← ↑
2 3 6 1 1 6 1
1 1 1 2 4 4 1
2 2 2 1 2 1 2
6 4 1 1 2 1 1
2 1 1 4 1 2 3
1 1 4 3 0 1 5
3 2 1 1 1 1 2
7x7 max
172
← ↓ ↑ → ↓ ← ↑ → ↓ ↑ ↓ ← ↑ → ↓ ↑ ← ↓ → ← ↑ → ↓ ← ↑ → ← ↓ ↑ ↓ ← → ↑ ↓ → ↑ ← ↓ → ← ↑ → ↓ ↑ ↓ ← ↑ ↓
6 6 6 1 2 4 0
5 3 4 5 3 5 6
3 4 1 2 2 2 6
6 1 3 1 2 4 2
1 5 3 1 1 3 6
5 2 1 4 3 4 3
6 5 2 6 5 6 5
7x7 min
99
1 6 1 1 2 6 1
1 4 4 1 2 4 1
1 3 1 1 1 2 6
2 1 1 3 1 1 3
4 2 2 0 2 3 1
3 1 1 1 1 1 2
1 1 2 2 2 1 4
↓↑←↓→←↑←↓→↓←↑←↓↑→↓←→↑→↓←↑→←↓→↓↑←↓→↑↓↑↓←↑↓←↓↑→↑→↑
7x7 max
174
0 4 2 6 4 6 6
4 5 5 4 2 4 5
6 4 2 2 3 1 2
1 5 1 1 2 1 6
3 4 1 3 3 3 6
6 2 3 5 2 4 4
6 6 6 1 1 5 6
→↓←→↑←↓↑→↓←↑↓→↑←↓→←↓→↑↓←→↑←↓↑→↓→↑←→←↓→↓←↑↓↑↓↑↓←↓
8x8 min
142
1 1 2 3 2 1 3 4
3 1 1 1 1 4 1 1
5 3 2 2 1 1 1 3
3 1 1 0 3 1 2 3
1 2 1 3 2 2 3 7
2 6 1 3 1 1 4 1
1 5 2 1 1 2 2 1
1 7 4 1 2 7 1 2
↑↓↑←↑→←↓←↑→↑←↓←↑↓↑→↑↓←→↑←→↓→←↑↓→↑←↑↓↑→↓→←↑←↓↑→←↓→←↑↓→↑←↓→↑←↓←↓↑
8x8 max
257
0 1 5 7 2 4 7 7
7 5 2 5 6 6 5 6
5 5 1 3 2 4 3 7
3 5 3 1 1 4 1 7
1 6 3 2 1 1 4 7
7 1 3 4 2 3 5 2
7 4 2 6 4 5 6 4
6 3 1 1 7 7 5 7
→↓↑←↓↑→↓←↑→↓←↑→←↓→↑↓↑←↑→↓↑↓←↑→↑←→↓←↑→↓↑←↓→↑←→←↑→↓←↓→↑↓↑↓↑↓↑→↓↑→
..............
Adenda del 8/11/14: Conjeturo que la suma máxima en el cuadrado de $n\times n$ es aproximadamente igual a $\frac{n^3}{2}$. Predigo en consecuencia que para 8x8 la suma máxima es aproximadamente igual a 256.
Comentario del 4/2/15: Marcos ha encontrado una suma máxima para 8x8 de 258, tal vez mi conjetura no sea tan acertada.
Adenda del 30/1/15: Al final de la entrada he agregado otra solución que me ha hecho llegar Marcos.
..............
En el movimiento cáscara de banana (1) una pieza resbala (hacia arriba, hacia abajo, hacia la derecha o hacia la izquierda) tanto como le sea posible, es decir, hasta que llega al borde del tablero o hasta que choca contra una casilla anulada. En el primer desafío elegimos una casilla inicial cualquiera, colocamos una pieza y marcamos allí un 0 (las casillas donde anotamos números se convierten en anuladas). A continuación, comenzamos a mover la pieza anotando, cada vez, en la casilla de llegada cuál ha sido la distancia recorrida. Por ejemplo:
1) Que al trabarse el movimiento, la suma de los números sea la MENOR posible.
2) Que se complete el tablero y que a la vez la suma sea la MENOR posible.
3) Que se complete el tablero y que a la vez la suma sea la MAYOR posible.
Como segundo desafío transformamos este mecanismo en un juego para dos jugadores, digamos Alicia y Bruno. Alicia juega primero y elige una casilla inicial cualquiera (que queda anulada), luego Bruno desplaza la ficha y la casilla final queda igualmente anulada; así siguen hasta que el juego se traba. Quien haya hecho la última jugada, gana. Para tableros de 3x3, 4x4, 5x5,… la pregunta es: ¿Cuál de los dos jugadores tiene una estrategia ganadora? También podemos preguntarnos qué sucede en la versión de “el último que juega pierde”.
Nota:
(1) No sé si el mecanismo, pero sí su nombre, hasta donde conozco, se debe a Jaime Poniachik. [Según comentó Pablo Milrud en el propio encuentro, el mecanismo "cáscara de banana" -y tal vez también el nombre- serían en realidad creaciones de Iván Skvarca.]
Resumen de las soluciones recibidas hasta ahora (véanse más abajo los detalles):
Para la pregunta 1) la respuesta es 5 independientemente del tamaño del tablero, siempre que sea mayor que 2 (respuesta enviada por Rodolfo Kurchan).
Para las preguntas 2) y 3):
3x3: Mín = 12, Máx = 12. (Rodolfo Kurchan)
4x4: Mín = 23, Máx = 30. (Rodolfo Kurchan)
5x5: Mín = 41, Máx = 61. (Marcos Donnantuoni)
6x6: Mín = 68, Máx = 107. (Marcos Donnantuoni)
7x7: Mín = 99, Máx = 174. (Marcos Donnantuoni)
8x8: Mín = 142. Máx = 258. (Marcos Donnantuoni)
Para el juego de dos, Rodolfo demostró que en tableros de 3x3 y 5x5 gana el primero.
Detalles:
(26/10/14) Pocas horas después del evento, Rodolfo Kurchan envió estas soluciones:
Para la pregunta 1 me parece que para cualquier tablero de lado nxn (salvo 2x2 que es muy chico) se traba con suma 5:
.0.
11.
12.
Ésta es la "punta" de cualquier tablero, va de 0 a 2, al 1 de arriba, al 1 de la izquierda y al 1 de abajo.
Para las preguntas 2 y 3:
3x3 mínimo 12, máximo 12
4x4 mínimo 23, máximo 30
1131 0313
2011 2113
1113 3221
3211 3113
Para el juego:
Tablero de 3x3 y 5X5 gana el primero
...
.12
453
76...
OX...
891..
453..
..2..
X es la jugada 10 y O es la jugada 11 (si el segundo jugador luego de A5 va para abajo pierde en 7 movidas en lugar de en 11.
(29/10/14) Marcos Donnantuoni envía estas soluciones (aclara que sin garantía de que sean óptimas):
5x5 min
41← ↑ ↓ → ↑ ← ↓ → ↑ ← ↓ → ← ↑ → ↓ ← ↓ → ↑ → ← ↑ ↓
2 3 1 1 1
1 1 2 2 4
1 0 1 2 1
4 1 1 2 1
1 1 4 1 2
5x5 max
61
↑ ← ↓ → ← → ↑ ↓ ← ↑ → ↓ ← → ↑ ← ↑ → ↓ ↑ ↓ ↑ ← ↓
4 1 1 4 3
2 2 3 1 4
4 1 1 3 1
3 1 2 3 0
4 3 4 2 4
6x6 min
68
→ ↑ ↓ ↑ ← ↑ → ↓ ↑ ← ↑ → ← ↓ → ↑ ← ↓ → ↑ ← ↓ → ← ↓ → ↓ ← ↑ ← ↑ → ↓ ← ↓
1 1 1 2 4 3
5 3 3 1 1 1
1 3 1 1 2 2
1 2 1 3 0 1
5 1 1 1 3 1
1 1 5 1 1 3
107
↓ ← → ↑ ← ↓ → ↑ ← → ↓ ↑ → ↓ ← → ← ↑ → ↓ ↑ ↓ ← ↓ → ↑ ↓ ↑ ↓ → ↑ ← → ← ↑
4 3 5 2 5 0
5 1 3 4 4 3
3 1 2 1 2 1
5 3 2 1 4 1
4 2 4 3 3 5
5 1 1 5 4 5
7x7 min
102
↓ → ← ↑ → ↓ ← ↑ → ↓ ↑ ↓ ← ↓ ↑ ↓ → ↓ ← → ↑ ← ↓ ↑ → ↑ ← ↓ → ← ↑ → ↓ ← ↑ ↓ ↑ → ← ↓ ← ↑ → ↑ ↓ → ← ↑
2 3 6 1 1 6 1
1 1 1 2 4 4 1
2 2 2 1 2 1 2
6 4 1 1 2 1 1
2 1 1 4 1 2 3
1 1 4 3 0 1 5
3 2 1 1 1 1 2
7x7 max
172
← ↓ ↑ → ↓ ← ↑ → ↓ ↑ ↓ ← ↑ → ↓ ↑ ← ↓ → ← ↑ → ↓ ← ↑ → ← ↓ ↑ ↓ ← → ↑ ↓ → ↑ ← ↓ → ← ↑ → ↓ ↑ ↓ ← ↑ ↓
6 6 6 1 2 4 0
5 3 4 5 3 5 6
3 4 1 2 2 2 6
6 1 3 1 2 4 2
1 5 3 1 1 3 6
5 2 1 4 3 4 3
6 5 2 6 5 6 5
(30/1/ 15) 8x8 max
250
→ ↑ ↓ ↑ ↓ ← ↑ → ↓ ↑ ↓ ← → ↑ ← ↓ → ← → ↑ ↓ ↑ ← ↓ → ↑ ← ↓ → ← ↓ ↑ → ↓ ← → ↑ ↓ ← ↑ → ↓ ↑ ← → ↓ → ↑ ← → ← → ↓ ← ↓ → ↑ ↓ ↑ → ← ↓ ←
5 4 4 1 7 6 6 7
4 2 1 6 5 4 6 5
7 5 3 4 2 4 1 2
1 6 2 2 1 2 4 7
3 2 3 1 1 3 5 7
7 5 2 3 3 4 1 4
6 3 1 1 6 5 5 6
0 7 3 7 2 4 7 7
99
1 6 1 1 2 6 1
1 4 4 1 2 4 1
1 3 1 1 1 2 6
2 1 1 3 1 1 3
4 2 2 0 2 3 1
3 1 1 1 1 1 2
1 1 2 2 2 1 4
↓↑←↓→←↑←↓→↓←↑←↓↑→↓←→↑→↓←↑→←↓→↓↑←↓→↑↓↑↓←↑↓←↓↑→↑→↑
7x7 max
174
0 4 2 6 4 6 6
4 5 5 4 2 4 5
6 4 2 2 3 1 2
1 5 1 1 2 1 6
3 4 1 3 3 3 6
6 2 3 5 2 4 4
6 6 6 1 1 5 6
→↓←→↑←↓↑→↓←↑↓→↑←↓→←↓→↑↓←→↑←↓↑→↓→↑←→←↓→↓←↑↓↑↓↑↓←↓
8x8 min
142
1 1 2 3 2 1 3 4
3 1 1 1 1 4 1 1
5 3 2 2 1 1 1 3
3 1 1 0 3 1 2 3
1 2 1 3 2 2 3 7
2 6 1 3 1 1 4 1
1 5 2 1 1 2 2 1
1 7 4 1 2 7 1 2
↑↓↑←↑→←↓←↑→↑←↓←↑↓↑→↑↓←→↑←→↓→←↑↓→↑←↑↓↑→↓→←↑←↓↑→←↓→←↑↓→↑←↓→↑←↓←↓↑
8x8 max
257
0 1 5 7 2 4 7 7
7 5 2 5 6 6 5 6
5 5 1 3 2 4 3 7
3 5 3 1 1 4 1 7
1 6 3 2 1 1 4 7
7 1 3 4 2 3 5 2
7 4 2 6 4 5 6 4
6 3 1 1 7 7 5 7
→↓↑←↓↑→↓←↑→↓←↑→←↓→↑↓↑←↑→↓↑↓←↑→↑←→↓←↑→↓↑←↓→↑←→←↑→↓←↓→↑↓↑↓↑↓↑→↓↑→
8x8 max
258
7 6 5 7 2 4 6 7
6 4 2 5 6 6 6 5
5 2 5 3 1 2 4 6
2 5 2 1 3 4 1 7
7 1 3 1 1 2 6 1
7 4 4 4 1 1 5 4
4 5 3 6 4 3 2 7
6 0 1 1 7 7 7 6
>^<>v^^v<^>v<>v<^>v^<^<>v<>v^v^v^>v>
16.10.14
Axiomas de Peano y consecuencias (5) con algunos comentarios sobre el teorema de Gödel
(Para ver todas las entradas de esta serie hágase clic aquí.)
A la parte 4 - A la parte 6
Nota: desde que publiqué por primera este entrada he ido modificando ligeramente su contenido buscando que converja a lo que quiero expresar.
Desde hace algún tiempo venimos mostrando algunos teoremas que se deducen de los axiomas de Peano. En las entradas previas hemos demostrado, por ejemplo, que la suma de números naturales es asociativa y conmutativa, y que el 0 es su neutro. También probamos que el producto es asociativo y conmutativo, y que el 1 (definido como S(0)) es su neutro. Veremos ahora algunos teoremas más, que tendrán esta vez, además, cierta relación con el teorema de Gödel. Para comenzar, recordemos dos de los axiomas de Peano:
Axioma 1: Para todo n, $S(n)\neq 0$.
Axioma 2: Si S(n) = S(m) entonces n = m.
Veamos ahora un nuevo teorema:
Teorema 13: Si $n\neq 0$ entonces existe m tal que S(m) = n.
Demostración:
El enunciado que queremos demostrar equivale a $\forall n (n=0 \vee \exists m(S(m)=n))$, y este último enunciado se prueba fácilmente por inducción. En efecto, para n = 0 vale, y supuesto que vale para n entonces es claro que también vale para S(n) ya que si n = S(m) entonces S(n) = SS(m).
Teorema 13 bis: Si $n\neq 0$ entonces n se obtiene aplicando al 0 la función S sucesivamente una cantidad finita de veces.
Demostración:
Por inducción. Para n = 0 vale (el antecedente de la implicación es falso). Supuesto que vale para n es inmediato que vale para S(n) ya que si n = SS...S(0) entonces S(n) = SSS...S(0) (una S más).
Teorema 13 ter: Si una afirmación vale para 0, S(0), SS(0), SSS(0), SSSS(0),... entonces la afirmación vale para todo n.
Demostración:
Sea n cualquiera, entonces, por el teorema anterior, o bien n = 0, o bien n = SS...S(0), en cualquiera de los dos casos, por hipótesis, la afirmación vale para n.
¿Cree usted que los tres teoremas son válidos?
Sucede que el enunciado y la demostración del primer teorema respetan las restricciones que impone la lógica de primer orden, mientras que los otros dos no las respetan (se enmarcan en la lógica de segundo orden). ¿Es importante esta distinción? En parte sí, porque el teorema de Gödel sólo vale en teorías basadas en la lógica de primer orden. De hecho, si se acepta la validez del teorema "13 ter" entonces el teorema de Gödel pasa a ser directamente falso (o, si se quiere, es falso si se acepta en la matemática ese tipo de razonamiento). Por así decirlo, la validez del teorema de Gödel termina en la delgada línea que separa el teorema 13 del teorema 13 bis. Vuelvo a preguntar: ¿cree usted que los tres teoremas son válidos?
Una primera conclusión es (o debería ser) que el teorema de Gödel involucra ciertas sutilezas que impiden que sea discutido a la ligera, y que refutan cualquier análisis que no tome en cuenta adecuadamente sus complejidades técnicas.
Por otra pare, yo sí creo que los tres teoremas son válidos, por lo que esta situación me convence (al menos a mí) de que la lógica que usan naturalmente los matemáticos no es (a diferencia de los que los lógicos suelen sostener) la lógica de primer orden, sino la lógica de segundo orden. La "verdadera lógica", digo yo, es la de segundo orden, la otra es una lógica muy apta para ser estudiada, pero no es la que usamos realmente para razonar.
¿Es falso entonces el teorema de Gödel? No, el teorema de Gódel sigue siendo válido en la teorías basadas en la lógica de primer orden, es decir, tiene una aplicación específica que, según yo lo veo, no alcanza a toda la matemática en su conjunto.
A la parte 4 - A la parte 6
Nota: desde que publiqué por primera este entrada he ido modificando ligeramente su contenido buscando que converja a lo que quiero expresar.
Desde hace algún tiempo venimos mostrando algunos teoremas que se deducen de los axiomas de Peano. En las entradas previas hemos demostrado, por ejemplo, que la suma de números naturales es asociativa y conmutativa, y que el 0 es su neutro. También probamos que el producto es asociativo y conmutativo, y que el 1 (definido como S(0)) es su neutro. Veremos ahora algunos teoremas más, que tendrán esta vez, además, cierta relación con el teorema de Gödel. Para comenzar, recordemos dos de los axiomas de Peano:
Axioma 1: Para todo n, $S(n)\neq 0$.
Axioma 2: Si S(n) = S(m) entonces n = m.
Veamos ahora un nuevo teorema:
Teorema 13: Si $n\neq 0$ entonces existe m tal que S(m) = n.
Demostración:
El enunciado que queremos demostrar equivale a $\forall n (n=0 \vee \exists m(S(m)=n))$, y este último enunciado se prueba fácilmente por inducción. En efecto, para n = 0 vale, y supuesto que vale para n entonces es claro que también vale para S(n) ya que si n = S(m) entonces S(n) = SS(m).
Teorema 13 bis: Si $n\neq 0$ entonces n se obtiene aplicando al 0 la función S sucesivamente una cantidad finita de veces.
Demostración:
Por inducción. Para n = 0 vale (el antecedente de la implicación es falso). Supuesto que vale para n es inmediato que vale para S(n) ya que si n = SS...S(0) entonces S(n) = SSS...S(0) (una S más).
Teorema 13 ter: Si una afirmación vale para 0, S(0), SS(0), SSS(0), SSSS(0),... entonces la afirmación vale para todo n.
Demostración:
Sea n cualquiera, entonces, por el teorema anterior, o bien n = 0, o bien n = SS...S(0), en cualquiera de los dos casos, por hipótesis, la afirmación vale para n.
¿Cree usted que los tres teoremas son válidos?
Sucede que el enunciado y la demostración del primer teorema respetan las restricciones que impone la lógica de primer orden, mientras que los otros dos no las respetan (se enmarcan en la lógica de segundo orden). ¿Es importante esta distinción? En parte sí, porque el teorema de Gödel sólo vale en teorías basadas en la lógica de primer orden. De hecho, si se acepta la validez del teorema "13 ter" entonces el teorema de Gödel pasa a ser directamente falso (o, si se quiere, es falso si se acepta en la matemática ese tipo de razonamiento). Por así decirlo, la validez del teorema de Gödel termina en la delgada línea que separa el teorema 13 del teorema 13 bis. Vuelvo a preguntar: ¿cree usted que los tres teoremas son válidos?
Una primera conclusión es (o debería ser) que el teorema de Gödel involucra ciertas sutilezas que impiden que sea discutido a la ligera, y que refutan cualquier análisis que no tome en cuenta adecuadamente sus complejidades técnicas.
Por otra pare, yo sí creo que los tres teoremas son válidos, por lo que esta situación me convence (al menos a mí) de que la lógica que usan naturalmente los matemáticos no es (a diferencia de los que los lógicos suelen sostener) la lógica de primer orden, sino la lógica de segundo orden. La "verdadera lógica", digo yo, es la de segundo orden, la otra es una lógica muy apta para ser estudiada, pero no es la que usamos realmente para razonar.
¿Es falso entonces el teorema de Gödel? No, el teorema de Gódel sigue siendo válido en la teorías basadas en la lógica de primer orden, es decir, tiene una aplicación específica que, según yo lo veo, no alcanza a toda la matemática en su conjunto.
Suscribirse a:
Entradas (Atom)