miniatura|Es pot il·lustrar informalment la inducció matemàtica fent referència a l'efecte seqüencial de la caiguda de fitxes de dòmino.Matt DeVos, Mathematical Induction, Simon Fraser UniversityGerardo con Diaz, Mathematical Induction , Harvard University La demostració per inducció en matemàtica és un tipus de demostració que s'aplica quan un cas base és provat i una regla d'inducció és usada per provar una sèrie d'altres casos que normalment és infinita. L'any 1575 Francesco Maurolico va fer la primera demostració per inducció al seu treball Arithmeticorum libri duo. En una forma general mostra que les formes que poden ser avaluades són equivalents en el que es coneix com a inducció estructural. La Demostració per inducció és una regla d'inferència usada en proves formals, que són exemples de raonament deductiu.
Història Segons David E. Joyce, no hi ha proves de l'ús del principi d'inducció matemàtica en els escrits d'Euclides. Fabio Acerbi, l'any 2000, argumenta que el Parmènides de Plató (c. 370 aC) conté traces d'una demostració inductiva implícita primerenca. Aquesta interpretació ha estat qüestionada per Negrepontis i Farmaki el 2021, que afirmen a més que ni Plató ni cap dels altres pitagòrics van utilitzar el principi d'inducció matemàtica.
La primera demostració implícita per inducció matemàtica va ser escrita per al-Karaji al voltant de l'any 1000 dC, que la va aplicar a seqüències aritmètiques per demostrar el teorema del binomi i les propietats del triangle de Pascal. Tot i que l'obra original es va perdre, Al-Samawal al-Maghribi la va esmentar més tard al seu tractat al-Bahir fi'l-jabr (El Brillant en Àlgebra) cap al 1150 dC.
Katz diu a la seva història de les matemàtiques:
L'argument d'Al-Karají inclou en essència els dos components bàsics d'un argument modern per inducció, és a dir, la veritat de l'afirmació per a n = 1 (1 = 13) i la derivació de la veritat per a n = k a partir de la de n = k − 1. Per descomptat, aquest segon component no és explícit, ja que, en cert sentit, l'argument d'al-Karají és l'invers; és a dir, comença des de n = 10 i baixa fins a 1 en lloc de continuar cap amunt. No obstant això, el seu argument a al-Fakhri és la prova existent més antiga del la fórmula de suma per a cubs integrals.Katz (1998), p. 255
A l'Índia, les primeres demostracions implícites per inducció matemàtica apareixen al mètode cíclic de Bhaskara.
Un altre cas similar (contràriament al que ha escrit Vacca, com va mostrar acuradament Freudenthal) va ser el de Francesco Maurolico al seu Arithmeticorum libri duo (1575), que va utilitzar la tècnica per demostrar que la suma dels primers enters imparells .
El primer ús rigorós de la inducció va ser per Guersònides (1288–1344). La primera formulació explícita del principi d'inducció la va donar Pascal al seu Traité du triangle arithmétique (1665). Un altre francès, Fermat, va fer un ús ampli d'un principi relacionat: la demostració indirecta per descens infinit.
La hipòtesi de la inducció també va ser emprada pel suís Jakob Bernoulli, i a partir de llavors va esdevenir ben coneguda. El tractament formal modern del principi va arribar només al , amb George Boole, Augustus De Morgan, Charles Sanders Peirce, Giuseppe Peano i Richard Dedekind.
Descripció La forma més simple i comuna d'inducció matemàtica infereix que una afirmació que implica un nombre natural (és a dir, un enter o 1) es compleix per a tots els valors de . La demostració consta de dos passos:
El cas inicial): demostrar que l'afirmació es compleix per a 0 o 1.
El pas inductiu, o cas de pas): demostra que per a cada , si l'afirmació es compleix per a , aleshores es compleix per a . En altres paraules, suposem que l'afirmació es compleix per a algun nombre natural arbitrari i demostrem que l'afirmació es compleix per a .
La hipòtesi en el pas d'inducció, que l'afirmació es compleix per a una particular, s'anomena hipòtesi d'inducció o hipòtesi inductiva. Per demostrar el pas d'inducció, s'assumeix la hipòtesi d'inducció per a i després s'utilitza aquesta suposició per demostrar que l'afirmació es compleix per a .
Els autors que prefereixen definir els nombres naturals començant per 0 utilitzen aquest valor en el cas base; els que defineixen els nombres naturals començant per 1 utilitzen aquest valor.
Aleshores es pot demostrar que la inducció, donats els axiomes esmentats anteriorment, implica el principi de bon ordenament. La demostració següent utilitza la inducció completa i el primer i quart axiomes.
Exemple Suposem que volem demostrar la relació (fórmula de la suma dels n primers nombres naturals) :
per a tots els nombres naturals n.
Demostració Primerament comprovem si és veritat per n = 1. Clarament, la suma dels dos primers nombres és igual a 1*(1 + 1) / 2 = 1, com preveu la fórmula. Per tant, l'expressió és certa per a n = 1.
Ara cal provar si el fet que la fórmula es verifiqui quan n = m implica que també ho farà quan n = m + 1. Es pot fer de la manera següent:
Assumim que la fórmula és certa quan n = m,
Afegim m + 1 a les dues bandes i es té
Per manipulació algebraica obtenim
Així, resulta
Aquesta és la fórmula per a n = m + 1. No ha estat provat que sigui certa i hem d'assumir que P(m) és veritat i d'això derivar que P(m + 1). Simbòlicament s'ha demostrat que
Per tant, es pot concloure per inducció que la relació P(n) es compleix per a tots els nombres naturals n.
Inducció transfinita Una variant del principi d'inducció completa es pot generalitzar per a enunciats sobre elements de qualsevol conjunt ben fundat, és a dir, un conjunt amb una relació < (irreflexiva) que no conté cap cadena descendent infinita. Tot conjunt que representa un nombre ordinal és ben fundat; el conjunt dels nombres naturals n'és un exemple.
Aplicada a un conjunt ben fundat, la inducció transfinita es pot formular en un sol pas. Per demostrar que un enunciat és cert per a cada nombre ordinal: Cal demostrar, per a cada nombre ordinal , que si és cert per a tots els , aleshores també és cert.
Aquesta forma d'inducció, quan s'aplica a un conjunt de nombres ordinals (que formen una classe ben ordenada i, per tant, ben fundada), s'anomena inducció transfinita. És una tècnica de demostració important en teoria de conjunts, topologia i altres camps.
Les demostracions per inducció transfinita solen distingir tres casos: quan és un element minimal, és a dir, no hi ha cap element més petit que ; quan té un predecessor immediat, és a dir, el conjunt d'elements més petits que té un element màxim; quan no té predecessor immediat, és a dir, és un anomenat ordinal límit.
Estrictament parlant, en la inducció transfinita no cal demostrar un cas base, perquè és un cas particular vacu de la proposició que diu que si és cert per a tots els , aleshores és cert per a . És vacuament cert precisament perquè no hi ha valors de que puguin servir de contraexemple. Per tant, els casos particulars són casos particulars del cas general.
Relació amb el principi del bon ordre El principi de la inducció matemàtica s'acostuma a enunciar com un axioma dels nombres naturals; vegeu els axiomes de Peano. És estrictament més fort que el principi de bon ordre en el context dels altres axiomes de Peano. Suposem el següent:
L'axioma de la tricotomia: Per a qualsevol nombre natural i , és menor o igual que si i només si no és menor que .
Per a qualsevol nombre natural , és més gran .
Per a qualsevol nombre natural , no hi ha cap nombre natural i .
Cap nombre natural és menor que zero.
Prova. Suposem que existeix un conjunt no buit, , de nombres naturals que no té cap element mínim. Sigui l'asserció que no és a Aleshores és certa, ja que si fos falsa, 0 és el mínim element de A més, sigui un nombre natural, i suposem que és certa per a tots els nombres naturals menors que . Aleshores, si és fals és a , per tant, sent un element mínim a , una contradicció. Així, és cert. Per tant, pel principi d'inducció completa, es compleix per a tots els nombres naturals ; per tant, és buit, una contradicció.
QED
miniatura|600x600px|Recta numèrica per al conjunt D'altra banda, el conjunt , que es mostra a la imatge, està ben ordenada per ordre lexicogràfic. A més, excepte l'axioma d'inducció, satisfà tots els axiomes de Peano, on la constant 0 de Peano s'interpreta com el parell (0, 0), i la funció successora de Peano es defineix en parells per per a tots i . Com a exemple de violació de l'axioma d'inducció, definiu el predicat com a o per a algun i . Aleshores, el cas base és trivialment certa, i també ho és el pas d'inducció: si , aleshores . Tanmateix, no és certa per a tots els parells del conjunt, ja que és falsa.
Els axiomes de Peano amb el principi d'inducció modelen de manera única els nombres naturals. Substituir el principi d'inducció pel principi de bon ordre permet models més exòtics que compleixen tots els axiomes.
En diversos llibres i fonts s'ha publicat per error que el principi del bon ordre és equivalent a l'axioma d'inducció. En el context dels altres axiomes de Peano, aquest no és el cas, però en el context d'altres axiomes, són equivalents; concretament, el principi de bon ordre implica l'axioma d'inducció en el context dels dos primers axiomes enumerats anteriorment i
Tot nombre natural és o bé 0 o bé per a algun nombre natural .
Un error comú en moltes demostracions errònies és suposar que és un nombre natural únic i ben definit, una propietat que no està implícita en els altres axiomes de Peano.
Referències
Bibliografia . (Ch. 8.)
. (Section 1.2.1: Mathematical Induction, pp. 11–21.) . (Section 3.8: Transfinite induction, pp. 28–29.)
Vegeu també Axiomes de Peano Raonament inductiu
Categoria:Lògica matemàtica