La inducción matemática es una técnica de prueba matemática . Esencialmente se usa para probar que un enunciado P ( n ) es válido para todo número natural n = 0, 1, 2, 3,. . . ; es decir, el enunciado general es una secuencia de infinitos casos P (0), P (1), P (2), P (3),. . . . Las metáforas informales ayudan a explicar esta técnica, como caer dominó o subir una escalera:
La inducción matemática demuestra que podemos subir tan alto como queramos en una escalera, al demostrar que podemos subir al peldaño inferior (la base ) y que de cada peldaño podemos subir al siguiente (el peldaño ).
- Matemáticas concretas , márgenes de la página 3.
Una prueba por inducción consta de dos casos. El primero, el caso base (o base ), prueba el enunciado para n = 0 sin asumir ningún conocimiento de otros casos. El segundo caso, el paso de inducción , demuestra que si el enunciado se cumple para cualquier caso dado n = k , entonces también debe ser válido para el siguiente caso n = k + 1. Estos dos pasos establecen que el enunciado se cumple para cada número natural n . [3] El caso base no necesariamente comienzan con n = 0, pero a menudo con n = 1, y posiblemente con cualquier número natural fijo n = N , el establecimiento de la verdad de la declaración para todos los números naturales n ≥ N .
El método puede ampliarse para probar afirmaciones sobre estructuras bien fundamentadas 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 extendido está estrechamente relacionada con la recursividad . La inducción matemática es una regla de inferencia utilizada en pruebas formales y, de alguna forma, es la base de todas las pruebas de corrección de los programas de computadora . [4]
Aunque su nombre puede sugerir lo contrario, la inducción matemática no debe confundirse con el razonamiento inductivo como se usa en filosofía (ver Problema de la inducción ). El método matemático examina un número infinito de casos para probar un enunciado general, pero lo hace mediante una cadena finita de razonamiento deductivo que involucra la variable n , que puede tomar un número infinito de valores. [5]
Historia
En 370 aC, el Parménides de Platón puede haber contenido un ejemplo temprano de una prueba inductiva implícita. [6] Una técnica iterada opuesta, contar hacia atrás en lugar de hacia arriba, se encuentra en la paradoja de los 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 se dejaba un montón, entonces un solo grano de arena (o incluso ningún grano) forma un montón. [7]
En India, las primeras demostraciones implícitas por inducción matemática aparecen en el " método cíclico " de Bhaskara , [8] y en el al-Fakhri escrito por al-Karaji alrededor del año 1000 d.C., quien lo aplicó a secuencias aritméticas para probar el teorema y las propiedades del binomio. del triángulo de Pascal . [9] [10]
Ninguno de estos antiguos matemáticos, sin embargo, declaró explícitamente la hipótesis de la inducción. Otro caso similar (contrario a lo que ha escrito Vacca, como Freudenthal cuidadosamente mostró) [11] fue el de Francesco Maurolico en su Arithmeticorum libri duo (1575), quien usó 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 el de Gersonides (1288-1344). [12] [13] 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 un amplio uso de un principio relacionado: la 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 conocida. El tratamiento formal moderno del principio se produjo sólo en el siglo XIX, con George Boole , [14] Augustus de Morgan , Charles Sanders Peirce , [15] [16] Giuseppe Peano y Richard Dedekind . [8]
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 cumple para todos los valores de n . La prueba consta de dos pasos:
- El caso inicial o base : demuestre que la declaración es válida para 0 o 1.
- El paso de inducción , el paso inductivo o el caso del paso : demuestre que para cada n , si el enunciado se cumple para n , entonces se cumple para n + 1 . En otras palabras, suponga que el enunciado se cumple 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 inductivo, 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 inductivo, se asume la hipótesis de inducción para n y luego se usa esta suposición para demostrar que el enunciado es válido para n + 1 .
Los autores que prefieren definir 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 de
Suma de números naturales consecutivos
La inducción matemática se puede utilizar para probar el siguiente enunciado P ( n ) para todos los números naturales n .
Esto 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.
Proposición. Para cualquier,
Prueba. Sea P ( n ) el enunciadoDamos una prueba por inducción en n .
Caso base : demuestre que el enunciado es válido para el número natural más pequeño n = 0.
P (0) es claramente cierto:
Paso inductivo : demuestre que para cualquier k ≥ 0, si P ( k ) se cumple, entonces P ( k +1) también se cumple.
Suponga 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:
Resulta que:
Algebraicamente, el lado derecho se simplifica como:
Al equiparar los extremos de la mano izquierda y la derecha, deducimos que:
Es decir, el enunciado P ( k + 1) también es válido, estableciendo el paso inductivo.
Conclusión : Dado que se ha demostrado que tanto el caso base como el paso inductivo son verdaderos, por inducción matemática se cumple el enunciado P ( n ) para todo número natural n . ∎
Una desigualdad trigonométrica
La inducción se usa a menudo para probar desigualdades. Como ejemplo, probamos que para cualquier número real y numero natural .
A primera vista, puede parecer que una versión más general, para cualquier número real, podría probarse sin inducción; pero el caso muestra que puede ser falso para valores no enteros de . Esto sugiere que examinemos la declaración específicamente para los valores naturales de, y la inducción es la herramienta más fácil.
Proposición . Para cualquier, .
Prueba. Fijar un número real arbitrario, y deja ser la declaración . Inducimos en.
Caso base: el cálculo verifica .
Paso inductivo: mostramos la implicación para cualquier número natural . Suponga la hipótesis de inducción: para un valor dado, el caso único es verdad. Usando la fórmula de la suma de ángulos y la desigualdad del triángulo , deducimos:
La desigualdad entre las cantidades del extremo izquierdo y derecho muestra que es cierto, lo que completa el paso inductivo.
Conclusión : la proposición es válido para todos los números naturales . ∎
Variantes
En la práctica, las pruebas por inducción a menudo se estructuran de manera diferente, dependiendo de la naturaleza exacta de la propiedad a probar. Todas las variantes de inducción son casos especiales de inducción transfinita; ver más abajo .
Base de inducción distinta de 0 o 1
Si se desea probar un enunciado, no para todos los números naturales, sino solo para todos los números n mayores o iguales que un cierto número b , entonces la prueba por inducción consiste en:
- Demostrar que el enunciado se cumple cuando n = b .
- Demostrando que si el enunciado se cumple para un número arbitrario n ≥ b , entonces el mismo enunciado también es válido para n + 1 .
Esto se puede usar, por ejemplo, para mostrar que 2 n ≥ n + 5 para n ≥ 3 .
De esta manera, se puede probar que algún enunciado P ( n ) es válido para todo n ≥ 1 , o incluso para todo n ≥ −5 . Esta forma de inducción matemática es en realidad un caso especial de la forma anterior, porque si el enunciado a probar es P ( n ), entonces probarlo con estas dos reglas es equivalente a probar P ( n + b ) para todos los números naturales n con un caso base de inducción 0 . [17]
Ejemplo: formar cantidades en dólares por monedas
Suponga un suministro infinito de monedas de 4 y 5 dólares. La inducción se puede utilizar para demostrar que cualquier cantidad total de dólares mayor o igual a 12 puede formarse mediante una combinación de tales monedas. Sea S ( k ) el enunciado " la cantidad de k dólares se puede formar mediante una combinación de monedas de 4 y 5 dólares ". La prueba de que S ( k ) es verdadera para todo k ≥ 12 se puede lograr por inducción en k de la siguiente manera:
Caso base : Mostrar que S ( k ) es válido 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 ≥ 12 ( hipótesis de inducción ), demuestre que S ( k + 1) también se cumple:
- Suponga que S ( k ) es cierto para algún k arbitrario ≥ 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 hacer k + 1 dólares. De lo contrario, si solo se utilizan 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 cierto.
Por lo tanto, según el principio de inducción, S ( k ) se cumple para todo k ≥ 12 , y la demostración es 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 más bajo m . Para m = 11 , el caso base es en realidad falso; para m = 10 , el segundo caso en el paso de inducción (reemplazando tres monedas de 5 por cuatro de 4 dólares) no funcionará; y mucho menos para m aún más bajo .
Inducción en más de un mostrador
A veces es deseable para probar una declaración que implica dos números naturales, n y m , iterando el proceso de inducción. Es decir, se prueba un caso base y un paso inductivo para n , y en cada uno de ellos se prueba un caso base y un paso inductivo 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 contadores.
Descenso infinito
El método de descenso infinito es una variación de la inducción matemática que fue utilizada por Pierre de Fermat . Se usa para mostrar que algún enunciado Q ( n ) es falso 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 m estrictamente más pequeño . 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 cierto para ningún n .
La validez de este método se puede verificar a partir del principio habitual de inducción matemática. Usando la inducción matemática en el 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 ) se cumple para todos los n , lo que significa que Q ( n ) es falso para todo número natural n .
Inducción de prefijo
La forma más común de prueba por inducción matemática requiere probar en el paso inductivo que
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 prefijo", en la que se prueba el siguiente enunciado en el paso inductivo:
o equivalente
Entonces, el principio de inducción "automatiza" log 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, tal como se forma truncando 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 del predecesor tradicional se interpreta computacionalmente como un bucle de n pasos, entonces la inducción de prefijo correspondería a un bucle log- n- step. Por eso, las demostraciones que utilizan la inducción de prefijo son "más factiblemente constructivas" que las demostraciones que utilizan la inducción predecesora.
La inducción del predecesor puede simular trivialmente la inducción del prefijo 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 polinómico dependen de excluir por completo los cuantificadores ilimitados y limitar la alternancia de cuantificadores universales y existenciales acotados permitidos en el enunciado. [18]
Se puede llevar la idea un paso más allá: hay que demostrar
con lo cual el principio de inducción "automatiza" log log n aplicaciones de esta inferencia para pasar de P (0) a P ( n ). Esta forma de inducción se ha utilizado, de forma análoga, para estudiar el cálculo paralelo log-time. [ cita requerida ]
Inducción completa (fuerte)
Otra variante, llamada inducción completa , inducción de curso de valores o inducción fuerte (en contraste con la que la forma básica de inducción se conoce a veces como inducción débil ), hace que el paso inductivo sea más fácil de probar utilizando una hipótesis más fuerte: uno prueba el enunciado bajo el supuesto de que es válido para todos los números naturales menos que ; por el contrario, la forma básica solo asume. El nombre "inducción fuerte" no significa que este método pueda resultar más que "inducción débil", sino que simplemente se refiere a la hipótesis más fuerte utilizada en el paso inductivo.
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, uno todavía tiene 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 ejemplo siguiente del número de Fibonacci .
Aunque el formulario que se acaba de describir requiere que uno pruebe el caso base, esto es innecesario si se puede probar (asumiendo para todos los inferiores ) para todos . Este es un caso especial de inducción transfinita como se describe a continuación. De esta forma, el caso base está subsumido por el caso, dónde se prueba con ningún otro ficticio; este caso puede necesitar manejarse por separado, pero a veces el mismo argumento se aplica para y , haciendo la prueba más simple y elegante. En este método, sin embargo, es vital asegurarse de que la prueba de no asume implícitamente que , por ejemplo, diciendo "elige un ", 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 describió anteriormente, en el sentido de que una prueba por un método puede transformarse en una prueba por el otro. Suponga que hay una prueba depor inducción completa. Dejar significar " se mantiene para todos tal que ". Luego se mantiene para todos si y solo si se mantiene para todos , y nuestra prueba de se transforma fácilmente en una prueba de por inducción (ordinaria). Si, por otro lado, había sido probado por inducción ordinaria, la prueba ya sería efectivamente una por inducción completa: se prueba en el caso base, sin utilizar suposiciones, y se prueba en el paso inductivo, en el que se pueden asumir todos los casos anteriores, pero sólo es necesario utilizar el caso .
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 inductivo. Por ejemplo, la inducción completa se puede utilizar para demostrar que
dónde es el n- ésimo número de Fibonacci ,(la proporción áurea ) y son las raíces del polinomio . Utilizando el hecho de que para cada , la identidad anterior se puede verificar mediante cálculo directo para si se supone que ya es válido para ambos y . Para completar la prueba, se debe verificar la identidad en los dos casos base: y .
Ejemplo: factorización prima
Otra prueba por inducción completa utiliza la hipótesis de que el enunciado es válido para todos losmás a fondo. Considere la afirmación de que "todo número natural mayor que 1 es un 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 inductivo, la hipótesis de inducción es que para un la declaración es válida para todos los más pequeños . Si es primo, entonces ciertamente es un producto de primos, y si no, entonces por definición es un producto: , donde ninguno de los factores es igual a 1; por 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 lo tanto es un producto de los productos primos y, por extensión, un producto de los primos en sí.
Ejemplo: montos en dólares revisados
Intentaremos probar el mismo ejemplo anterior , esta vez con una fuerte inducción . La declaración sigue siendo la misma:
Sin embargo, habrá ligeras diferencias en la estructura y los supuestos de la prueba, comenzando con el caso base extendido:
Caso base : demuestre que sostiene para .
El caso base aguanta.
Hipótesis de inducción : dadas algunas, asumir se mantiene para todos con .
Paso inductivo : demuestre que sostiene.
Elegir , y observando que muestra que sostiene, por hipótesis inductiva. Es decir, la suma puede estar formado por alguna combinación de y monedas de un dólar. Luego, simplemente agregando un moneda de un dólar a esa combinación da como resultado la suma . Es decir,sostiene. QED
Inducción hacia adelante y hacia atrás
A veces, es más conveniente deducir al revés, probando el enunciado para , dada su validez para . Sin embargo, probar la validez de la declaración para ningún número es suficiente para establecer el caso base; en su lugar, es necesario probar el enunciado de un subconjunto infinito de números naturales. Por ejemplo, Augustin Louis Cauchy usó primero la inducción directa (regular) para demostrar la desigualdad de las medias aritmética y geométrica para todas las potencias de 2, y luego usó la inducción hacia atrás para mostrarla para todos los números naturales. [19] [20]
Ejemplo de error en el paso inductivo
El paso inductivo debe demostrarse para todos los valores de n . Para ilustrar esto, Joel E. Cohen propuso el siguiente argumento, que pretende probar por inducción matemática que todos los caballos son del mismo color : [21]
- Caso base: En un juego de un solo caballo, solo hay un color.
- Paso inductivo: suponga como hipótesis de inducción que dentro de cualquier conjunto de caballos, solo hay un color. Ahora mire cualquier conjunto decaballos. Numerarlos:. Considere los conjuntos y . Cada uno es un conjunto de solocaballos, por lo tanto dentro de cada uno hay un solo color. Pero los dos conjuntos se superponen, por lo que debe haber un solo color entre todos caballos.
El caso base es trivial (ya que cualquier caballo es del mismo color que él), y el paso inductivo es correcto en todos los casos . Sin embargo, la lógica del paso inductivo es incorrecta para, debido a la afirmación de que "los dos conjuntos se superponen" es falsa (solo hay caballos antes de la remoción y después de la remoción, los grupos de un caballo no se superponen).
Formalización
En la lógica de segundo orden , uno puede escribir el " axioma de inducción" de la siguiente manera:
- ,
donde P (.) es una variable de predicados que implican un número natural y k y n son variables para números naturales .
En palabras, el caso base P (0) y el paso inductivo (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 a partir del caso base y el paso inductivo.
El primer cuantificador en el axioma abarca predicados en lugar de 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 posible predicado. 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 siguientes cuatro axiomas:
- 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 inducción por cuantificación sobre conjuntos:
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
El principio de inducción completa no solo es válido para enunciados sobre números naturales, sino también para enunciados sobre elementos de cualquier conjunto bien fundado , es decir, un conjunto con una relación irreflexiva
Aplicado a un conjunto bien fundamentado, se puede formular como un solo paso:
- Demuestre que si algún enunciado se cumple para todo m < n , entonces el mismo enunciado también se cumple para n .
Esta forma de inducción, cuando se aplica a un conjunto de 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 que son más pequeños que n tiene un elemento más grande;
- cuando n no tiene un predecesor directo, es decir, n es un 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 verdadero para todos n < m , entonces P es verdadero para m . Es vacuosamente 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 se suele enunciar como un axioma de los números naturales; ver axiomas de Peano . Es estrictamente más fuerte que el principio del buen orden en el contexto de los otros axiomas de Peano. Suponga lo siguiente:
- La tricotomía axioma: Para cualquier números naturales n y m , n es menor que o igual a m si y sólo 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 probar que la inducción, dados los axiomas enumerados anteriormente, implica el principio del buen orden. La siguiente demostración utiliza la 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. Deje que P ( n ) ser la afirmación de que n no se encuentra en S . Entonces P (0) es cierto, por si fuera falsa entonces 0 es el menos elemento de S . Además, sea n un número natural y suponga que P ( m ) es verdadero para todos los números naturales m menores 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 tanto, P ( n + 1) es verdadero. Por lo tanto, según el principio de inducción completo, P ( n ) se cumple para todos los números naturales n ; entonces S está vacío, una contradicción. QED
Por otro lado, el conjunto {(0, n ): n ∈ ℕ} ∪ {(1, n ): n ∈ ℕ} , que se muestra en la imagen, está bien ordenado [22] : 35lf por el orden lexicográfico . Además, a excepción del 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 por succ ( x , n ) = ( x , n + 1) para todo x ∈ {0,1} y n ∈ℕ. 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 ∈ {0,1} y m ∈ℕ. Entonces el caso base P (0,0) es trivialmente cierto, y también lo es el caso escalonado: si P ( x , n ) , entonces P ( succ ( x , n )) . Sin embargo, P no es cierto para todos los pares del conjunto.
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 ordenamiento adecuado permite modelos más exóticos que cumplen con todos los axiomas. [22]
Está impreso erróneamente en varios libros [22] y fuentes 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; [22] 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 .
El error común en muchas demostraciones erróneas es asumir que n - 1 es un número natural único y bien definido, una propiedad que no está implícita en los otros axiomas de Peano. [22]
Ver también
- Prueba combinatoria
- Puzzles de inducción
- Prueba por agotamiento
- Recursividad
- Recursión (informática)
- Inducción estructural
- Inducción transfinita
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
- ^ "El glosario definitivo de jerga matemática superior - prueba por inducción" . Bóveda de matemáticas . El 1 de agosto de 2019 . Consultado el 23 de octubre de 2019 .
- ^ Anderson, Robert B. (1979). Probar que los programas son correctos . Nueva York: John Wiley & Sons. pag. 1 . ISBN 978-0471033950.
- ^ Suber, Peter. "Inducción matemática" . Earlham College . Consultado el 26 de marzo de 2011 .
- ^ Acerbi 2000 .
- ^ Hyde y Raffman 2018 .
- ↑ a b 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. [...] Al leer un poco entre líneas, uno puede 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 demostración de Euclides que el número de primos es infinito '.
- ^ Rashed 1994 , p. 62-84.
- ^ Conocimiento matemático y la interacción de prácticas "La primera prueba implícita por inducción matemática se dio alrededor de 1000 en un trabajo del matemático persa Al-Karaji"
- ^ Rashed 1994 , p. 62.
- ^ Simonson 2000 .
- ^ Rabinovitch 1970 .
- ^ "A veces se requiere probar un teorema que será verdadero siempre que una cierta cantidad n que involucra sea un número entero o entero y el método de prueba sea usualmente del siguiente tipo. 1 ° . 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 número entero mayor. Por lo tanto, el teorema es cierto universalmente ... Esta especie de argumento puede denominarse sorites continuos"(Boole, circa 1849 , Tratado elemental de lógica, no matemática, páginas 40-41, reimpreso en Grattan-Guinness, Ivor y Bornet, Gérard (1997), George Boole: Manuscritos seleccionados sobre lógica y su filosofía , Birkhäuser Verlag, Berlina, ISBN 3-7643-5456-9 )
- ^ Peirce 1881 .
- ^ Escudos 1997 .
- ^ Ted Sundstrom, Razonamiento matemático , p. 190, Pearson, 2006, ISBN 978-0131877184
- ^ Buss, Samuel (1986). Aritmética acotada . Nápoles: Bibliopolis.
- ^ "Inducción hacia adelante y hacia atrás | Wiki brillante de matemáticas y ciencias" . shiny.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 la Wayback Machine Paris. La prueba de la desigualdad de las medias geométrica y aritmética se puede encontrar en las páginas 457 y siguientes.
- ^ Cohen, Joel E. (1961), "Sobre la naturaleza de la demostración matemática", Opus. Reimpreso en A Random Walk in Science (RL Weber, ed.), Crane, Russak & Co., 1973.
- ^ a b c d e Ö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 . Sydney: Kew Books. ISBN 978-0-646-54509-7. (Capítulo 8.)
- "Inducción matemática" , Enciclopedia de las matemáticas , EMS Press , 2001 [1994]
- Hermes, Hans (1973). Introducción a la lógica matemática . Hochschultext. Londres: Springer. ISBN 978-3540058199. ISSN 1431-4657 .
- 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-21.)
- Kolmogorov, Andrey N .; Fomin, Sergei V. (1975). Introducción al análisis real . 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 .
- Bussey, WH (1917). "El origen de la inducción matemática". American Mathematical Monthly . 24 (5): 199–207. doi : 10.2307 / 2974308 . JSTOR 2974308 .
- Cajori, Florian (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 usado la inducción matemática? ¿La usaron?". Physis . XXXI : 253-265.
- Freudenthal, Hans (1953). "Zur Geschichte der vollständigen Inducción". Archives Internationales d'Histoire des Sciences . 6 : 17–37.
- Hyde, Dominic; Raffman, Diana (2018), Zalta, Edward N. (ed.), "Sorites Paradox" , The Stanford Encyclopedia of Philosophy (verano de 2018 ed.), Metaphysics Research Lab, Stanford University , consultado el 23 de octubre de 2019
- Katz, Victor J. (1998). Historia de las Matemáticas: 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-88), (W 4: 299-309)
- Rabinovitch, Nachum L. (1970). "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 .
- Rashed, 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 .
- Rashed, R. (1994), "Inducción matemática: al-Karajī y al-Samawʾal", El desarrollo de las matemáticas árabes: entre aritmética y álgebra , Boston Studies in the Philosophy of Science, 156 , Springer Science & Business Media, ISBN 9780792325659
- Shields, Paul (1997). "Axiomatización de la aritmética de Peirce". En Houser; et al. (eds.). Estudios en la lógica de Charles S. Peirce .
- Simonson, Charles G. (invierno de 2000). "Las matemáticas de Levi ben Gershon, el Ralbag" (PDF) . Bekhol Derakhekha Daehu . Prensa Universitaria Bar-Ilan. 10 : 5-21.
- Unguru, S. (1991). "Matemáticas griegas e inducción matemática". Physis . XXVIII : 273-289.
- Unguru, S. (1994). "Aves de corral después de la inducción". Physis . XXXI : 267–272.
- Vacca, G. (1909). "Maurolycus, el primer descubridor del principio de inducción matemática" . Boletín de la American Mathematical Society . 16 (2): 70–73. doi : 10.1090 / S0002-9904-1909-01860-9 .
- 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 .