La equivalencia del principio del buen Orden y el principio de Inducción Matemática.

En esta ocasión se pretende mostrar una técnica de demostración equivalente al principio de inducción, si bien no parece del todo evidente como utilizarla, a primera vista, se presentará un ejemplo para reforzar la idea del teorema.

PIM y PBO – PDF

— 1. El principio de Inducción (PI) —

En el siglo XIX Giuseppe Peano, matemático, lógico y filósofo italiano, ideó un conjunto de axiomas con los cuales se presenta formalmente al conjunto de los números naturales, {\mathbb{N}}, de ese conjunto de axiomas, a partir de el axioma 5 se define lo que conocemos como el principio de inducción matemática.

Para todo subconjunto {\mathbf{K}} de {\mathbb{N}} que cumpla con las propiedades siguientes

  • i) 1 {\in \mathbf{K}}
  • ii) Si {1,2,\ldots , k} implica que {\sigma(k)=k+1 \in \mathbf{K}}

entonces se tiene que {\mathbf{K}=\mathbb{N}}.

— 2. El principio del buen orden —

Una vez definidos los números naturales, con sus correspondientes operaciones suma,{(+)}, y producto, {(\cdot)}, se define una relación de orden \textquotedblleft {<} \textquotedblright en {\mathbb{N}} dada por

\displaystyle m<n \Leftrightarrow \exists p \in \mathbb{N} \mid m+p=n

Desde luego, la notación {m \leq n} significa que {m<n} ó {m=n}. Con este orden {\mathbb{N}} es un conjunto totalmente ordenado, es decir, cualesquiera dos elementos del mismo son comparables, así se tiene el

Lema (Principio del buen orden (PBO)) Todo subconjunto {\mathbf{S}} de {\mathbb{N}}, no vacío, posee un elemento mínimo, con respecto al orden definido.

— 3. Equivalencia entre el principio de inducción y el principio del buen orden —

Teorema El principio de inducción matemática y el principio del buen orden son equivalentes.

Demostración: Tomemos el principio de inducción matemática como válido, entonces, sea un subconjunto {S \subset \mathbb{N}} no vacío definido por la siguiente propiedad: {S} no posee elemento mínimo. Sea ahora un conjunto {M} dado por

\displaystyle M:=\{ n\in \mathbb{N} \mid n<s \; \forall s \in S \}

De la construcción de {S} y {M} es claro que {S \cap M = \emptyset}, pues de existir un elemento, digamos {m \in S \cap M = \emptyset} se tendría entonces que {m<m} lo que no es posible, dada la definición de orden usual. Así tenemos que {M\subseteq \mathbb{N}-S}. De lo anterior tenemos que:

  • i) {1 \notin S} pues, por lo axiomas de Peano, {1\leq n\, \forall n \in \mathbb{N}}.
  • ii) Si {n\in M} entonces {n+1 \in M} pues de no ser así, entonces {n+1>s} para algún {s\in S}, por otro lado, como {S} no tiene elemento mínimo, existe {s' \in S} tal que {s' < s} entonces {s'<n+1} pero entonces {s'-1<n} más aún {s' \leq n}, como {n\in M} se tiene, por construcción de {S}, que {n<s'} así {s'=n} lo que es una contradicción pues {s' \in S} y {s' \in \mathbb{N}-S=S^{c}}.

Así vemos que suponer que existe al menos un subconjunto en los naturales que no tiene elemento mínimo nos lleva a una contradicción. Supongamos ahora que el principio del buen orden es válido y veamos que de ello se obtiene el principio de inducción, para tal fin sea {M \subseteq \mathbb{N}} de tal modo que

  • i) {1\in M}
  • ii){1,2,\ldots,n-1,n \in M \Rightarrow n+1 \in M}

Ahora, analicemos {M^{c}}: Si {M^{c}\neq \emptyset} entonces, por el principio del buen orden existe un {m\in M^{c}} tal que {m\leq s\; \forall s \in M^{c}}. Entonces tenemos que {m-1 \in M} pero, por la construcción de {M} entonces {m \in M} Así tendríamos que {m \in M} y {m \in M^{c}}, lo que es una contradicción. \Box

Como bien puede observar el lector, la demostración del teorema nos da la idea de como llevar a cabo una demostración basada en el principio del buen orden en lugar de utilizar el tan acostumbrado principio de inducción.

  1. Defina un conjunto, digamos {S}, en el cuál estarán los contraejemplos de la proposición a demostrar
  2. Para llevar a cabo la demostración asumamos que {S} es no vacío
  3. Por el principio del buen orden {S} debe tener un elemento mínimo
  4. Ahora debemos obtener una contradicción (Aquí entra el conocimiento y herramientas de las que disponga el lector)
  5. Por último debemos concluir entonces que {S} es vacío, dicho de otra manera, que no existe un contraejemplo para la proposición, por lo que se cumple para todo {n \in \mathbb{N}}.

A continuación se expone un ejemplo, para ilustrar el método.

Ejemplo 1 A partir del principio del buen orden muestre que

\displaystyle \sum\limits_{i=1}^{n}{i}= \frac{n(n+1)}{2}

Sea {S=\{ k \in \mathbb{N} \mid \sum\limits_{i=1}^{n}{i}\neq \frac{n(n+1)}{2} \}} si {S \neq \emptyset} por el principio del buen orden tendría un elemento mínimo, digamos {s=\min (S)}. Así {s-1 \notin S} por lo que {s-1 \in S^{c}} es decir

\displaystyle \sum\limits_{i=1}^{s-1}{i}= \frac{s(s-1)}{2}

Así tenemos que

\displaystyle \sum\limits_{i=1}^{s-1}{i} + s = \frac{s(s-1)}{2} + s = \frac{s(s+1)}{2}

Por lo tanto {s \notin S} y por lo tanto {S} no tiene un elemento mínimo, lo que contradice el PBO, así {S=\emptyset} y la proposición se cumple para todo {n \in \mathbb{N}}.

Consideremos por último un ejemplo más.

Ejemplo 2 A partir del principio del buen orden pruebe que

\displaystyle 1+n=n+1 \; \forall n \in \mathbb{N}

Sea {S=\{ k \in \mathbb{N} \mid k+1 \neq 1+k \}} entonces, si {S \neq \emptyset}, por el PBO se tiene un elemento {s\in S} tal que {s \leq m}, {\forall m \in S}. Como {s+1 \neq 1+s} entonces, debe pasar que {s+1<1+s} ó {1+s<s+1}; sin pérdida de generalidad supongamos {s+1<1+s}:

\displaystyle s+1<1+s\Rightarrow \exists p \in \mathbb{N} \mid s+1+p=1+s

Se afirma que {p<s} pues si {p>s\Rightarrow (s+1)+p>(s+1)+s\geq 1+s} (note el lector que {1 \notin S}). Así pues {p \notin S} y por lo tanto

\displaystyle s+p+1 = 1+s \Rightarrow s-1+s+p+1=2s \Rightarrow 2s+p=2s

Lo que es una contradicción pues {p \geq 1}, así pues {S=\emptyset} y por lo tanto

\displaystyle 1+n=n+1\;\forall n\in \mathbb{N}

Remark 1 En la prueba no se supone la conmutatividad en {\mathbb{N}} lo que hace un poco más elaborada la prueba. Más aún, si el lector ha trabajado con las propiedades de {\mathbb{N}}, recordará que se tiene que probar esta propiedad de los naturales para poder probar la conmutatividad en general.

Referencias

[1] Pineda Ruelas M., Villa Salvador G. D., Divisibilidad, UAM – I.

http://licmat.izt.uam.mx/notas de clase/Divisibilidad.pdf

[2] Wikipedia – Giuseppe Peano

http://en.wikipedia.org/wiki/Giuseppe_Peano

¡Saludos!

About these ads

Hey, hey ;) ¿Quieres comentar algo al respecto? Puedes utilizar código LaTeX: Sólo tienes que escribir $latex código-latex-que-quieras-insertar$.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s