Capítulo 10 — Inducción, Recurrencia y Sumas
10.1 — El Principio de Inducción
Los puntos suspensivos de contienen un teorema; esta sección lo extrae.
En el §1.1 los números naturales se presentaron por extensión, como , y la presentación descansaba en que el lector supiera continuar la lista. Para contar alcanza. Para demostrar no alcanza, porque los puntos suspensivos no dicen qué objetos pertenecen a y cuáles no, y cada vez que el libro probó algo “para todo ” pasando de a usó una propiedad de que nunca enunció. Esta sección define dentro de , con los axiomas del §1.1 como único punto de partida, y demuestra a partir de esa definición el principio de inducción y sus variantes.
§1. El menor conjunto inductivo
Sección titulada «§1. El menor conjunto inductivo»Definición. Un subconjunto es inductivo si y, para todo , también .
El propio es inductivo, y también lo son , y el conjunto . Un conjunto inductivo contiene al , al , al y, en general, a todo lo que la lista del §1.1 pretendía enumerar, pero puede contener mucho más. Lo que se busca es el conjunto que contenga eso y nada más, y la manera de obtenerlo sin usar puntos suspensivos es tomar lo que todos los conjuntos inductivos tienen en común.
Definición. El conjunto de los números naturales es la intersección de todos los subconjuntos inductivos de :
Proposición. es inductivo, y está contenido en todo subconjunto inductivo de .
Demostración. El número pertenece a todo conjunto inductivo, así que . Si , entonces pertenece a todo conjunto inductivo , y como cada uno de ellos es inductivo, también ; por lo tanto . La segunda afirmación es inmediata: si es inductivo, es uno de los conjuntos que se intersecan, y la intersección está contenida en cada uno de ellos.
es, así, el menor conjunto inductivo, en el sentido de la inclusión. De esa minimalidad sale todo lo demás, empezando por el teorema que da nombre a la sección.
Teorema (principio de inducción). Sea tal que y, para todo , también . Entonces .
Demostración. Las hipótesis dicen que es inductivo. Por la proposición, , y como , ambos conjuntos coinciden.
En la práctica el teorema se usa en la forma de propiedades. Sea una afirmación que tiene sentido para cada natural . Si se prueba que es verdadera, el caso base, y que para todo la verdad de implica la de , el paso inductivo, entonces es verdadera para todo . Basta aplicar el teorema al conjunto . En el paso inductivo, la suposición de que vale se llama hipótesis inductiva. No es una petición de principio: no se supone lo que se quiere probar, que es para todo , sino que se prueba una implicación para cada .
§2. Lo que la definición reconstruye
Sección titulada «§2. Lo que la definición reconstruye»La definición debe recuperar las propiedades que el §1.1 atribuía a la lista. Se prueban aquí las que el resto del capítulo necesita, y cada prueba es un primer ejercicio del principio.
Proposición. Para todo se cumple .
Demostración. El intervalo es inductivo, así que contiene a .
Proposición. Si , entonces y .
Demostración. Se fija y se prueba por inducción en que . Para , porque es inductivo. Si , entonces por la misma razón. Para el producto, con fijo, , y si , entonces por lo ya probado para la suma.
Proposición. Si y , entonces .
Demostración. Sea . Contiene al . Si , entonces y , así que . Por el principio de inducción, , que es lo que se afirmaba.
Proposición. Para todo , no existe ningún natural con .
Demostración. Primero el caso . El conjunto es inductivo, porque si entonces , y si entonces . Contiene, por lo tanto, a , y no tiene puntos en . Supóngase ahora que la afirmación vale para , y que existiera con . Como , se tiene , y por la proposición anterior , con , contra la hipótesis inductiva.
Esta última proposición es la que da sentido preciso a la frase ” es el siguiente de ”. Entre dos naturales consecutivos no hay otro natural. Se sigue, en particular, que si y son naturales con , entonces o . El conjunto de los enteros se obtiene como , y se escribe .
Queda una propiedad que el libro usó desde el capítulo 1: que los naturales no están acotados.
Proposición (propiedad arquimediana). Para todo número real existe con .
Demostración. Si no fuera así, sería un conjunto no vacío acotado superiormente por , y por el axioma del supremo del §1.1 tendría supremo . Como , el número no es cota superior, y existe con . Pero entonces y , contra la definición de supremo.
La demostración necesita las dos mitades de la estructura de : el axioma del supremo y el carácter inductivo de . Sin la segunda, el argumento no puede pasar de a .
§3. Variantes del principio
Sección titulada «§3. Variantes del principio»Muchas afirmaciones valen solo a partir de cierto número, y muchos pasos inductivos necesitan más que el caso inmediatamente anterior. Ambas situaciones se reducen al principio básico.
Proposición (inducción desde ). Sea y sea una afirmación para cada entero . Si es verdadera y, para todo , implica , entonces es verdadera para todo entero .
Demostración. Se aplica el principio de inducción a la afirmación : ” es verdadera”, para . es , y es el paso con . Todo entero es de la forma con .
Teorema (inducción fuerte). Sea una afirmación para cada . Si, para todo , la verdad de para todos los naturales implica la verdad de , entonces es verdadera para todo .
Demostración. Sea la afirmación ” es verdadera para todo natural ”. Para , no hay naturales menores que (§2), de modo que la hipótesis, aplicada a , da sin suponer nada; como el único natural es el , vale . Supóngase . Entonces vale para todo , porque por el §2 esos son exactamente los , y la hipótesis da . Por lo tanto vale para todo , que es . Por el principio de inducción vale para todo , y en particular .
En la inducción fuerte no hay un caso base separado, pero el caso debe tratarse de todos modos, porque para él la hipótesis no ofrece nada que usar.
Teorema (principio del buen orden). Todo subconjunto no vacío de tiene un elemento mínimo.
Demostración. Sea sin elemento mínimo; se prueba que es vacío. Sea la afirmación "". Si vale para todos los naturales , entonces ningún natural menor que está en . Si estuviera en , sería su mínimo, que no existe. Por lo tanto , es decir, vale . Por inducción fuerte, ningún natural está en .
El buen orden es, a su vez, suficiente para recuperar el principio de inducción. Si cumple las hipótesis del teorema del §1 y no fuera todo , el conjunto sería no vacío y tendría un mínimo . Sería , porque , y entonces , con por ser menor que el mínimo. Así, , y por hipótesis , una contradicción. Las dos formulaciones son, en este sentido, equivalentes. La del buen orden es la que usan las demostraciones por descenso, en las que se supone un contraejemplo y se construye otro menor, lo que es imposible si se partió del mínimo.
§4. Dos aplicaciones
Sección titulada «§4. Dos aplicaciones»La primera aplicación salda una deuda del capítulo 4, cuya prueba de unicidad de la exponencial se apoyó en una desigualdad de Bernoulli. La potencia de exponente natural se usa aquí con su definición del §1.2, “el producto de factores iguales a ”, que es, en rigor, una definición por recurrencia: y . El §10.2 prueba que esa definición es legítima.
Proposición (desigualdad de Bernoulli). Si , entonces para todo .
Demostración. Para la desigualdad es una igualdad. Supóngase que vale para . Como , el factor es no negativo, y multiplicar la hipótesis inductiva por él conserva la desigualdad (§1.7):
donde el último paso usa que .
La hipótesis se usó en un solo lugar, para multiplicar la desigualdad sin invertirla, y no puede suprimirse. Con , para los miembros valen y , y para ambos valen , de modo que la desigualdad todavía se cumple. Pero para el primer miembro vale y el segundo , y la desigualdad falla.
Los otros argumentos de los capítulos 4 y 5 que pasaban de un término al siguiente tenían la misma estructura. Así ocurre con las afirmaciones del tipo ” para todo ” sobre las sucesiones que construyeron , y con las cotas de los polígonos de lados que construyeron . Todos son aplicaciones del principio que esta sección acaba de demostrar, y quedan justificados sin cambiar una línea.
La segunda aplicación es un principio de conteo que el §10.4 va a necesitar. Para , sea , el conjunto de los primeros naturales.
Proposición (principio del palomar). Para todo , no existe ninguna función inyectiva de en .
Demostración. Para , toda función de en asigna a ambos elementos el valor y no es inyectiva. Supóngase que no existe función inyectiva de en , y que existiera una función inyectiva . Si el valor no es imagen de ningún elemento, la restricción de a es una función inyectiva de en , contra la hipótesis inductiva. Si para cierto , sea la función que coincide con salvo que intercambia los valores en y en . Es decir, , y para los demás . La función sigue siendo inyectiva y solo toma el valor en , porque lo tomaba solo en . Su restricción a es, entonces, una función inyectiva de en , otra vez contra la hipótesis.
El nombre viene de su lectura cotidiana: si palomas se acomodan en nidos, algún nido recibe al menos dos. Parece demasiado obvio para necesitar una prueba, y sin embargo la prueba no es trivial, porque “obvio” significaba aquí “evidente para los primeros casos que uno imagina”. El principio de inducción es exactamente lo que convierte esa evidencia local en un enunciado para todo .
El principio de inducción permite demostrar afirmaciones sobre todos los naturales. La sección siguiente prueba su contraparte constructiva: que una regla que dice cómo obtener cada término a partir del anterior define, efectivamente, una única sucesión.
Copyright © 2026 Carlos Dagorret — Licencia Creative Commons Atribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)