Principio de inducción

El principio de inducción (que no debe confundirse con el método de inducción) es una declaración sobre números naturales que en matemáticas encuentra Amplio uso en demostraciones, para demostrar que una cierta propiedad es válida para todos los enteros. La idea intuitiva en su base es el "efecto dominó" : Para que las fichas Dominó dispuestas a lo largo de una fila caigan, son suficientes las dos condiciones: el principio de inducción extiende esta idea al caso en el que la fila está compuesta de fichas infinitas.

El principio de inducción establece que si P {\displaystyle P} es una propiedad que se mantiene para el número 0, y si P ( y ) ⇒ P ( y + 1 ) {\displaystyle P (n)\Rightarrow P (N + 1)} para cada y {\displaystyle n} , entonces P ( y ) {\displaystyle P (n)} se aplica a cada y {\displaystyle n} . En símbolos: donde k {\displaystyle k} y y {\displaystyle n} son números naturales.

El primer testimonio específico del principio es de 1861, por Robert Grassmann. Su primer uso en una demostración se remonta a 1575 por el italiano Francesco Maurolico. En el siglo XVII, Pierre de Fermat refinó su uso formulándolo como el principio del descenso infinito, y la noción también aparece claramente en las obras posteriores de Blaise Pascal (1653). La expresión "inducción matemática" parece haber sido acuñada por el lógico y matemático A. de Morgan a principios del siglo XIX. Su formulación completa, todavía utilizada hoy en día, es esencialmente la dada por Giuseppe Peano en su Arithmetices Principia, publicado en 1889. El principio de inducción deriva directamente del quinto axioma de Peano, y es equivalente a él: suponiendo que es un axioma, el quinto axioma de Peano se deriva de él.

Para demostrar que una cierta afirmación P ( y ) {\displaystyle P (n)} donde aparece un número natural y {\displaystyle n} se aplica a cualquier y ∈ Y {\displaystyle n \ in \ mathbb {N} } el principio de inducción se puede explotar de la siguiente manera: U = { y ∈ Y : pena P ( y ) } {\displaystyle U = \{n \ in \ mathbb {N}: {\mbox{vale }}P (n)\}} , y por lo tanto se concluye que el conjunto U {\displaystyle U} de los números por los que vale la pena P ( y ) {\displaystyle P (n)} coincide con el conjunto de números naturales Una forma intuitiva de ver este tipo de demostración es la siguiente: si tenemos una demostración de la base y el tono inductivo, entonces claramente podemos aprovechar estas demostraciones para demostrar P ( 1 ) {\displaystyle P (1)} usando la regla lógica modus ponens en P ( 0 ) {\displaystyle P (0)} (la base) y P ( 0 ) ⇒ P ( 1 ) {\displaystyle P (0) \ Rightarrow P(1)} (que es un caso especial de paso inductivo para y = 0 {\displaystyle n = 0} ), entonces podemos probar P ( 2 ) {\displaystyle P (2)} porque ahora usamos el modus ponens en P ( 1 ) {\displaystyle P (1)} y P ( 1 ) ⇒ P ( 2 ) {\displaystyle P (1) \ Rightarrow P(2)} , así que para P ( 3 ) {\displaystyle P (3)} , P ( 4 ) {\displaystyle P (4)} , así sucesivamente El principio de inducción proporciona una herramienta importante para las demostraciones. El Paso 1 generalmente se llama base de inducción, Paso 2 Paso inductivo. está claro en este punto que podemos producir una demostración en un número finito de pasos (posiblemente muy largos) de P ( y ) {\displaystyle P (n)} para cualquier número natural y {\displaystyle n} , de la que deducimos que P ( y ) {\displaystyle P (n)} es verdad para todos y ∈ Y {\displaystyle n \ in \ mathbb {N} } . la prueba de esta declaración se vuelve más simple después de presionar que la adición de los primeros n + 1 enteros es igual a la adición de n+1 a la suma de los primeros n enteros, es decir, que: por lo que la prueba que estamos buscando se obtiene mediante la adición de n + 1 a P ( y ) {\displaystyle P (n)} y verificando que el resultado coincide con P ( y + 1 ) {\displaystyle P (n+1)} los pasos algebraicos son entonces: esto concluye la demostración del paso inductivo Vamos a demostrar que vale la pena la afirmación: para cada y ∈ Y + {\displaystyle n \ in \ mathbb {n} ^{+}} resulta: hemos definido en este caso P ( y ) = 1 + 2 + 3 + 4 + . . . + y = y ( y + 1 ) 2 {\displaystyle P (n)=1+2+3+4+. +n = {\frac {n (n + 1)} {2}}} . Por lo tanto, habiendo verificado la validez tanto de la base de inducción como del paso inductivo, podemos concluir que la fórmula es verdadera para cada y ∈ Y + {\displaystyle n \ in \ mathbb {n} ^{+}} .

El principio de inducción fuerte proviene de una versión con hipótesis aparentemente más restrictivas del quinto axioma de Peano, pero equivalente: si U {\displaystyle U} es un subconjunto del conjunto Y {\displaystyle \ mathbb {N} } de números naturales tales que entonces U = Y {\displaystyle u = \ mathbb {N} } la palabra "fuerte" está relacionada con el hecho de que esta formulación requiere suposiciones aparentemente más fuerte y más apretado para inferir que el conjunto U {\displaystyle U} partidos con Y {\displaystyle \ mathbb {N} } : para admitir un número como un todo se requiere que todos los anteriores ya sean parte de él (y no solo el número anterior) En la práctica, la propiedad P {\displaystyle {\mathcal {P}}} debe aplicarse no solo a n, sino a cada x ∈ Y : x & lt; y {\displaystyle x \ in \ mathbb {n}: x & lt; n} . No es difícil probar su equivalencia lógica con el principio de inducción, razonando así: si se aplica a 1 (o 0), también se aplica a su sucesor, y al sucesor de este último, etc. , hasta no. Además, si la propiedad se aplica a cada número menor que n, También se aplica a 1 (o 0), y si se aplica a b, también se aplica a B+1 ≤ n, y por lo tanto es equivalente al principio de inducción. Esta formulación, a veces, hace que sea más fácil de demostrar por inducción, dada la posibilidad de tener una audiencia más amplia de hipótesis (Todos números más pequeños de y {\displaystyle n} ) para la demostración del siguiente "paso inductivo" . Esto ocurre, por ejemplo, en la prueba de la fattorizzabilità de enteros (ver teorema fundamental de aritmética): donde, en la demostración, se utilizaría el principio de inducción, regresión, por una serie de factores puerta más pequeña al número anterior m, pero en números más pequeños. En ese caso, el principio de inducción débil no sería útil. La misma situación se encuentra en la factorización de polinomios.

En total, las formas del principio de inducción son 4: estas formas son equivalentes en el sentido de que suponiendo una verdadera puede probar las otras tres.

Generalmente, el principio de inducción se conoce como el axioma de los números naturales: a veces se considera en lugar del quinto axioma de Peano, obteniendo un modelo equivalente, ya que, como se mencionó anteriormente, los dos son equivalentes. La teoría obtenida al considerar los axiomas clásicos de Peano formalizados (es decir, los axiomas de la aritmética de Peano) excepto el principio de inducción se llama aritmética Robinson y admite modelos alternativos en los que el principio de inducción es falso. Sin embargo, hay algunos sistemas lógicos en los que se puede demostrar: por ejemplo, cuando se utiliza el axioma o también conocido como el principio de buen orden para los números naturales. De hecho, este axioma adicional es una formulación alternativa del principio de inducción matemática: los dos axiomas son de hecho equivalentes. De hecho, si un conjunto no vacío no tiene un mínimo, el 0 no le pertenece. Suponiendo entonces que los números menores que m números no le pertenecen, entonces m tampoco le pertenece (de lo contrario sería el mínimo. Aplicando una fuerte inducción se obtiene que ningún número le pertenece. Por el contrario, dado un conjunto disfruta de las dos propiedades enunciadas por el principio de inducción sin cubrir todo Y {\displaystyle \ mathbb {N} } . Si defino el conjunto Y {\displaystyle \ mathbb {N} } axiomáticamente (con axiomas de Peano) tendré que el principio de inducción es un axioma, como se dijo anteriormente, viceversa si defino el conjunto Y {\displaystyle \ mathbb {N} } como el conjunto inductivo más pequeño contenido en R {\displaystyle \mathbb {R} } , y más precisamente como la intersección de todos los conjuntos inductivos contenidos en R {\displaystyle \ mathbb {R} } , Voy a tener que el principio de inducción no puede ser considerado un axioma no ser el todo Y {\displaystyle \ mathbb {N} } defined axiomatically, but it will be a consequence of the fact that Y {\displaystyle \ mathbb {N} } es el conjunto inductivo más pequeño Existirá, para una buena clasificación, el menor número que no le pertenezca y que este sea m. entonces m no puede ser 0. Su m-1 anterior no respeta la hipótesis inductiva. Sin embargo, en algunos casos el principio de inducción no se considera axioma, esto depende de cómo se defina el conjunto de números naturales.

Una primera generalización muy básica es comenzar la inducción a partir de un número natural distinto de cero k. O: si queremos demostrar que una declaración P ( y ) {\displaystyle P (n)} se aplica a cada número natural y {\displaystyle n} mayor o igual a un número fijo k {\displaystyle k} aplicamos la técnica de demostración por inducción considerando como base de la inducción P ( k ) {\displaystyle P (k)} en su lugar P ( 0 ) {\displaystyle P (0)} . El principio de inducción transfinita generaliza el principio de inducción a la clase de ordinales transfinitas en (de los cuales los números naturales son un subconjunto). Afirma que si U {\displaystyle U} es un subconjunto de la clase O y {\displaystyle On} de todos los ordinales verifica las siguientes dos propiedades: entonces U {\displaystyle U} coincide con toda la clase de ordinales O y {\displaystyle On} . El principio de inducción transfinita, a diferencia del principio de inducción fuerte, es un principio estrictamente más poderoso que el principio de inducción, de hecho hay teoremas como el teorema de Goodstein que pueden ser probados por inducción transfinita pero no pueden ser probados por inducción simple.

Una aplicación errónea clásica del principio de inducción es la siguiente "demostración" que lleva a la conclusión de que razonamos por inducción sobre la magnitud de los posibles conjuntos de caballos: demostramos que para cada y ∈ Y {\displaystyle n \ in \ mathbb {N} } pena P ( y ) {\displaystyle P (n)} = "un conjunto de y {\displaystyle n} caballos contiene todos los caballos del mismo color" : Del principio de inducción se desprende que cualquiera que sea el número de caballos presentes en el mundo, todos tienen el mismo color La demostración del paso inductivo anterior es solo aparente: de hecho, para n = 1 los dos conjuntos de N elementos tienen en común N - 1 = 0 elementos y, por lo tanto, no se puede deducir que n +1 = 2 caballos tengan el mismo color.

Lógica matemática

Teoría de números

Función theta de Ramanujan

En matemáticas, la función Theta de Ramanujan generaliza la forma de las funciones Theta DE Jacobi, manteniendo sus propiedades generales. En particular, el tri...

Aritmética tipográfica

En matemáticas, la teoría tipográfica de números (at) es un sistema axiomático formal que describe los números naturales que aparece en el libro de Douglas Hofs...

Funciones matemáticas

Inteligencia artificial

Esta página se basa en el artículo de Wikipedia: Fuente, Autores, Licencia Creative Commons Reconocimiento-CompartirIgual.
This page is based on the Wikipedia article: Source, Authors, Creative Commons Attribution-ShareAlike License.
contactos
Política de privacidad , Descargos de responsabilidad