Inducción y principio del buen orden.

Iniciemos este post, citando los axiomas de los números naturales, que se conocen normalmente como los Axiomas de Peano, aunque el 5to para este caso será el principio del buen orden, que finalmente es equivalente al principio de inducción.

Giuseppe Peano (1858 - 1932)

También hay una anotación extra que es importante hacer, dependiendo de la construcción o formación matemática el 0 puede o no pertenecer a los naturales, en la siguiente lista tomaremos ambos casos en los casos a) el cero es natural, en los casos b) no lo es.

Axiomas de los números naturales

1.- 

2.-

3.-   

a) el 0 no es sucesor de ningún número natural.

b) el 1 no es sucesor de ningún número natural.

4.-

a) y b) si n,m tienen el mismo sucesor entonces n=m

5.- Principio del buen orden (PBO)

Centremos nuestra atención en el último axioma, debe de ser claro que lo que dice es que todo conjunto no vacío de naturales siempre tiene un número más pequeño, un pilar por decirlo así, lo más interesante es que esto es equivalente al principio de inducción matemática (PIM), que dice:

Sea P(n) una cierta propiedad para cada natural n

Si 

i)  P (1) es cierta y

ii) Suponiendo que P(k) es cierta se puede demostrar que P(k+1) lo es 

entonces P es cierta para todos los Naturales

o, dicho de otra manera

Demostremos que ambos principios son equivalentes.

PBO implica PIM

Demostración. - 

Suponemos el PBO

Y dada una propiedad P(n) tal que 

Entonces por PBO este conjunto tiene un elemento mínimo llamémoslo s*

 

.

Demostremos ahora la otra implicación

PIM implica PBO

Demostración. - 

Tenemos como hipótesis el PIM y supongamos que:

QED

Para terminar el tema digamos que el principio de inducción lo podemos interpretar como si la propiedad que queremos demostrar en los naturales fueran un conjunto de piezas de domino acomodadas para caer, tenemos que tener una pieza inicial (el 1) y dada la n-esima pieza la n+1-esima pieza tiene que acomodarse bien para que pueda darse la secuencia de caída.

Si todo está bien acomodado la propiedad será verdad para todas las piezas (los naturales).

Ejemplos

Dada la siguiente proposición

Demostrémosla usando el PIM