Inducción matemática

La inducción matemática es un método para demostrar que una afirmación es verdadera para todo número natural , es decir, que todos los infinitos casos se cumplen. Esto se hace demostrando primero un caso simple y luego mostrando también que si asumimos que la afirmación es verdadera para un caso dado, entonces el siguiente caso también lo será. Las metáforas informales ayudan a explicar esta técnica, como caer una ficha de dominó o subir una escalera: $P(n)$ $n$ $P(0),P(1),P(2),P(3),\puntos$

La inducción matemática demuestra que podemos subir tan alto como queramos en una escalera, demostrando que podemos subir al peldaño inferior (la base ) y que desde cada peldaño podemos subir al siguiente (el escalón ).
— Matemáticas Concretas , página 3 márgenes.

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

El método puede ampliarse para probar afirmaciones sobre estructuras más generales bien fundamentadas , 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 extendido 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. ^[3]

A pesar de su nombre, la inducción matemática se diferencia fundamentalmente del razonamiento inductivo tal como se utiliza en filosofía , en el que el examen de muchos casos da como resultado una conclusión probable. El método matemático examina infinitos casos para probar una afirmación general, pero lo hace mediante una cadena finita de razonamiento deductivo que involucra a la variable , que puede tomar infinitos valores. El resultado es una prueba rigurosa de la afirmación, no una afirmación de su probabilidad. ^[4] $n$

Historia

En 370 a. C., el Parménides de Platón puede haber contenido rastros de un ejemplo temprano de prueba inductiva implícita; ^[5] sin embargo, la prueba implícita más antigua por inducción matemática fue escrita por al-Karaji alrededor del año 1000 d. C., quien la aplicó a secuencias aritméticas. demostrar el teorema del binomio y las propiedades del triángulo de Pascal . Si bien la obra original se perdió, Al-Samawal al-Maghribi hizo referencia a ella más tarde en su tratado al-Bahir fi'l-jabr (El brillante en álgebra) alrededor del año 1150 d.C. ^[6]^[7]

Katz dice en su historia de las matemáticas

Otra idea importante introducida por al-Karaji y continuada por al-Samaw'al y otros fue la de un argumento inductivo para abordar ciertas secuencias aritméticas. Así, al-Karaji utilizó tal argumento para probar el resultado de las sumas de cubos integrales ya conocidos por Aryabhata [...] Al-Karaji, sin embargo, no declaró un resultado general para n arbitrario . Expuso su teorema para el número entero particular 10 [...] Su demostración, sin embargo, estaba claramente diseñada para ser extensible a cualquier otro número 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 del enunciado para n = 1 (1 = 1 ³ ) y la derivación de la verdad para n = k a partir de el de n = k - 1. Por supuesto, este segundo componente no es explícito ya que, en cierto sentido, el argumento de al-Karaji es al revés; es decir, comienza desde n = 10 y baja hasta 1 en lugar de avanzar hacia arriba. Sin embargo, su argumento en al-Fakhri es la prueba más antigua que existe de la fórmula de la suma para cubos integrales . ^[8]

En la India, las primeras pruebas implícitas por inducción matemática aparecen en el " método cíclico " de Bhaskara . ^[9]

Sin embargo, ninguno de estos antiguos matemáticos afirmó explícitamente la hipótesis de la inducción. Otro caso similar (al contrario de lo que ha escrito Vacca, como bien demostró Freudenthal) ^[10] fue el de Francesco Maurolico en su Arithmeticorum libri duo (1575), quien utilizó la técnica para demostrar que la suma de los primeros $n$ enteros impares es $n$ $2$ .

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

La hipótesis de la inducción también fue utilizada por el suizo Jakob Bernoulli y desde entonces se hizo muy conocida. El tratamiento formal moderno del principio no llegó hasta el siglo XIX, con George Boole , ^[13] Augustus De Morgan , Charles Sanders Peirce , ^[14]^[15] Giuseppe Peano y Richard Dedekind . ^[9]

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 \geq 0$ o 1) es válido para todos los valores de $n$ . La prueba consta de dos pasos:

ElCaso base (ocaso inicial): demuestre que la afirmación es válida para 0 o 1.
Elpaso de inducción (opaso inductivo, ocaso de paso): demuestre que para cada $n$ , si el enunciado es válido para $n$ , entonces es válido para $n + 1$ . En otras palabras, suponga que el enunciado es válido para algún número natural arbitrario $n$ y demuestre que el enunciado es válido para $n + 1$ .

La hipótesis en el paso de inducción, de que el enunciado es válido para un $n$ particular , se llama 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 demostrar que la afirmación es válida para $n + 1$ .

Los autores que prefieren definir los números naturales para que comiencen en 0 utilizan 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 probar la siguiente afirmación $P (n)$ para todos los números naturales $n$ .

P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.

Este establece una fórmula general para la suma de los números naturales menores o iguales a un número dado; de hecho, una secuencia infinita de declaraciones: , , , etc. $0={\tfrac {(0)(0+1)}{2}}$ $0+1={\tfrac {(1)(1+1)}{2}}$ $0+1+2={\tfrac {(2)(2+1)}{2}}$

Proposición. Para cada, $n\in \mathbb {N}$ $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$

Prueba. Sea $P (n)$ el enunciado Damos una prueba por inducción sobre $n$ . $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$

Caso base: Demuestre que la afirmación es válida para el número natural más pequeño $n = 0$ .

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

Paso de inducción: Demuestre que para cada $k \geq 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 , el caso único $n = k$ se cumple, lo que significa que $P (k)$ es verdadero:

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

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

Algebraicamente , el lado derecho se simplifica como:

{\begin{alineado}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)} {2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)} {2}}.\end{aligned}}

Igualando los extremos izquierdo y derecho, deducimos que:

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

P (k + 1)

Conclusión: Dado que se ha demostrado que tanto el caso base como el paso de inducción son verdaderos, por inducción matemática el enunciado $P (n)$ es válido para todo número natural $n$ . QED

Una desigualdad trigonométrica

La inducción se utiliza a menudo para demostrar desigualdades . Como ejemplo, demostramos que para cualquier número real y número natural . $\left|\sin nx\right|\leq n\left|\sin x\right|$ $x$ $n$

A primera vista, puede parecer que una versión más general, para cualquier número real , podría demostrarse sin inducción; pero el caso muestra que puede ser falso para valores no enteros de . Esto sugiere que examinemos el enunciado específicamente para los valores naturales de , y la inducción es la herramienta más disponible. $\left|\sin nx\right|\leq n\left|\sin x\right|$ $n,x$ ${\textstyle n={\frac {1}{2}},\,x=\pi }$ $n$ $n$

Proposición. Para cualquieray,. $x\in \mathbb {R}$ $n\in \mathbb {N}$ $\left|\sin nx\right|\leq n\left|\sin x\right|$

Prueba. Fije un número real arbitrario y sea el enunciado . Inducimos en . $x$ $P(n)$ $\left|\sin nx\right|\leq n\left|\sin x\right|$ $n$

Caso base: El cálculo verifica . $\left|\sin 0x\right|=0\leq 0=0\left|\sin x\right|$ $P(0)$

Paso de inducción: Mostramos la implicación para cualquier número natural . Supongamos la hipótesis de inducción: para un valor dado , el caso único es verdadero. Usando la fórmula de la suma de ángulos y la desigualdad de triángulos , deducimos: $P(k)\implica P(k+1)$ $k$ $n=k\geq 0$ $P(k)$

{\begin{alineado}\left|\sin(k+1)x\right|&=\left|\sin kx\cos x+\sin x\cos kx\right|&&{\text{(ángulo suma)}}\\&\leq \left|\sin kx\cos x\right|+\left|\sin x\,\cos kx\right|&&{\text{(desigualdad del triángulo)}}\\& =\left|\sin kx\right|\left|\cos x\right|+\left|\sin x\right|\left|\cos kx\right|\\&\leq \left|\sin kx\ right|+\left|\sin x\right|&&(\left|\cos t\right|\leq 1)\\&\leq k\left|\sin x\right|+\left|\sin x\ right|&&{\text{(hipótesis de inducción}})\\&=(k+1)\left|\sin x\right|.\end{aligned}}

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

Conclusión: la proposición es válida para todos los números naturales QED $P(n)$ $n.$

Variantes

En la práctica, las pruebas por inducción suelen estructurarse de forma diferente, dependiendo de la naturaleza exacta de la propiedad que se debe 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 sólo para todos los números $n$ mayores o iguales a un cierto número $b$ , entonces la prueba por inducción consiste en lo siguiente:

Demostrando que el enunciado se cumple cuando $n = b$ .
Mostrando que si el enunciado es válido para un número arbitrario $n \geq b$ , entonces el mismo enunciado también es válido para $n + 1$ .

Esto se puede utilizar, por ejemplo, para demostrar que $2 n \geq n + 5$ para $n \geq 3$ .

De esta manera, se puede demostrar que algún enunciado $P (n)$ es válido para todo $n \geq 1$ , o incluso para todo $n \geq -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)$ entonces demostrarlo con estas dos reglas equivale a demostrar $P (n + b)$ para todos los números naturales $n$ con un caso base de inducción $0$ . ^[dieciséis]

Ejemplo: formar cantidades en dólares mediante monedas

Supongamos una oferta infinita de monedas de 4 y 5 dólares. La inducción se puede utilizar para demostrar que cualquier cantidad entera de dólares mayor o igual a $12$ puede formarse mediante una combinación de dichas monedas. Sea $S (k)$ el enunciado " $k$ dólares pueden formarse mediante una combinación de monedas de 4 y 5 dólares". La prueba de que $S (k)$ es cierta para todo $k \geq 12$ se puede lograr mediante inducción sobre $k$ de la siguiente manera:

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

Paso de inducción: dado que $S (k)$ se cumple para algún valor de $k \geq 12$ ( hipótesis de inducción ), demuestre que $S (k + 1)$ también se cumple. Supongamos que $S (k)$ es cierto para algún $k \geq 12$ arbitrario . 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 obtener $k + 1$ dólares. De lo contrario, si sólo se utilizan monedas de 5 dólares, $k$ debe ser múltiplo de 5 y, por tanto, al menos 15; pero luego podemos reemplazar tres monedas de 5 dólares por cuatro monedas de 4 dólares para obtener $k + 1$ dólares. En cada caso, $S (k + 1)$ es verdadera.

Por lo tanto, según el principio de inducción, $S (k)$ se cumple para todo $k \geq 12$ y la prueba está completa.

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

Inducción en más de un mostrador.

A veces es deseable probar un enunciado que involucra dos números naturales, $n$ y $m$ , iterando el proceso de inducción. Es decir, se prueba un caso base y un paso de inducción para $n$ , y en cada uno de ellos se 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 involucren tres o más fichas.

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 utiliza para demostrar que alguna afirmación $Q (n)$ es falsa para todos los números naturales $n$ . Su forma tradicional consiste en demostrar que si $Q (n)$ es verdadera para algún número natural $n$ , también es válida para algún número natural estrictamente menor $m$ . Debido a que no hay secuencias infinitas decrecientes de números naturales, esta situación sería imposible, mostrando así ( por contradicción ) que $Q (n)$ no puede ser cierta para ningún $n$ .

La validez de este método puede verificarse a partir del principio habitual de inducción matemática. Utilizando la inducción matemática del enunciado $P (n)$ definido como " $Q (m)$ es falso para todos los números naturales $m$ menores o iguales que $n$ ", se deduce que $P (n)$ es válido para todos $los n$ , lo que significa que $Q (n))$ es falso para todo número natural $n$ .

Inducción matemática limitada

Si se desea demostrar que una propiedad $P$ se cumple para todos los números naturales menores o iguales que $n$ , basta con demostrar $que P$ satisface las siguientes condiciones: ^[17]

$P$ es válido para 0,
Para cualquier número natural $x$ menor que $n$ , si $P$ es válido para $x$ , entonces $P$ es válido para $x + 1$

inducción de prefijo

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

\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 demuestra la siguiente afirmación en el paso de inducción:

\forall k\,(P(k)\to P(2k)\land P(2k+1))

\forall k\,\left(P\!\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)

El principio de inducción luego "automatiza" las aplicaciones log ₂ n 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, formado al truncar el bit bajo 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 tradicional de predecesores se interpreta computacionalmente como un bucle $de n$ pasos, entonces la inducción de prefijo correspondería a un bucle log $de n$ pasos. Por eso, las pruebas que utilizan la inducción de prefijos son "más factiblemente constructivas" que las pruebas que utilizan la inducción de predecesores.

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 sintácticamente compleja (agregando un cuantificador universal acotado ), por lo que los resultados interesantes que relacionan la inducción de prefijos con el cálculo en tiempo polinomial dependen de excluir por completo los cuantificadores ilimitados y limitar la alternancia. de cuantificadores universales y existenciales acotados permitidos en la declaración. ^[18]

Se puede llevar la idea un paso más allá: hay que demostrar

\forall k\,\left(P\!\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)

log log n

P (0)

P (n)

^{[ cita necesaria ]}

Inducción completa (fuerte)

Otra variante, llamada inducción completa , inducción del curso de valores o inducción fuerte (en contraste con la cual la forma básica de inducción a veces se conoce como inducción débil ), hace que el paso de inducción sea más fácil de probar mediante el uso de una hipótesis más fuerte: se prueba el enunciado bajo el supuesto que se cumple para todos los números naturales menores que ; por el contrario, la forma básica sólo asume . El nombre "inducción fuerte" no significa que este método pueda demostrar más que "inducción débil", sino que simplemente se refiere a la hipótesis más fuerte utilizada en el paso de inducción. $P(m+1)$ $P(n)$ $n$ $m+1$ $P(m)$

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

Aunque la forma que acabamos de describir requiere que uno pruebe el caso base, esto es innecesario si se puede probar (asumiendo que para todos es menor ) para todos . 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. De esta forma el caso base queda subsumido por el caso , donde se demuestra sin ningún otro supuesto; Es posible que este caso deba tratarse por separado, pero a veces se aplica el mismo argumento para y , lo que hace que la prueba sea más simple y elegante. En este método, sin embargo, es vital garantizar que la prueba de no asuma implícitamente que , por ejemplo diciendo "elija un arbitrario ", o suponiendo que un conjunto de $m$ elementos tiene un elemento. $P(m)$ $P(n)$ $n$ $m\geq 0$ $m=0$ $P(0)$ $P(n)$ $m=0$ $m>0$ $P(m)$ $m>0$ $n<m$

Equivalencia con inducción ordinaria

La inducción completa es equivalente a la inducción matemática ordinaria descrita anteriormente, en el sentido de que una prueba mediante un método puede transformarse en una prueba mediante el otro. Supongamos que hay una prueba de por inducción completa. Entonces, esta prueba puede transformarse en una prueba de inducción ordinaria asumiendo una hipótesis inductiva más fuerte. Sea el enunciado " es válido para todo lo que "; ésta se convierte en la hipótesis inductiva de la inducción ordinaria. Entonces podemos mostrar y por suponer únicamente y mostrar que implica . ^[19] $P(n)$ $Q(n)$ $P(m)$ $m$ $0\leq m\leq n$ $Q(0)$ $Q(n+1)$ $n\in \mathbb {N}$ $Q(n)$ $Q(n)$ $P(n)$

Si, por el contrario, se hubiera probado por inducción ordinaria, la prueba ya sería efectivamente una prueba por inducción completa: se prueba en el caso base, sin utilizar suposiciones, y se prueba en el paso de inducción, en el que se pueden suponer todos Casos anteriores, pero solo es necesario usar el caso . $P(n)$ $P(0)$ $P(n+1)$ $P(n)$

Ejemplo: números de Fibonacci

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

F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}

n

número de Fibonacci proporción áurea raíces polinomio

F_{n}

{\textstyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}

{\textstyle \psi ={\frac {1}{2}}(1-{\sqrt {5}})}

x^{2}-x-1

F_{n+2}=F_{n+1}+F_{n}

n\in \mathbb {N}

{\textstyle F_{n+2}}

{\textstyle F_{n+1}}

{\textstyle F_{n}}

n=0

{\textstyle n=1}

Ejemplo: factorización prima

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

Ejemplo: montos en dólares revisados

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

S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \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 base: Demuestre que es válido para . $S(k)$ $k=12,13,14,15$

{\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}

El caso base se mantiene.

Paso de inducción: dados algunos , supongamos que se cumple para todos con . Demuestre que eso es válido. $j>15$ $S(m)$ $m$ $12\leq m<j$ $S(j)$

Elegir y observar eso demuestra que se cumple, mediante la hipótesis inductiva. Es decir, la suma puede estar formada por alguna combinación de monedas de un dólar. Luego, simplemente agregando una moneda de un dólar a esa combinación se obtiene la suma . Es decir, tiene ^[20] QED $m=j-4$ $15<j\implies 12\leq j-4<j$ $S(j-4)$ $j-4$ $4$ $5$ $4$ $j$ $S(j)$

Inducción hacia adelante y hacia atrás

A veces, es más conveniente deducir hacia atrás, demostrando el enunciado para , dada su validez para . Sin embargo, no basta con demostrar la validez de la declaración para ningún número único para establecer el caso base; en cambio, es necesario probar el enunciado para un subconjunto infinito de números naturales. Por ejemplo, Augustin Louis Cauchy utilizó por primera vez la inducción directa (regular) para demostrar la desigualdad de las medias aritméticas y geométricas para todas las potencias de 2 , y luego utilizó la inducción hacia atrás para demostrarla para todos los números naturales. ^[21]^[22] $n-1$ $n$

Ejemplo de error en el paso de inducción

El paso de inducción debe demostrarse 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 : ^[23]

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

Paso de inducción: asumir como hipótesis de inducción que dentro de cualquier conjunto de caballos, existe un solo color. Ahora mira cualquier par de caballos. Numéralos: . Considere los conjuntos y . Cada uno es un conjunto de solo caballos, por lo tanto dentro de cada uno solo hay un color. Pero los dos conjuntos se superponen, por lo que debe haber un solo color entre todos los caballos. $n$ $n+1$ $1,2,3,\dotsc ,n,n+1$ ${\textstyle \left\{1,2,3,\dotsc ,n\right\}}$ ${\textstyle \left\{2,3,4,\dotsc ,n+1\right\}}$ $n$ $n+1$

El caso base es trivial y el paso de inducción es correcto en todos los casos . Sin embargo, el argumento utilizado en el paso de inducción es incorrecto para , porque la afirmación de que "los dos conjuntos se superponen" es falsa para y . $n=1$ $n>1$ $n+1=2$ ${\textstyle \left\{1\right\}}$ ${\textstyle \left\{2\right\}}$

Formalización

En lógica de segundo orden , se puede escribir el " axioma de inducción" de la siguiente manera:

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

P (\cdot)

k

n

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)$ es válido para cualquier número natural $n$ a partir del caso base y el paso de inducción.

El primer cuantificador del axioma abarca predicados en lugar de números individuales. Este es un cuantificador de segundo orden, lo que significa que este axioma está enunciado 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 más información sobre este tema.

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

0 es un número natural.
La función sucesora $s$ de cada número natural produce un número natural $(s (x) = x + 1)$ .
La función sucesora es inyectiva .
0 no está en el rango de $s$ .

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

\forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}

A

construcción de los números naturales axioma del infinito el esquema de axioma de especificación

inducción transfinita

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

Aplicada a un conjunto bien fundamentado, la inducción transfinita puede formularse como un solo paso. Para demostrar que un enunciado $P (n)$ es válido para cada número ordinal:

Demuestre, para cada número ordinal $n$ , que si $P (m)$ se cumple para todo $m < n$ , entonces $P (n)$ también se cumple.

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

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

cuando $n$ es un elemento mínimo, es decir, no hay ningún elemento menor que $n$ ;
cuando $n$ tiene un predecesor directo, es decir, el conjunto de elementos menores que $n$ tiene un elemento mayor;
cuando $n$ no tiene un predecesor directo, es decir, $n$ es el llamado ordinal límite .

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

Relación con el principio de buen orden

El principio de inducción matemática suele enunciarse como un axioma de los números naturales; véase 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 de la tricotomía : para cualquier número natural $n$ y $m$ , $n$ es menor o igual que $m$ si y solo si $m$ no es menor 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 está entre n y $n + 1$ .
Ningún número natural es menor que cero.

Entonces se puede demostrar que la inducción, dados los axiomas enumerados anteriormente, implica el principio de buen ordenamiento. La siguiente prueba utiliza inducción completa y el primer y cuarto axiomas.

Prueba. Supongamos que existe un conjunto no vacío , $S$ , de números naturales que no tiene ningún 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 mínimo de $S.$ Además, sea $n$ un número natural y supongamos que $P (m)$ es cierto para todos los números naturales $m$ menores que $n + 1$ . Entonces si $P (n +1)$ es falso $n +1$ está en $S$ , siendo así un elemento mínimo en $S$ , una contradicción. Por tanto, $P (n + 1)$ es verdadera. Por lo tanto, según 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. QED

" Recta numérica " para el conjunto

html.skin-theme-clientpref-night .mw-parser-output div:not(.notheme)>.tmp-color,html.skin-theme-clientpref-night .mw-parser-output p>.tmp-color,html.skin-theme-clientpref-night .mw-parser-output table:not(.notheme) .tmp-color{color:inherit!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output div:not(.notheme)>.tmp-color,html.skin-theme-clientpref-os .mw-parser-output p>.tmp-color,html.skin-theme-clientpref-os .mw-parser-output table:not(.notheme) .tmp-color{color:inherit!important}} {(0, n): n \in N} \cup {(1, n): n \in N}

. Los números se refieren al segundo componente de los pares; el primero se puede obtener por color o ubicación.

Por otro lado, el conjunto , que se muestra en la imagen, está bien ordenado ^[24]^{: 35lf} por el orden lexicográfico . Además, excepto 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 la función sucesora de Peano se define en pares mediante $succ($ $x$ $,$ $n$ $) = ($ $x$ $,$ $n$ $+ 1)$ para todos y . Como ejemplo de la violación del axioma de inducción, defina el predicado $P$ $($ $x$ $,$ $n$ $)$ como $($ $x$ $,$ $n$ $) = (0, 0)$ o $($ $x$ $,$ $n$ $) = succ($ $y$ $,$ $m$ $)$ para algunos y . Entonces el caso base $P$ $(0, 0)$ es trivialmente cierto, al igual que el paso de inducción: si $P$ $($ $x$ $,$ $n$ $)$ , entonces $P$ $(succ($ $x$ $,$ $n$ $))$ . Sin embargo, $P$ no es cierta para todos los pares del conjunto. $\{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}$ $x\in \{0,1\}$ $n\in \mathbb {N}$ $y\in \{0,1\}$ $m\in \mathbb {N}$

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 todos los axiomas. ^[24]

^{En varios libros [24]} y fuentes se imprime erróneamente que el principio de 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; ^[24] específicamente, el principio de buen orden implica el axioma de inducción en el contexto de los dos primeros axiomas enumerados anteriormente y

Todo 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 suponer que $n - 1$ es un número natural único y bien definido, propiedad que no está implícita en los otros axiomas de Peano. ^[24]

Ver también

Notas

^ Matt DeVos, Inducción Matemática, Universidad Simon Fraser
↑ Gerardo con Diaz, Inducción matemática Archivado el 2 de mayo de 2013 en Wayback Machine , Universidad de Harvard
^ Anderson, Robert B. (1979). Demostrar que los programas son correctos . Nueva York: John Wiley & Sons. pag. 1.ISBN 978-0471033950.
^ Suber, Peter. "Inducción matemática". Universidad Earlham. Archivado desde el original el 24 de mayo de 2011 . Consultado el 26 de marzo de 2011 .
^ Acerbi 2000.
^ Rashed 1994, págs. 62–84.
^ Conocimiento matemático e interacción de prácticas "La primera prueba implícita por inducción matemática se proporcionó alrededor del año 1000 en una obra del matemático persa Al-Karaji"
^ Katz (1998), pág. 255
^ ab Cajori (1918), pág. 197: 'El proceso de razonamiento llamado "Inducción Matemática" ha tenido varios orígenes independientes. Se remonta al suizo Jakob (James) Bernoulli, al francés B. Pascal y P. Fermat y al italiano F. Maurolycus. [...] Leyendo un poco entre líneas se pueden encontrar rastros de inducción matemática aún antes, en los escritos de los hindúes y los griegos, como, por ejemplo, en el "método cíclico" de Bhaskara y en la prueba de Euclides. que el número de números primos es infinito.'
^ Erupcionado 1994, pag. 62.
^ Simonson 2000.
^ Rabinovitch 1970.
^ "A veces es necesario demostrar un teorema que será verdadero siempre que una cierta cantidad n que involucra sea un número entero o un número entero y el método de prueba suele ser del siguiente tipo. Primero . Se demuestra que el teorema es verdadero. cuando n = 1. En segundo lugar , se demuestra que si el teorema es verdadero cuando n es un número entero dado, será verdadero si n es el siguiente entero mayor. Por lo tanto, el teorema es verdadero universalmente. denominado sorites continuo " (Boole c. 1849 Tratado elemental sobre lógica no matemática, págs. 40-41 reimpreso en Grattan-Guinness, Ivor y Bornet, Gérard (1997), George Boole: Selected Manuscripts on Logic and its Philosophy , Birkhäuser Verlag, Berlín, ISBN 3-7643-5456-9 )
^ Peirce 1881.
^ Escudos 1997.
^ Ted Sundstrom, Razonamiento matemático , p. 190, Pearson, 2006, ISBN 978-0131877184
^ Smullyan, Raymond (2014). Una guía para principiantes de lógica matemática . Dover. pag. 41.ISBN 0486492370.
^ Buss, Samuel (1986). Aritmética acotada . Nápoles: Bibliópolis.
^ "Prueba: una inducción fuerte equivale a una inducción débil". Universidad de Cornell . Consultado el 4 de mayo de 2023 .
^ . Shafiei, Niloufar. "Fuerte inducción y buen orden" (PDF) . Universidad de York . Consultado el 28 de mayo de 2023 .
^ "Inducción hacia adelante y hacia atrás | Wiki brillante de matemáticas y ciencias". brillante.org . Consultado el 23 de octubre de 2019 .
^ Cauchy, Augustin-Louis (1821). Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique, Archivado el 14 de octubre de 2017 en Wayback Machine Paris. La prueba de la desigualdad de medias aritméticas y geométricas se puede encontrar en las páginas 457 y siguientes.
^ Cohen, Joel E. (1961). "Sobre la naturaleza de la prueba matemática". Opus .. Reimpreso en A Random Walk in Science (RL Weber, ed.), Crane, Russak & Co., 1973.
^ abcde Öhman, Lars – Daniel (6 de mayo de 2019). "¿Son equivalentes la inducción y el buen orden?". El inteligente matemático . 41 (3): 33–40. doi : 10.1007/s00283-019-09898-4 .

Referencias

Introducción

Franklin, J .; Daoud, A. (2011). Prueba en matemáticas: una introducción. Sídney: Libros de Kew. ISBN 978-0-646-54509-7.(Cap. 8.)
"Inducción matemática". Enciclopedia de Matemáticas . Prensa EMS . 2001 [1994].
Hermes, Hans (1973). Introducción a la Lógica Matemática . Hochschultext. Londres: Springer. ISBN 978-3540058199. ISSN 1431-4657. SEÑOR 0345788.
Knuth, Donald E. (1997). El arte de la programación informática, volumen 1: algoritmos fundamentales (3ª ed.). Addison-Wesley. ISBN 978-0-201-89683-1.(Sección 1.2.1: Inducción matemática, págs. 11 a 21.)
Kolmogorov, Andrey N .; Fomin, Sergei V. (1975). Análisis real introductorio. Silverman, RA (trad., ed.). Nueva York: Dover. ISBN 978-0-486-61226-3.(Sección 3.8: Inducción transfinita, págs. 28-29.)

Historia

Acerbi, Fabio (agosto de 2000). "Platón: Parménides 149a7-c3. ¿Una prueba por inducción completa?". Archivo de Historia de las Ciencias Exactas . 55 (1): 57–76. doi :10.1007/s004070000020. JSTOR 41134098. S2CID 123045154.
Bussey, WH (1917). "El origen de la inducción matemática". El Mensual Matemático Estadounidense . 24 (5): 199–207. doi :10.2307/2974308. JSTOR 2974308.
Cajori, Florián (1918). "Origen del nombre "Inducción Matemática"". The American Mathematical Monthly . 25 (5): 197–201. doi :10.2307/2972638. JSTOR 2972638.
Fowler, D. (1994). "¿Podrían los griegos haber utilizado la inducción matemática? ¿La usaron?". Física . 31 : 253–265.
Freudenthal, Hans (1953). "Zur Geschichte der vollständigen Inducción". Archivos Internacionales de Historia de las Ciencias . 6 : 17–37.
Katz, Víctor J. (1998). Historia de las matemáticas: una introducción . Addison-Wesley . ISBN 0-321-01618-1.
Peirce, Charles Sanders (1881). "Sobre la lógica del número". Revista Estadounidense de Matemáticas . 4 (1–4): 85–95. doi :10.2307/2369151. JSTOR 2369151. SEÑOR 1507856.Reimpreso (CP 3.252–288), (W 4:299–309)
Rabinovitch, Nachum L. (1970). "El rabino Levi Ben Gershon y los orígenes de la inducción matemática". Archivo de Historia de las Ciencias Exactas . 6 (3): 237–248. doi :10.1007/BF00327237. SEÑOR 1554128. S2CID 119948133.
Erupcionado, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archivo de Historia de las Ciencias Exactas (en francés). 9 (1): 1–21. doi :10.1007/BF00348537. SEÑOR 1554160. S2CID 124040444.
Erupcionado, R. (1994). "Inducción matemática: al-Karajī y al-Samawʾal". El desarrollo de las matemáticas árabes: entre la aritmética y el álgebra. Estudios de Boston en Filosofía de la Ciencia. vol. 156. Medios científicos y comerciales de Springer. ISBN 9780792325659.
Escudos, Paul (1997). "Axiomatización de la aritmética de Peirce". En Houser, Nathan; Roberts, Don D.; Evra, James Van (eds.). Estudios de lógica de Charles S. Peirce . Prensa de la Universidad de Indiana. págs. 43–52. ISBN 0-253-33020-3. SEÑOR 1720827.
Simonson, Charles G. (invierno de 2000). "Las matemáticas de Levi ben Gershon, el Ralbag" (PDF) . Bekhol Derakhekha Daehu . 10 . Prensa de la Universidad Bar-Ilan: 5–21.
Unguru, S. (1991). "Matemáticas griegas e inducción matemática". Física . 28 : 273–289.
Unguru, S. (1994). "Cazar después de la inducción". Física . 31 : 267–272.
Vacca, G. (1909). "Maurolycus, el primer descubridor del principio de inducción matemática". Boletín de la Sociedad Matemática Estadounidense . 16 (2): 70–73. doi : 10.1090/S0002-9904-1909-01860-9 . SEÑOR 1558845.
Yadegari, Mohammad (1978). "El uso de la inducción matemática por Abū Kāmil Shujā' Ibn Aslam (850-930)". Isis . 69 (2): 259–262. doi :10.1086/352009. JSTOR 230435. S2CID 144112534.