En clase, para demostrar el principio del buen orden, utilizamos el principio de inducción fuerte, que dice lo siguiente.
Principio de inducción fuerte. Sea $latex K\subset\N$ tal que
Entonces $latex K=\N $.
Para demostrar el principio de inducción fuerte, necesitaremos el siguiente lema.
Lema. Para $latex n\in\N $, cualquier subconjunto no vacío de $latex \{0,1,\ldots, n\} $ tiene un mínimo.
Demostración: Demostraremos este lema por inducción en $latex n $. Si $latex n=0$, el resultado es claro porque, si $latex S\subset\{0\} $ es no vacío, entonces $latex S=\{0\} $, y $latex 0$ es su mínimo.
Suponemos ahora que el resultado es cierto para $latex n $, y sea $latex S\subset\{0,1,\ldots, n+1\} $ no vacío.
Si $latex S\cap\{0,1,\ldots, n\} =\emptyset $, entonces $latex S=\{n+1\} $, y $latex n+1$ es el mínimo de $latex S $.
Si $latex S\cap\{0,1,\ldots, n\} \not=\emptyset $, entonces es un subconjunto no vacío de $latex \{0,1,\ldots, n\} $, y por la hipótesis de inducción tiene un mínimo, el cual será el mínimo de $latex S $.
En cualquier caso, $latex S $ tiene un mínimo. Por el principio de inducción, el lema es cierto para todo $latex n\in\N $. $latex \Box $
Ahora sí estamos listos para la demostración del principio de inducción fuerte.
Demostración del principio de inducción fuerte: Sea $latex K $ un conjunto de números naturales que satisface (1) y (2). Para llegar a una contradicción, suponemos que $latex K\not=\N $.
Sea $latex n\not\in K $, y consideramos el conjunto $latex S=\{0,1,\ldots, n-1\}\setminus K$. Si $latex S=\emptyset $, entonces $latex 0,1,\ldots, n-1\in K $, así que, por (2), $latex n\in K $, una contradicción.
Ahora bien, si $latex S\not=\emptyset$, entonces $latex S$ es un subconjunto no vacío de $latex \{0,1,\ldots,n-1\}$ y, por el lema, tiene un mínimo, digamos $latex m$. $latex m\not=0$ porque $latex 0\in K$, por (1). Sin embargo, esto implica que $latex 0,1,\ldots,m-1\in K$, y, por (2), entonces $latex m\in K$, y llegamos a otra contradicción.
Por lo tanto, $latex K=\N$. $latex \Box$
Principio de inducción fuerte. Sea $latex K\subset\N$ tal que
- $latex 0\in K$
- Si $latex 0,1,\ldots, n\in K $, entonces $latex n+1\in K $.
Entonces $latex K=\N $.
Para demostrar el principio de inducción fuerte, necesitaremos el siguiente lema.
Lema. Para $latex n\in\N $, cualquier subconjunto no vacío de $latex \{0,1,\ldots, n\} $ tiene un mínimo.
Demostración: Demostraremos este lema por inducción en $latex n $. Si $latex n=0$, el resultado es claro porque, si $latex S\subset\{0\} $ es no vacío, entonces $latex S=\{0\} $, y $latex 0$ es su mínimo.
Suponemos ahora que el resultado es cierto para $latex n $, y sea $latex S\subset\{0,1,\ldots, n+1\} $ no vacío.
Si $latex S\cap\{0,1,\ldots, n\} =\emptyset $, entonces $latex S=\{n+1\} $, y $latex n+1$ es el mínimo de $latex S $.
Si $latex S\cap\{0,1,\ldots, n\} \not=\emptyset $, entonces es un subconjunto no vacío de $latex \{0,1,\ldots, n\} $, y por la hipótesis de inducción tiene un mínimo, el cual será el mínimo de $latex S $.
En cualquier caso, $latex S $ tiene un mínimo. Por el principio de inducción, el lema es cierto para todo $latex n\in\N $. $latex \Box $
Ahora sí estamos listos para la demostración del principio de inducción fuerte.
Demostración del principio de inducción fuerte: Sea $latex K $ un conjunto de números naturales que satisface (1) y (2). Para llegar a una contradicción, suponemos que $latex K\not=\N $.
Sea $latex n\not\in K $, y consideramos el conjunto $latex S=\{0,1,\ldots, n-1\}\setminus K$. Si $latex S=\emptyset $, entonces $latex 0,1,\ldots, n-1\in K $, así que, por (2), $latex n\in K $, una contradicción.
Ahora bien, si $latex S\not=\emptyset$, entonces $latex S$ es un subconjunto no vacío de $latex \{0,1,\ldots,n-1\}$ y, por el lema, tiene un mínimo, digamos $latex m$. $latex m\not=0$ porque $latex 0\in K$, por (1). Sin embargo, esto implica que $latex 0,1,\ldots,m-1\in K$, y, por (2), entonces $latex m\in K$, y llegamos a otra contradicción.
Por lo tanto, $latex K=\N$. $latex \Box$
Hola, tengo dos preguntas, puedes explicar mejor lo de "Sin embargo, esto implica que 0,1,\ldots,m-1\in K" y qué contradice "m\in K, y llegamos a otra contradicción."
ResponderBorrarS está dado como el conjunto de números entre 0 y n-1 que no están en K, y suponemos que no es vacío.
ResponderBorrarComo, por la hipótesis (1), sabemos que 0 sí está en K, entonces 0 no está en S. Así que, si m es el mínimo de S, entonces m>0. Pero esto significa que los números 0, 1, ..., m-1 no están S, así que deben estar en K.
Como K satisface (2), si 0, 1, ..., m-1 están en K, entonces también m está en K. Esto es una contradicción porque m es el mínimo de S, así que también está en S. Recuerda que los números de S son los que no están en K, por lo que m no puede estar en S y en K.