Inducción matemática

La inducción matemática puede ser ilustrada informalmente por referencia al efecto secuencial de dominó caídos.

La inducción matemática es un método para probar que un enunciado P(n) es verdadero para todo número natural n, es decir, que los infinitos casos P(0), P(1), P(2), P(3),...  todos se mantienen. Las metáforas informales ayudan a explicar esta técnica, como caer fichas de dominó o subir una escalera:

La inducción matemática demuestra que podemos subir tan alto como nos gusta en una escalera, probando que podemos subir a la escalera inferior (la base) y que de cada rang podemos subir hasta el siguiente (el paso).

—Matemáticas concretas, página 3 márgenes.

Una demostración por inducción consta de dos casos. El primero, el caso base, prueba la declaración para n = 0 sin asumir ningún conocimiento de otros casos. El segundo caso, el paso de inducción, prueba que si el enunciado se cumple para cualquier caso n = k, entonces también debe ser válido para el siguiente caso n = k + 1. Estos dos pasos establecen que el enunciado es válido para todo número natural n. El caso base no necesariamente comienza con n = 0, pero a menudo con n = 1, y posiblemente con cualquier número natural fijo n = < i>N, estableciendo la verdad del enunciado para todos los números naturales n ≥ N.

El método se puede extender para probar declaraciones sobre estructuras bien fundadas más generales, como árboles; esta generalización, conocida como inducción estructural, se utiliza en lógica matemática e informática. La inducción matemática en este sentido amplio está estrechamente relacionada con la recursividad. La inducción matemática es una regla de inferencia utilizada en pruebas formales y es la base de la mayoría de las pruebas de corrección para programas de computadora.

Aunque su nombre pueda sugerir lo contrario, la inducción matemática no debe confundirse con el razonamiento inductivo tal como se usa en filosofía (ver Problema de la inducción). El método matemático examina una cantidad infinita de casos para probar una declaración general, pero lo hace mediante una cadena finita de razonamiento deductivo que involucra la variable n, que puede tomar una cantidad infinita de valores.

Historia

En 370 a. C., el Parménides de Platón puede haber contenido rastros de un ejemplo temprano de una prueba inductiva implícita. Una técnica iterada opuesta, contando hacia abajo en lugar de hacia arriba, se encuentra en la paradoja de sorites, donde se argumentó que si 1,000,000 de granos de arena formaban un montón, y al quitar un grano de un montón, quedaba un montón, entonces un solo grano de arena (o incluso ningún grano) forma un montón.

La prueba implícita más antigua por inducción matemática se encuentra en el al-Fakhri escrito por al-Karaji alrededor del año 1000 d. C., quien lo aplicó a las sucesiones aritméticas para demostrar el teorema del binomio y las propiedades de Pascal' triángulo s.

Como dice Katz

Otra idea importante introducida por al-Karaji y continuada por al-Samaw'al y otros fue la de un argumento inductivo para tratar con ciertas secuencias aritméticas. Así, al-Karaji utilizó tal argumento para demostrar el resultado en las sumas de cubos integrales ya conocidos por Aryabhata [...] Al-Karaji no declaró, sin embargo, un resultado general para arbitrarios n. Él declaró su teorema para el entero particular 10 [...] Su prueba, sin embargo, fue claramente diseñada para ser extensible a cualquier otro entero. [...] El argumento de Al-Karaji incluye en esencia los dos componentes básicos de un argumento moderno por inducción, a saber, la verdad de la declaración para n 1 (1 = 1³) y la derivación de la verdad para n = k de la n = k - 1. Por supuesto, este segundo componente no es explícito ya que, en algún sentido, el argumento de Al-Karaji está en reversa; esto es, comienza desde n = 10 y baja a 1 en lugar de proceder hacia arriba. Sin embargo, su argumento en al-Fakhri es la prueba extante más temprana de la fórmula suma para cubos integrales.

En India, las primeras pruebas implícitas por inducción matemática aparecen en el 'método cíclico' de Bhaskara.

Ninguno de estos antiguos matemáticos, sin embargo, declaró explícitamente la hipótesis de la inducción. Otro caso similar (al contrario de lo que ha escrito Vacca, como mostró cuidadosamente Freudenthal) fue el de Francesco Maurolico en su Arithmeticorum libri duo (1575), quien utilizó la técnica para probar que la suma de los primeros < i>n enteros impares es n².

El primer uso riguroso de la inducción fue Gersonides (1288–1344). La primera formulación explícita del principio de inducción la dio Pascal en su Traité du Triangle Arithmétique (1665). Otro francés, Fermat, hizo amplio uso de un principio relacionado: prueba indirecta por descendencia infinita.

La hipótesis de la inducción también fue empleada por el suizo Jakob Bernoulli, y desde entonces se hizo muy conocida. El tratamiento formal moderno del principio llegó solo en el siglo XIX, con George Boole, Augustus De Morgan, Charles Sanders Peirce, Giuseppe Peano y Richard Dedekind.

Descripción

La forma más simple y común de inducción matemática infiere que un enunciado que involucra un número natural n (es decir, un número entero n ≥ 0 o 1) se mantiene para todos los valores de n . La demostración consta de dos pasos:

1. El Caso básico (o Caso inicial): probar que la declaración tiene para 0, o 1.
2. El paso de inducción (o paso inductivo, o Caso de paso): probar eso por cada n, si la declaración es válida n, entonces es para n+ 1. En otras palabras, asuma que la declaración contiene un número natural arbitrario n, y probar que la declaración es válida n+ 1.

La hipótesis en el paso de inducción, que la afirmación se cumple para un n en particular, se denomina hipótesis de inducción o hipótesis inductiva. Para probar el paso de inducción, se asume la hipótesis de inducción para n y luego se usa esta suposición para probar que la afirmación se cumple para n + 1.

Los autores que prefieren definir los números naturales para comenzar en 0 usan ese valor en el caso base; aquellos que definen los números naturales para comenzar en 1 usan ese valor.

Ejemplos

Suma de números naturales consecutivos

La inducción matemática se puede utilizar para demostrar la siguiente declaración P(n) para todos los números naturales n.

${displaystyle P(n)!: 0+1+2+cdots - ¿Qué?$

Esto establece una fórmula general para la suma de los números naturales menos que o igual a un número determinado; de hecho una secuencia infinita de declaraciones: ${displaystyle 0={tfrac {(0+1)}{2}}$, ${displaystyle 0+1={tfrac {(1)(1+1)}{2}}$, ${displaystyle 0+1+2={tfrac {(2)(2+1)}{2}}}$, etc.

Proposición. Por todos ${displaystyle nin mathbb {N}$, ${displaystyle 0+1+2+cdots +n={tfrac {n(n+1)}{2}}}$

Prueba. Vamos P()n) Sea la declaración ${displaystyle 0+1+2+cdots +n={tfrac {n(n+1)}{2}}}$ Damos una prueba por inducción n.

Caso base: Muestre que el enunciado se cumple para el número natural más pequeño n = 0.

P(0) es claramente cierto: ${displaystyle 0={tfrac {0(0+1)}{2},}$

Paso de inducción: Muestre que para cada k ≥ 0, si P(k) se cumple, entonces P(k + 1) también se cumple.

Supongamos la hipótesis de inducción de que para un k particular, se cumple el único caso n = k, lo que significa P(< i>k) es verdadero:

${displaystyle 0+1+cdots ¿Qué?$

Se sigue que:

${displaystyle (0+1+2+cdots +k)+(k+1)={frac {k(k+1)}{2}}+(k+1).}$

Algebraicamente, el lado derecho se simplifica como:

${displaystyle {begin{aligned}{frac {k(k+1)}{2}+(k+1) limit={frac {k(k+1)+2(k+1)}{2}\\q=frac {(k+1)}{2}}}}\c}{}{}{2}+1)}+1)}$

Igualando los extremos izquierdo y derecho, deducimos que:

${displaystyle 0+1+2+cdots +k+(k+1)={frac {(k+1)(k+1)}{2}}}$

Es decir, la declaración P(k + 1) también se cumple, estableciendo el paso de inducción.

Conclusión: Dado que tanto el caso base como el paso de inducción han sido probados como verdaderos, por inducción matemática la afirmación P(n) vale para todo número natural n. ∎

Una desigualdad trigonométrica

La inducción suele utilizarse para demostrar desigualdades. Como ejemplo, demostramos que $################################################################################################################################################################################################################################################################$ para cualquier número real ${displaystyle x}$ y número natural ${displaystyle n}$.

A primera vista, puede parecer que una versión más general, $################################################################################################################################################################################################################################################################$ para cualquier real números ${displaystyle n,x}$, podría ser probado sin inducción; pero el caso ${textstyle n={frac {1}{2}},x=pi}$ muestra que puede ser falso para valores no enteros de ${displaystyle n}$. Esto sugiere que examinemos la declaración específicamente para naturales naturales valores de ${displaystyle n}$, y la inducción es la herramienta más leída.

Proposición. Para cualquier ${displaystyle xin mathbb {R}$ y ${displaystyle nin mathbb {N}$, $################################################################################################################################################################################################################################################################$.

Prueba. Fijar un número real arbitrario ${displaystyle x}$, y dejar ${displaystyle P(n)}$ la declaración $################################################################################################################################################################################################################################################################$. Nos inducimos ${displaystyle n}$.

Caso básico: El cálculo ${fnMicrosoft Sans SerpientesfnMicrosoft Sans Serif}$ verificada ${displaystyle P(0)}$.

Paso de inducción: Mostramos la implicación ${displaystyle P(k)implies P(k+1)}$ para cualquier número natural ${displaystyle k}$. Suponga la hipótesis de inducción: para un valor dado ${displaystyle n=kgeq 0}$, el caso único ${displaystyle P(k)}$ es verdad. Usando la fórmula de adición del ángulo y la desigualdad del triángulo, deducimos:

$################################################################################################################################################################################################################################################################$

La desigualdad entre las cantidades extremas izquierda y derecha muestra que ${displaystyle P(k+1)}$ es cierto, que completa el paso de la inducción.

Conclusión: La propuesta ${displaystyle P(n)}$ para todos los números naturales ${displaystyle n}$∎

Variantes

En la práctica, las pruebas por inducción a menudo se estructuran de manera diferente, según la naturaleza exacta de la propiedad que se va a probar. Todas las variantes de inducción son casos especiales de inducción transfinita; vea abajo.

Caso base distinto de 0 o 1

Si se desea probar una afirmación, no para todos los números naturales, sino solo para todos los números n mayores que o iguales a un cierto número b, entonces la prueba por inducción consiste en lo siguiente:

1. Mostrando que la declaración se mantiene cuando n = b.
2. Mostrando que si la declaración tiene un número arbitrario n ≥ b, entonces la misma declaración también tiene para n+ 1.

Esto se puede usar, por ejemplo, para mostrar que 2ⁿ ≥ n + 5< /span> para n ≥ 3.

De esta manera, uno puede probar que alguna declaración P(n) se cumple para todos n ≥ 1, o incluso para todos los n ≥ −5. Esta forma de inducción matemática es en realidad un caso especial de la forma anterior, porque si el enunciado a demostrar es P(n)< /span> entonces probarlo con estas dos reglas es equivalente a probar P(n + b)< /span> para todos los números naturales n con un caso base de inducción 0.

Ejemplo: formación de cantidades en dólares por monedas

Suponga un suministro infinito de monedas de 4 y 5 dólares. Se puede usar la inducción para probar que cualquier cantidad total de dólares mayor o igual a 12 se puede formar mediante una combinación de tales monedas. Sea S(k) la afirmación "k dólares pueden estar formados por una combinación de monedas de 4 y 5 dólares". La prueba de que S(k) es verdadera para todos los k< /i> ≥ 12 se puede lograr por inducción en k de la siguiente manera:

Caso base: mostrando que S(k) se cumple para k = 12 es simple: toma tres monedas de 4 dólares.

Paso de inducción: dado que S(k) se cumple para algún valor de k ≥ 12 (hipótesis de inducción), demuestre que S(k + 1) también se cumple. Suponga que S(k) es cierto para algunos k ≥ 12. Si hay una solución para k dólares que incluye al menos una moneda de 4 dólares, reemplácela por una moneda de 5 dólares para ganar k + 1 dólares. De lo contrario, si solo se usan monedas de 5 dólares, k debe ser un múltiplo de 5 y, por lo tanto, al menos 15; pero luego podemos reemplazar tres monedas de 5 dólares por cuatro monedas de 4 dólares para hacer k + 1 dólares. En cada caso, S(k + 1) es verdadero.

Por lo tanto, por el principio de inducción, S(k) se cumple para todos los k ≥ 12, y la prueba está completa.

En este ejemplo, aunque S()k) también retiene ${textstyle kin {4,5,8,9,10}$, la prueba anterior no se puede modificar para reemplazar la cantidad mínima 12 dólar a cualquier valor inferior m. Para m = 11, el caso base es realmente falso; m = 10, el segundo caso en el paso de la inducción (replazando tres 5- por cuatro monedas de 4 dólares) no funcionará; mucho menos aún m.

Inducción en más de un contador

A veces es deseable probar un enunciado que involucre dos números naturales, n y m, iterando el proceso de inducción. Es decir, uno prueba un caso base y un paso de inducción para n, y en cada uno de ellos prueba un caso base y un paso de inducción para m. Véase, por ejemplo, la prueba de conmutatividad que acompaña a la suma de números naturales. También son posibles argumentos más complicados que involucran tres o más contadores.

Descenso infinito

El método del descenso infinito es una variación de la inducción matemática que fue utilizada por Pierre de Fermat. Se usa para mostrar que alguna declaración Q(n) es falsa para todos los números naturales n. Su forma tradicional consiste en mostrar que si Q(n) es cierto para algún número natural n, también lo es para algún número natural estrictamente menor m. Debido a que no hay infinitas secuencias decrecientes de números naturales, esta situación sería imposible, lo que demuestra (por contradicción) que Q(n) no puede ser cierto para cualquier n.

La validez de este método se puede verificar a partir del principio habitual de inducción matemática. Usar inducción matemática en la afirmación P(n) definida como "Q(m) es falso para todos los números naturales m menores que o iguales a n", se sigue que P(n) se cumple para todo n, lo que significa que Q(n) es falso para todo número natural n.

Inducción de prefijos

La forma más común de prueba por inducción matemática requiere demostrar en el paso de inducción que

${displaystyle forall k(P(k)to P(k+1)}$

con lo cual el principio de inducción "automatiza" n aplicaciones de este paso para pasar de P(0) a P(n). Esto podría llamarse "inducción del predecesor" porque cada paso prueba algo sobre un número a partir de algo sobre el predecesor de ese número.

Una variante de interés en la complejidad computacional es la "inducción de prefijos", en la que se prueba la siguiente afirmación en el paso de inducción:

${displaystyle forall k(P(k)to P(2k)land P(2k+1)}$

o equivalente

${displaystyle forall kleft(P!left(leftlfloor {frac {k}{2}rightrfloor right)to P(k)right)}$

Entonces, el principio de inducción "automatiza" log2 n aplicaciones de esta inferencia para pasar de P(0) a P(n). De hecho, se llama "inducción de prefijo" porque cada paso prueba algo sobre un número a partir de algo sobre el "prefijo" de ese número, como se forma al truncar el bit inferior de su representación binaria. También puede verse como una aplicación de la inducción tradicional sobre la longitud de esa representación binaria.

Si la inducción de predecesores tradicional se interpreta computacionalmente como un ciclo de n pasos, entonces la inducción de prefijos correspondería a un ciclo de log-n pasos. Por eso, las demostraciones que utilizan la inducción de prefijos son "más factiblemente constructivas" que las pruebas que utilizan la inducción predecesora.

La inducción de predecesores puede simular trivialmente la inducción de prefijos en la misma declaración. La inducción de prefijos puede simular la inducción de predecesores, pero solo a costa de hacer que la declaración sea más compleja sintácticamente (agregando un cuantificador universal acotado), por lo que los resultados interesantes que relacionan la inducción de prefijos con el cálculo de tiempo polinomial dependen de excluir por completo los cuantificadores ilimitados y limitar la alternancia de cuantificadores universales y existenciales acotados permitidos en el enunciado.

Se puede llevar la idea un paso más allá: se debe probar

${displaystyle forall kleft(P!left(leftlfloor {sqrt {k}rightrfloor right)to P(k)right}$

con lo cual el principio de inducción "automatiza" log log n aplicaciones de esta inferencia al pasar de P(0) a P(n). Esta forma de inducción se ha utilizado, de manera análoga, para estudiar el cálculo paralelo de tiempo logarítmico.

Inducción completa (fuerte)

Otra variante, llamada inducción completa, curso de inducción de valores o fuerte inducción (en contraste con la cual la forma básica de la inducción es a veces conocida como débil inducción), hace que el paso de la inducción sea más fácil de probar utilizando una hipótesis más fuerte: uno prueba la declaración ${displaystyle P(m+1)}$ en virtud de la hipótesis de que ${displaystyle P(n)}$ para Todos números naturales ${displaystyle n}$ menos que ${displaystyle m+1}$; por el contrario, la forma básica sólo asume ${displaystyle P(m)}$. El nombre "inducción fuerte" no significa que este método pueda demostrar más que "inducción débil", sino simplemente se refiere a la hipótesis más fuerte utilizada en el paso de la inducción.

De hecho, se puede demostrar que los dos métodos son en realidad equivalentes, como se explica a continuación. En esta forma de inducción completa, uno todavía tiene que probar el caso base, ${displaystyle P(0)}$, e incluso puede ser necesario probar casos extrabase tales como ${displaystyle P(1)}$ antes de aplicar el argumento general, como en el ejemplo siguiente del número de Fibonacci ${displaystyle F_{n}$.

Aunque el formulario que acaba de describir requiere uno para probar el caso base, esto es innecesario si uno puede probar ${displaystyle P(m)}$ (suponiendo ${displaystyle P(n)}$ para todos menores ${displaystyle n}$) para todos ${displaystyle mgeq 0}$. Este es un caso especial de inducción transfinita como se describe a continuación, aunque ya no es equivalente a la inducción ordinaria. En este formulario el caso base es subsumido por el caso ${displaystyle m=0}$, donde ${displaystyle P(0)}$ se prueba sin otro ${displaystyle P(n)}$ asumido; este caso puede necesitar ser manejado por separado, pero a veces el mismo argumento se aplica para ${displaystyle m=0}$ y ${displaystyle m confía0}$, haciendo la prueba más simple y más elegante. En este método, sin embargo, es vital asegurar que la prueba de ${displaystyle P(m)}$ no supone implícitamente que ${displaystyle m confía0}$Por ejemplo, diciendo "escoge un arbitrario ${displaystyle No.$", o asumiendo que un conjunto de m elementos tiene un elemento.

La inducción completa es equivalente a la inducción matemática ordinaria como se describe anteriormente, en el sentido de que una prueba por un método puede ser transformado en una prueba por el otro. Supongamos que hay una prueba de ${displaystyle P(n)}$ por inducción completa. Vamos ${displaystyle Q(n)}$ ser la declaración "${displaystyle P(m)}$ para todos ${displaystyle m}$ tales que ${displaystyle 0leq mleq n}$". Entonces... ${displaystyle Q(n)}$ para todos ${displaystyle n}$ si ${displaystyle P(n)}$ para todos ${displaystyle n}$, y nuestra prueba de ${displaystyle P(n)}$ se transforma fácilmente en una prueba de ${displaystyle Q(n)}$ por (ordinaria) inducción. Si, por otro lado, ${displaystyle P(n)}$ había sido probado por la inducción ordinaria, la prueba ya sería efectivamente una por inducción completa: ${displaystyle P(0)}$ se demuestra en el caso base, sin hipótesis, y ${displaystyle P(n+1)}$ se demuestra en el paso de inducción, en el que uno puede asumir todos los casos anteriores pero sólo necesita utilizar el caso ${displaystyle P(n)}$.

Ejemplo: números de Fibonacci

La inducción completa es más útil cuando se requieren varias instancias de la hipótesis inductiva para cada paso de inducción. Por ejemplo, se puede usar la inducción completa para demostrar que

${displaystyle ¿Qué? - ¿Qué?$

Donde ${displaystyle F_{n}$ es nnúmero Fibonacci, y ${textstyle varphi ={1+{sqrt {5}} over 2}$ (la relación de oro) y ${textstyle psi ={1-{sqrt {5}} over 2}$ son las raíces del polinomio ${displaystyle x^{2}-x-1}$. Usando el hecho de que ${displaystyle F_{n+2}=F_{n+1}+F_{n}$ para cada uno ${displaystyle nin {fnMithbb {N}}$, la identidad anterior se puede verificar mediante cálculo directo ${textstyle F_{n+2}$ si uno asume que ya tiene para ambos ${textstyle F_{n+1}$ y ${textstyle F_{n}$. Para completar la prueba, la identidad debe verificarse en los dos casos básicos: ${displaystyle n=0}$ y ${textstyle n=1}$.

Ejemplo: descomposición en factores primos

Otra prueba por inducción completa utiliza la hipótesis que la declaración sostiene para Todos más pequeño ${displaystyle n}$ más a fondo. Considere la afirmación de que "cada número natural superior a 1 es un producto de (uno o más) números primos", que es la parte "existencia" del teorema fundamental de la aritmética. Para probar el paso de la inducción, la hipótesis de inducción es que para un dado ${displaystyle n confía1}$ la declaración mantiene para todos más pequeños ${displaystyle n confía1}$. Si ${displaystyle m}$ es primo entonces es ciertamente un producto de primos, y si no, entonces por definición es un producto: ${displaystyle m=n_{1}n_{2}$, donde ninguno de los factores es igual a 1; por lo tanto no es igual a ${displaystyle m}$, y por lo tanto ambos son mayores de 1 y menor que ${displaystyle m}$. La hipótesis de inducción ahora se aplica a ${displaystyle No.$ y ${displaystyle No.$Así que cada uno es un producto de primos. Así ${displaystyle m}$ es un producto de productos de primos, y por lo tanto por extensión un producto de primos en sí mismo.

Ejemplo: montos en dólares revisados

Buscaremos probar el mismo ejemplo anterior, esta vez con inducción fuerte. La declaración sigue siendo la misma:

${displaystyle S(n):,,ngeq 12implies ,exists ,a,bin mathbb {N}.,n=4a+5b}$

Sin embargo, habrá ligeras diferencias en la estructura y los supuestos de la prueba, comenzando con el caso base extendido.

Prueba.

Caso básico: Mostrar eso ${displaystyle S(k)}$ para ${displaystyle k=12,13,14,15}$.

${displaystyle {begin{aligned}4cdot 3+5cdot 0=124cdot 2+5cdot 1=134cdot 1+5cdot 2=144cdot 0+5cdot 3=15end{aligned}}}}}$

El caso base se mantiene.

Paso de inducción: Dados algunos ${displaystyle j título15}$, asumir ${displaystyle S(m)}$ para todos ${displaystyle m}$ con ${displaystyle 12leq m won}$. Probar eso ${displaystyle S(j)}$ sostiene.

Elegir ${displaystyle m=j-4}$, y observando que ${displaystyle 15 madejimplies 12leq j-4 madej}$ muestra que ${displaystyle S(j-4)}$ sostiene, por la hipótesis inductiva. Es decir, la suma ${displaystyle j-4}$ puede ser formado por alguna combinación de ${displaystyle 4}$ y ${displaystyle 5}$ monedas de dólares. Entonces, simplemente añadir un ${displaystyle 4}$ moneda de dólar a esa combinación produce la suma ${displaystyle j}$. Eso es, ${displaystyle S(j)}$ sostiene. ∎

Inducción adelante-atrás

A veces, es más conveniente deducir hacia atrás, demostrando la declaración para ${displaystyle n-1}$, dada su validez ${displaystyle n}$. Sin embargo, probar la validez de la declaración de ningún número basta para establecer el caso básico; en cambio, hay que demostrar la declaración de un subconjunto infinito de los números naturales. Por ejemplo, Augustin Louis Cauchy utilizó primero la inducción hacia adelante (regular) para probar la desigualdad de medios aritméticos y geométricos para todos los poderes de 2, y luego utiliza la inducción atrasada para mostrarlo para todos los números naturales.

Ejemplo de error en el paso de inducción

El paso de inducción debe probarse para todos los valores de n. Para ilustrar esto, Joel E. Cohen propuso el siguiente argumento, que pretende demostrar por inducción matemática que todos los caballos son del mismo color:

Caso base: en un conjunto de solo un caballo, solo hay un color.

Paso de inducción: asume como hipótesis de inducción que dentro de cualquier conjunto de ${displaystyle n}$ caballos, sólo hay un color. Ahora mira cualquier conjunto de ${displaystyle n+1}$ caballos. Número: ${displaystyle 1,2,3,dotscn,n+1}$. Considerar los conjuntos ${textstyle left{1,2,3,dotscnright}}$ y ${textstyle left{2,3,4,dotscn+1right}}$. Cada uno es un conjunto de sólo ${displaystyle n}$ caballos, por lo tanto dentro de cada uno hay sólo un color. Pero los dos se solapan, así que sólo debe haber un color entre todos ${displaystyle n+1}$ caballos.

El caso base ${displaystyle n=1}$ es trivial, y el paso de inducción es correcto en todos los casos ${displaystyle n confía1}$. Sin embargo, el argumento utilizado en la etapa de inducción es incorrecto ${displaystyle n+1=2}$, porque la afirmación de que "los dos se solapan" es falsa ${textstyle left{1right}}$ y ${textstyle left{2right}}$.

Formalización

En lógica de segundo orden, uno puede escribir el "axioma de inducción" como sigue:

${displaystyle forall P{Bigl (}P(0)land forall k{bigl (}P(k)to P(k+1){bigr)}to forall n{bigl (}P(n){bigr)}{Bigr)}}}}}}$,

donde P(.) es una variable para predicados que involucran un número natural y k y n son variables para números naturales.

En palabras, el caso base P(0) y el paso de inducción (es decir, que la hipótesis de inducción P(k) implica P(k + 1)) juntos implican que P(n) para cualquier número natural n. El axioma de inducción afirma la validez de inferir que P(n) se cumple para cualquier número natural n del caso base y el paso de inducción.

El primer cuantificador en el axioma se extiende sobre predicados en lugar de sobre números individuales. Este es un cuantificador de segundo orden, lo que significa que este axioma se establece en lógica de segundo orden. Axiomatizar la inducción aritmética en lógica de primer orden requiere un esquema de axioma que contenga un axioma separado para cada predicado posible. El artículo Axiomas de Peano contiene una discusión más detallada de este tema.

El axioma de inducción estructural para los números naturales fue formulado por primera vez por Peano, quien lo usó para especificar los números naturales junto con los siguientes cuatro axiomas:

1. 0 es un número natural.
2. La función sucesora s de cada número natural produce un número natural ()s()x) x + 1).
3. La función sucesora es inyectable.
4. 0 no está en el rango de s.

En la teoría de conjuntos ZFC de primer orden, la cuantificación sobre predicados no está permitida, pero aún se puede expresar la inducción mediante la cuantificación sobre conjuntos:

${displaystyle forall A{Bigl (}0in Aland forall kin mathbb {N} {bigl (}kin Ato (k+1)in A{bigr)}to mathbb {N} subseteq A{Bigr)}}}}}$

A puede leerse como un conjunto que representa una proposición y que contiene números naturales, para los cuales se cumple la proposición. Esto no es un axioma, sino un teorema, dado que los números naturales se definen en el lenguaje de la teoría de conjuntos ZFC por axiomas, análogos a los de Peano.

Inducción transfinita

Se puede generalizar una variación del principio de inducción completa para enunciados sobre elementos de cualquier conjunto bien fundado, es decir, un conjunto con una relación irreflexiva < que no contiene infinitas cadenas descendentes. Todo conjunto que representa un número ordinal está bien fundado, el conjunto de los números naturales es uno de ellos.

Aplicada a un conjunto bien fundado, la inducción transfinita se puede formular como un solo paso. Para probar que un enunciado P(n) se cumple para cada número ordinal:

1. Mostrar, por cada número ordinal n, eso si P()m) sostiene para todos m. n, entonces P()n) también sostiene.

Esta forma de inducción, cuando se aplica a un conjunto de números ordinales (que forman una clase bien ordenada y, por lo tanto, bien fundamentada), se denomina inducción transfinita. Es una técnica de prueba importante en teoría de conjuntos, topología y otros campos.

Las demostraciones por inducción transfinita suelen distinguir tres casos:

1. cuando n es un elemento mínimo, es decir, no hay elemento más pequeño que n;
2. cuando n tiene un antecesor directo, es decir, el conjunto de elementos que son más pequeños que n tiene un elemento más grande;
3. cuando n no tiene predecesor directo, es decir. n es un llamado ordinal límite.

Estrictamente hablando, no es necesario en la inducción transfinita probar un caso base, porque es un caso especial vacío de la proposición de que si P es verdadero para todo n < m, entonces P es verdadero de m. Es vagamente cierto precisamente porque no hay valores de n < m que podrían servir como contraejemplos. Entonces los casos especiales son casos especiales del caso general.

Relación con el principio del buen orden

El principio de la inducción matemática suele establecerse como un axioma de los números naturales; ver axiomas de Peano. Es estrictamente más fuerte que el principio de buen orden en el contexto de los otros axiomas de Peano. Supongamos lo siguiente:

• El axioma tricotomía: Para cualquier número natural n y m, n es menor o igual a m si m no es menos que n.
• Para cualquier número natural n, n+ 1 es mayor que n.
• Para cualquier número natural n, ningún número natural es entre n y n+ 1.
• Ningún número natural es inferior a cero.

Entonces se puede demostrar que la inducción, dados los axiomas mencionados anteriormente, implica el principio de buena ordenación. La siguiente prueba usa inducción completa y el primer y cuarto axioma.

Demostración. Supongamos que existe un conjunto no vacío, S, de números naturales que no tiene elemento mínimo. Sea P(n) la afirmación de que n no está en S. Entonces P(0) es verdadero, porque si fuera falso entonces 0 es el elemento menor de S. Además, sea n un número natural y suponga que P(m) es cierto para todos los números naturales m menor que n + 1. Entonces, si P(n + 1) es falso n + 1 está en S, por lo que es un elemento mínimo en S, una contradicción. Por lo tanto, P(n + 1) es verdadero. Por lo tanto, por el principio de inducción completa, P(n) se cumple para todos los números naturales n; entonces S está vacío, una contradicción. ∎

"Número de línea" para el conjunto [0, n): n ▪ ${displaystyle mathbb {N}$} ∪ {1} n): n ▪ ${displaystyle mathbb {N}$}. Los números se refieren al segundo componente de pares; el primero se puede obtener de color o ubicación.

Por otro lado, el conjunto ${displaystyle {(0,n):nin mathbb {N}cup {(1,n):nin mathbb {N}}$, se muestra en la imagen, está bien ordenado por el orden lexicográfico. Además, excepto por el axioma de inducción, satisface todos los axiomas de Peano, donde la constante 0 de Peano se interpreta como el par (0, 0), y el Peano sucesor función se define en pares por succ(x, n) =x, n+ 1) para todos ${displaystyle xin {0,1}$ y ${displaystyle nin mathbb {N}$. Como ejemplo para la violación del axioma de inducción, definir el predicado P()x, n) como ()x, n) = (0, 0) o ()x, n) = succ(Sí., m) para algunos ${displaystyle yin {0,1}$ y ${displaystyle min mathbb {N}$. Entonces el caso base P(0, 0) es trivialmente cierto, y así es el paso de la inducción: si P()x, n), entonces P(succ(x, n). Sin embargo, P no es cierto para todos los pares en el set.

Los axiomas de Peano con el principio de inducción modelan de forma única los números naturales. Reemplazar el principio de inducción con el principio de buen orden permite modelos más exóticos que cumplen con todos los axiomas.

Está impreso erróneamente en varios libros y fuentes que el principio del buen orden es equivalente al axioma de inducción. En el contexto de los otros axiomas de Peano, este no es el caso, pero en el contexto de otros axiomas, son equivalentes; específicamente, el principio de buen orden implica el axioma de inducción en el contexto de los dos primeros axiomas enumerados anteriormente y

• Cada número natural es 0 o n+ 1 para algún número natural n.

Un error común en muchas pruebas erróneas es asumir que n − 1 es un número natural único y bien definido, una propiedad que es no implicado por los otros axiomas de Peano.