(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.
¿Verdadero o falso?
"Si un número entero es negativo entonces ese número es positivo."
"Si 3 es negativo entonces 3 es positivo."
¿Sí o no?
"Si todo triángulo tiene tres lados entonces esta afirmación (la implicación completa) es falsa."
(*) Agregado para evitar ambigüedades.
Una demostración
(Esta entrada ya había sido publicada en el blog en julio de 2013; se la vuelve publicar aquí "remozada".)
Vamos a demostrar a continuación que si p es un número primo que es divisor del producto ab entonces p es divisor de a o es divisor de b. La "originalidad" de esta demostración reside en el hecho de que se basa directamente en el principio del mínimo mientras que la demostración que habitualmente se encuentra en los libros usa el hecho de que si mcd(a,b) = 1 entonces existen s y t tales que as + bt = 1.
(Aunque casi nunca se lo mencione explícitamente, todos los números mencionados son enteros positivos.)
Teorema: Si p es un número primo positivo y $k,a,b\in \mathbb{N}$ son tales que pk = ab entonces p es divisor de a o p es divisor de b.
Demostración: Supongamos que la afirmación es falsa y sea p el menor primo para el cual existen $k,a,b\in \mathbb{N}$ con pk = ab sin que p sea divisor de a ni de b. De todos los valores posibles de k elegimos, a su vez, el menor posible.
Afirmo que $a < p$ y que $b < p$. En efecto, supongamos que $p < a$ (no pueden se iguales porque p no es divisor de a). Dividimos a por p y obtenemos a = pq + r; como p y q son positivos entonces $r < a$ y además p no es divisor de r (porque no es divisor de a).
Luego, ab = pqb + rb y en consecuencia p es divisor de rb, existe entonces un k' tal que pk' = rb. Observemos que $pk^\prime = rb < ab = pk$ y entonces $k^\prime < k$ con pk' = rb y además r y b no divisibles por p. Esto contradice la minimalidad de k. El absurdo proviene de suponer que $p < a$, deducimos entonces que $a < p$.
Tenemos entonces que pk = ab con $a < p$ y $b < p$. Nótese que $pk = ab < p^2$, luego $k < p$. Sea $p^\prime $ primo y $n\in \mathbb{N}$ tales que $p^\prime n = k$ (si k resultara ser primo, entonces tomamos $p^\prime =k$ y $n=1$). Luego, $pp^\prime n=ab$. Como $p^\prime \leq k < p$ entonces, por la minimalidad de p, $p^\prime $ es divisor de a o es divisor de b. Podemos suponer que $p^\prime $ es divisor de a, luego, existe t tal que $p^\prime t=a$. Tenemos que:
$pk = ab$
$pp^\prime n = p^\prime tb$
$pn = tb$
Como n es menor que k entonces, por la minimalidad de k, p es divisor de t (y entonces, divisor de a) o bien p es divisor de b. En ambos casos se llega a un absurdo. Esto finaliza la demostración.
Desafío para los lectores: ¿En qué punto de la demostración se usa la hipótesis de que p es primo?
Axiomas de Peano y consecuencias (4)
(Para ver todas las entradas de esta serie hágase clic aquí.)A la parte 3 - A la parte 5
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.
Productoria
1) Si $(a_1,\dots ,a_n)$ es una n-upla de números reales, la productoria $\prod (a_1,\dots ,a_n)$ se define, inductivamente, de esta manera:
Para $n=0$, definimos $\prod ()=1$.
Supuesto definido $\prod (a_1,\dots ,a_n)$, definimos $\prod (a_1,\dots ,a_n,a_{n+1}) = a_{n+1}\cdot \prod (a_1,\dots ,a_n)$.
2) Definimos $b^n=\prod (b,\dots ,b)$, donde b aparece n veces; en particular $b^0=\prod ()=1$. Y más en particular $0^0=\prod ()=1$.
Para $n=0$, definimos $\prod ()=1$.
Supuesto definido $\prod (a_1,\dots ,a_n)$, definimos $\prod (a_1,\dots ,a_n,a_{n+1}) = a_{n+1}\cdot \prod (a_1,\dots ,a_n)$.
2) Definimos $b^n=\prod (b,\dots ,b)$, donde b aparece n veces; en particular $b^0=\prod ()=1$. Y más en particular $0^0=\prod ()=1$.