În matematică , raționamentul prin inducție (sau de inducție sau de inducție completă) este o formă de raționament pentru a demonstra o proprietate asupra tuturor celor numerele naturale . Raționamentul prin inducție constă în demonstrarea următoarelor puncte:
Odată stabilit acest lucru, concluzionăm că această proprietate este adevărată pentru toate numerele naturale mai mari sau egale cu n 0 .
Raționamentul prin inducție stabilește o proprietate importantă a numerelor întregi naturale: aceea de a fi construit dintr-un număr întreg n 0 prin iterarea pasajului către succesor. Într-o prezentare axiomatică a numerelor naturale, este formalizată direct de o axiomă. Cu anumite proprietăți ale numerelor întregi naturale, este echivalent cu alte proprietăți ale acestora, în special existența unui minim față de orice set non-gol ( ordine bună ), care, prin urmare, permite o axiomatizare alternativă pe baza acestei proprietăți.
Anumite forme ale acestui raționament sunt, de altfel, generalizate în mod natural la toate ordinele infinite bune (nu numai la cele întregi naturale), vorbim apoi despre recurența transfinită sau despre recurența ordinală (orice ordine bună este izomorfă pentru un ordinal ); termenul inducție este, de asemenea, adesea folosit în acest context. Raționamentul prin inducție poate fi în cele din urmă generalizat la relații întemeiate . În anumite contexte, în logica matematică sau în informatică , pentru structuri de natură arborescentă sau referitoare la termenii limbajului formal de bază, vorbim de recurență sau inducție structurală .
Vorbim în mod obișnuit de recurență într-un context legat, dar diferit, cel al definițiilor prin recurența secvențelor (sau operațiilor) cu argumente întregi. Dacă unicitatea unor astfel de apartamente este demonstrată în mod clar prin recurență, existența lor, care este adesea admisă tacit în școala secundară sau chiar în primii ani de universitate, se bazează pe un principiu diferit.
Istoria începuturilor raționamentului prin inducție poate fi deschisă interpretării, în funcție de ceea ce acceptăm să identificăm ca atare. Dacă privim lucrurile de la distanță, putem spune, ca Jean Itard în 1961 cu privire la Elementele lui Euclid : „Nu vom găsi niciodată motivul modern un pic pedant:„ Am verificat proprietatea pentru 2, am a arătat că, dacă este adevărat pentru un număr, este adevărat pentru următorul său, de aceea este general ”și cei care văd inducția completă doar însoțită de refrenul său vor avea dreptul să spună că nu este găsită. . Pentru noi, o vedem în recuzită. 3, 27 și 36, VII, 2, 4 și 13 VIII, 8 și 9 IX. „ Acest punct de vedere nu este în mod necesar împărtășit de alți istorici.
Găsim în Tratatul triunghiului aritmetic al lui Blaise Pascal , scris în 1654, dar publicat în 1665, ceea ce este în general considerat ca prima utilizare destul de explicită a raționamentului prin inducție. În special, chiar dacă Pascal folosește uneori forme mai puțin complete în tratatul său, el scrie acest lucru:
„Deși această propunere are o infinitate de cazuri, voi da o dovadă foarte scurtă, presupunând două leme.
Primul, care este evident de la sine, că această proporție se găsește în a doua bază; deoarece este clar vizibil, că φ este la σ ca 1 este la 1.
Al doilea, că dacă această proporție se găsește în orice bază, va fi găsită în mod necesar în următoarea bază.
De unde se vede că este neapărat în toate bazele: pentru că se află în a doua bază de prima lemă; de aceea până la a doua se află în a treia bază, deci în a patra și până la infinit. "
De asemenea , în al XVII - lea secol, noi trebuie să menționăm Pierre de Fermat și Jacques Bernoulli care critică atât „metoda de inducție“ de John Wallis , deoarece numit de inducție incompletă, ceea ce corespunde aproximativ la o demonstrație pentru primul număr întreg și „așa mai departe“. Fermat promovează, de asemenea, metoda descendenței infinite , ea însăși legată de recurență (vezi mai jos). El este primul care îl identifică și îl numește, dar este deja folosit, acolo, fără nicio ambiguitate, de către Euclid . Bernoulli , la rândul său, propune să demonstreze trecerea de la n la n + 1, adică raționamentul exact prin inducție.
În timpul XVIII - lea și al XIX - lea secol, raționamentul prin recurență este utilizat din ce în ce în cele din urmă conducând la formalizarea și axiomatizarea sale, în primul rând parțial de Grassmann , în 1861, apoi de Richard Dedekind în 1888 și , în mod independent de către Giuseppe Peano în 1889. Pentru Dedekind, aceasta este o chestiune de completare a aritmetizării realelor, prin furnizarea unui cadru formal care să permită dezvoltarea metodei tăieturilor publicată în 1872. Pentru Peano, acestea sunt premisele proiectului său foarte ambițios de a formaliza realii. matematică (vezi formularul de matematică ). În ambele cazuri, recurența nu mai este pur și simplu un principiu de dovadă bazat pe intuiție, ci o axiomă care formalizează o proprietate a numerelor naturale.
Indiferent dacă Pascal a fost sau nu inventatorul raționamentului prin inducție, nu putem neglija numeroșii săi precursori.
Lucrurile se complică prin lipsa unui limbaj algebric modern. Unele rezultate nu pot fi uneori nici măcar enunțate în generalitate și, prin urmare, sunt pentru numere întregi date, în timp ce ideile esențiale pentru demonstrarea rezultatului general (trecerea de la n la n + 1) sunt prezente.
Florian Cajori (1918) îl detectează în metoda chakravala a lui Bhaskara II și în demonstrația lui Euclid a existenței unei infinități de numere prime .
Mai multe forme de raționament recurent au fost descoperite încă din anii 1970 în matematica lumii arabo-islamice, vezi Rashed (1972). Astfel, în jurul anului 1000, persanul Al- Karaji (953-1029) a stabilit formula binomului lui Newton (de fapt, el nu avea notațiile care să-i permită să o afirme în cazul general, dar metodele funcționează pentru un întreg arbitrar). El calculează, de asemenea, suma cuburilor primelor n numere întregi naturale, al-Samaw'al își continuă activitatea. Aceste rezultate folosesc într-adevăr forme „arhaice” de definiție și raționament prin inducție (cum ar fi regresia, plecăm de la un întreg dat ales în mod arbitrar și, printr-un proces evident general, trecând de la n la n - 1, revenim la în caz inițial). În același timp, Ibn al-Haytham (953-1039) a folosit raționamentul de inducție pentru a calcula suma cuburilor și apoi a patra putere a primelor n numere întregi naturale. Deși nici măcar nu menționează posibilitatea de a trece dincolo de puterea a 4-a, metoda sa, iterativă, ar permite-o.
În timpul evului mediu european, filosoful și matematicianul evreu din Languedoc, Levi ben Gershom (1288-1344), cunoscut sub numele de Gersonide , a folosit sistematic regresia pentru a stabili rezultate combinatorii (suma cuburilor, numărul de permutări etc.).
Pascal, sau Bernoulli au fost deja luate în considerare în XIX - lea secol ca părinții inductiei matematice, dar apoi, o mare parte a fost citat în prima jumătate a XX - lea secol italian matematician Francesco Maurolico (1494-1575) și lucrarea lui Arithmeticorum libri duo (1575), în urma unui articol al lui Giovanni Vacca din 1909, care a influențat Moritz Cantor și a fost tradus în alte limbi, de exemplu în franceză în 1911. Pentru a demonstra că suma primelor n numere întregi impare este un pătrat perfect, Maurolico folosește o propoziție, care este trecerea de la cazul n la cazul n + 1 (dar aceasta nu este menționată ca o lemă, având în vedere propoziția anterioară). Pe de altă parte, din corespondența lui Pascal reiese că a citit Maurolico. Cu toate acestea, un articol al lui Hans Freudenthal (1953) arată că Maurolico folosește foarte puțin raționamentul de tip recurență în cartea sa (sub orice formă) și, pe de altă parte, descoperirile lucrărilor anterioare ale lui Al-Karaji, ben Gershom și alții relativizează contribuția sa, până la punctul în care lucrările generale despre istoria matematicii nu o mai menționează.
Pentru a demonstra o proprietate referitoare la toate numerele naturale, cum ar fi formula binomială a lui Newton , putem folosi raționamentul de inducție. Să notăm proprietatea în cauză P ( n ) pentru a indica dependența de numărul întreg n . O putem obține apoi pentru orice număr întreg n dovedind aceste două afirmații:
Spunem apoi că proprietatea P este dedusă prin inducție pentru orice număr întreg n . Uneori specificăm „recurență simplă”, atunci când este necesar să distingem acest raționament de alte forme de recurență (vezi mai jos).
O modalitate ușoară de a vizualiza raționamentul recurenței este de a face analogia cu jocul de domino care se încadrează. Considerăm o serie infinită de domino, fiecare dintre ele având un număr (0,1,2,3, ...) și căutăm condiții simple, astfel încât să cadă toate domino-urile. Oricine a jucat deja acest joc va înțelege că, pentru căderea tuturor domino-urilor, este suficient ca primul domino (cel numerotat 0) să cadă și că căderea domino n cauzează căderea domino n + 1. Dacă notăm apoi cu P ( n ) proprietatea "domino n cade", atunci căderea domino 0 corespunde inițializării menționate mai sus și faptul că căderea domino n provoacă căderea domino n + 1 corespunde eredității de mai sus.
Raționamentul prin inducție este o proprietate fundamentală a numerelor naturale și este principala axiomelor lui Peano . O axiomatică este, într-un fel, o definiție implicită, în acest caz o definiție implicită a numerelor naturale. În anumite contexte, ca și în teoria mulțimilor , deducem direct recurența definiției, explicită de data aceasta, a setului de numere întregi naturale.
Recurența poate fi, de asemenea, exprimată într-un mod stabilit: este doar o variație a definiției unui set în înțelegere . Asociem cu o proprietate P mulțimea E de numere întregi naturale care o satisfac, iar cu un set de numere întregi naturale E proprietatea de membru asociată. Recurența este apoi reafirmată într-un mod echivalent după cum urmează:
Fie E un subset de N , dacă:
Apoi , E = N .
Desigur, inițializarea poate începe de la un întreg arbitrar k și în acest caz proprietatea este dovedită adevărată doar din rangul k :
Da :
Atunci pentru orice număr întreg n mai mare sau egal cu k , P ( n ).
Această recurență de la k este o consecință imediată a recurenței de la 0: este suficient să se demonstreze " n < k sau P ( n )", sau chiar " P ( n + k )" dacă cineva are l 'adunare, prin inducție pe n ; fiecare dintre aceste proprietăți este adevărată pentru orice număr întreg n dacă și numai dacă proprietatea P este adevărată pentru orice număr întreg mai mare sau egal cu k .
În mod analog, vom avea alte raționamente prin inducție, fără a fi nevoie să prezentăm de fiecare dată un nou principiu, de exemplu, o recurență pe numere întregi (luăm P (2 n )) etc.
Numere întregi impare sunt numere întregi de forma 2 n + 1 (primul, obținut pentru n = 0, este 1). Deducem dintr - o identitate remarcabilă bine cunoscută că 2 n + 1 adăugat la pătratul lui n dă pătratul următorului număr: n 2 + 2 n + 1 = ( n + 1) 2 Prin urmare, vom arăta prin inducție că suma primelor n numere întregi impare este egală cu pătratul lui n : 1 + 3 + ... + (2 n - 1) = n 2 . Deși scrierea anterioară poate implica că 2 n - 1> 3, nu o vom presupune. Suma este gol , prin urmare , zero , în cazul în care n = 0, redus la 1 dacă n = 1, egal cu 1 + 3 în cazul în care n = 2, etc.
Dacă luăm, de exemplu, secvența , putem observa că această secvență crește de la n = 2 char . Dacă încercăm să arătăm asta pentru orice : inițializarea este ușor de dovedit deoarece ; ereditate și pentru că, secvența fiind în creștere, dacă atunci . Cu toate acestea, această inegalitate este adevărată numai pentru n = 1. Ereditatea a fost de fapt dovedită doar pentru n mai mare sau egal cu 2 și nu pentru n mai mare sau egal cu 1.
Mai multe forme de recurență, aparent mai generale decât recurența obișnuită, se dovedesc a fi echivalente.
Se poate întâmpla ca, pentru ereditate, atunci când vine vorba de a demonstra P ( n + 1), să avem nevoie de asumarea proprietății la cele două rânduri precedente, adică nu numai pentru n , ci și pentru n - 1. Suntem a condus la utilizarea următorului principiu de inducție:
Fie P ( n ) o proprietate definită pe N , dacă:
atunci P ( n ) pentru orice n ∈ N .
Această proprietate este aparent mai puternică decât recurența simplă, deoarece avem la dispoziție o ipoteză suplimentară, dar este de fapt echivalentă cu aceasta, deoarece aceasta echivalează cu demonstrarea [ P ( n ) și P ( n + 1)] prin recurență simplă. Exemple de aplicare a acestui principiu de recurență pot fi găsite în articolul secvența Fibonacci, de exemplu.
Recurența anterioară poate fi generalizată la mai multe ipoteze, 3, 4 etc. Dar toate aceste principii apar ca cazuri speciale ale următorului principiu de recurență, numit uneori recurență puternică , care face posibilă demonstrarea proprietății la rangul următor, presupunerea că este adevărată pentru toate rangurile inferioare (din acest motiv, această formă de recurență se mai numește recurență cumulativă ). Avem o versiune mai puternică a eredității:
Fie P ( n ) o proprietate definită pe N , dacă:
atunci P ( n ) pentru orice întreg n ∈ N .
Inițializarea rămâne aceeași, dar moștenirea este modificată. Pentru a demonstra proprietatea la rangul n + 1, putem presupune că proprietatea este adevărată nu numai pentru n, ci și pentru toate numerele întregi mai mici decât n .
Din nou, această proprietate, aparent mai puternică decât simpla recurență, este de fapt echivalentă cu ea. Într-adevăr, aceasta echivalează cu demonstrarea prin simplă inducție a proprietății „∀ k ≤ n P ( k )”, adică a proprietății P pentru toate numerele întregi mai mici sau egale cu n . Folosim pentru echivalență proprietățile care caracterizează ordinea pe N , și anume aceea pentru tot numărul natural k : k ≤ n + 1 ⇔ ( k ≤ n sau k = n + 1) k ≤ 0 ⇔ k = 0. Această recurență poate trece de la un anumit rang, la fel ca recurența simplă.
Exemplu de utilizarePentru a demonstra că orice număr natural mai mare sau egal cu 2 are un divizor prim (deci recurența de la rangul 2).
sau altfel n + 1 este prim atunci are un divizor prim care este el însuși sau altfel n + 1 este compus și există un număr întreg d mai mare sau egal cu 2 și mai mic sau egal cu n care împarte n + 1. Apoi, prin ipoteza inducției, d are un divizor prim, care este, de asemenea, un divizor al n + 1. Raționamentul care se face pentru n + 1 funcționează la fel de bine pentru 2: vedem din exemplu că nu este cu adevărat necesar să tratăm inițializarea separat, adică această demonstrație se face mai elegant prin recidivă bine întemeiată sau prin utilizarea principiului bunei ordini (vezi mai jos).
Ca alternativă la recurență, în special recurență puternică, putem folosi următorul principiu: Fiecare subgrup non-vid al lui N are un element mai mic ( N este bine ordonat ). De exemplu, dacă luăm exemplul tratat în paragraful anterior, existența pentru orice număr al unui divizor prim, alegem direct p cel mai mic divizor diferit de 1 dintr-un număr dat n mai mare sau egal cu 2, care este cel mai mic element al setului nevid de divizori, altul decât 1 din n . Arătăm apoi prin absurd că p este prim: dacă p ar avea un divizor strict mai mic decât p și diferit de 1, s-ar împărți și n , iar p nu ar fi cel mai mic divizor al lui n .
Această proprietate este o proprietate a relației ordine pe N . O astfel de ordine se numește ordine bună și spunem că N este bine ordonat.
Proprietatea de recurență este dedusă din cea de bună ordine și din faptul că orice număr întreg este fie 0, fie un succesor ( de forma n + 1).
Într-adevăr, pentru o proprietate ereditară P ( P ( n ) ⇒ P ( n + 1)) și verificată la 0, este suficient să se ia în considerare minimul setului de numere întregi care nu o satisfac. Există de îndată ce acest set nu este gol. Datorită inițializării, știm că acest minim nu este 0. Prin moștenire, știm că acest minim nu este succesorul n + 1 de către un număr întreg n , care să verifice proprietatea P . Prin urmare, setul de numere întregi care nu îndeplinesc P nu are nici un minim, deci este gol: verifică întregi P .
Reciproc, proprietatea bunei ordini este dedusă din proprietatea recurenței (și din proprietățile ordinului) . Contrapoziția proprietății de bună ordine este de fapt dedusă direct din recurența puternică (prin utilizarea proprietăților care caracterizează ordinea pe N ). Presupunem că o mulțime E de numere întregi, n nu are cel mai mic element și trebuie să arătăm că E este gol, adică pentru întregul întreg n , n ∉ E:
Odată ce anumite proprietăți ale numerelor întregi naturale au fost admise (în special faptul că orice număr întreg este 0 sau succesorul unui alt număr întreg), avem deci o echivalență între principiul recurenței și proprietatea bunei ordine.
Un alt principiu apropiat de recurență, în special recurența puternică, este principiul descendenței infinite ilustrat de Pierre de Fermat : nu există o secvență infinită strict descrescătoare de numere naturale. Fermat demonstrează astfel în mod absurd rezultatele inexistenței soluțiilor la anumite ecuații diofantine , construind dintr-o presupusă soluție o altă soluție strict mai mică.
Este o consecință directă a proprietății bunei ordini , dacă ar exista o astfel de succesiune, setul ne-gol al valorilor sale nu ar avea niciun minim. Principiul descendenței infinite este direct legat de noțiunea de relație bine întemeiată , abordată în paragraful următor, despre care oferă o caracterizare.
Putem redistribui recurența puternică folosind relația de ordine unică, iar cele două ipoteze de recurență pot fi apoi combinate într-una singură.
Fie P ( n ) o proprietate definită pe N , dacă [∀ k < n P ( k )] ⇒ P ( n ) (pentru toate n ∈ N ) atunci P ( n ) pentru orice n ∈ N .
În cazul în care n = 0, ipoteza este adevărată prin golul setului de k < 0 , deci cuantificarea este adevărată și afirmația revine la P ( 0 ). Deci, atunci când luăm pentru <ordinea naturală a numerelor întregi, distingem dacă n = 0 sau n este un „succesor”, adică n este de forma m + 1, găsim exact proprietatea recurenței puternice .
Această formă de raționament prin inducție nu se mai referă la constanta 0 și operația succesivă a numerelor întregi. Se generalizează direct la orice ordine bine întemeiată, care nu este neapărat totală (și chiar la orice relație bine întemeiată ).
Într-adevăr, a spune că relația de ordine strictă pe N este bine întemeiată înseamnă că orice parte neocupată din N are un element minim (deci minim aici , deoarece ordinea pentru N este totală), totuși se demonstrează cu ușurință ( cf. articol detaliat) că această proprietate este echivalentă cu o recidivă bine fundamentată. Dovada este, de fapt, în esență cea dată mai sus între recurență și bună ordine prin recurență puternică. Dar, deoarece există ordine bune care nu sunt izomorfe pentru ordinea obișnuită pe N , am folosit în mod necesar în trecerea unei proprietăți specifice a numerelor întregi, în acest caz faptul că orice număr întreg diferit de zero este succesorul unui alt întreg. Această ultimă proprietate este, în plus, o consecință a proprietății simple de recurență (cazul foarte particular în care nu se folosește ipoteza recurenței). Nu este neapărat adevărat în mulțimi bine ordonate.
În broșura sa despre funcția gamma , Emil Artin folosește, pentru a extinde inegalitatea convexității pentru mass-media la toate centrele izobari , un principiu de inducție care se potrivește bine cazului în care proprietatea este ușor demonstrată pentru puterile lui 2. Acest principiu a avut deja folosit de Cauchy pentru a demonstra inegalitatea aritmetico-geometrică . Afirmația sa este următoarea:
Fie P ( n ) o proprietate definită pe N :
apoi, pentru orice număr întreg n ∈ N , P ( n ).
Originalitatea acestei metode se bazează pe un principiu de inducție înapoi : nu mai dovedim o proprietate de la n la n + 1 ci de la n + 1 la n , adăugând doar dacă proprietatea este adevărată pentru un număr întreg, atunci este adevărat pentru un alt număr întreg strict mai mare, care oferă o dovadă de proprietate asupra tuturor numerelor întregi „în zigzag”.
Raționamentul prin inducție generalizează în mod firesc, sub forma recidivei bine întemeiate indicate în paragraful recidivei bine întemeiat , la seturi pe care putem defini o ordine bună , izomorfă la ordinală sau pur și simplu o relație bine întemeiată .
Textul lui Blaise Pascal citat mai sus, primul text în care raționamentul prin recurență apare destul de explicit, oferă o justificare intuitivă foarte naturală: faptul că face posibilă construirea unei demonstrații directe pentru orice ceea ce un întreg, o justificare folosit astăzi. Cu toate acestea, această justificare nu poate constitui o demonstrație a validității principiului recurenței. Pentru a demonstra P ( n ) pentru orice număr întreg n , ar trebui să scriem toate implicațiile dintre P ( n ) și P ( n + 1) din P (0) și asta ar necesita o infinitate de implicații. Deoarece o dovadă este finită, o astfel de dovadă va fi, prin urmare, valabilă doar pentru un număr întreg n fixat în avans. Cele două ipoteze ale principiului inducției ne permit teoretic să scriem „mecanic” o dovadă pentru un întreg arbitrar mare, dar nu pentru toate numerele întregi.
Prin urmare, principiul recurenței este o proprietate a numerelor întregi naturale, admisă ca axiomă (Dedekind 1888), sau altfel demonstrată în cadrul unei teorii mai puternice precum teoria mulțimilor . Apoi face posibilă „adunarea” sub forma unei demonstrații finite, această infinitate de demonstrații, una pentru fiecare număr întreg.
Cu toate acestea, axiomatizarea a captat pe deplin intuiția? Deducem foarte direct din teoremele de incompletitudine ale lui Gödel (1931) că nu. Într-adevăr, pentru orice axiomatizare rezonabilă , de exemplu teoria mulțimilor ZFC , fiecare dintre aceste două teoreme oferă o proprietate P a numerelor întregi care este exprimată în limbajul teoriei și care poate fi demonstrată pentru orice număr întreg fixat pentru a avansa, dar totuși noi nu poate dovedi afirmația (formalizată în teorie) „pentru toate numerele întregi naturale P ( n )”, prin inducție sau orice alt mijloc disponibil prin axiomatizare.
Astfel, ipotezele P (0) și P ereditare: ∀ n [ P ( n ) ⇒ P ( n + 1)] ne permit să arătăm că, pentru orice număr întreg n , avem (unde simbolul indică faptul că există un demonstrarea propoziției enunțate). Dar numai aceste presupuneri nu fac posibilă afirmarea , ceea ce este mult mai puternic. Principiul recurenței îl permite.
Într-adevăr, putem avea o teorie coerentă T , cum ar fi:
Fără a avea însă:
Acest lucru poate fi conceput cu ușurință printr-un exemplu: în prezent nu se știe dacă conjectura Goldbach care spune că orice număr întreg> 2 este suma a 2 numere prime este o afirmație:
Dacă acesta este cazul, luând pentru P ( n ), „2 n + 4 este suma a 2 numere prime”, am avea, pentru orice număr întreg n :
Dar nu :
Putem avea chiar o teorie coerentă T , cum ar fi:
Se spune că o astfel de teorie este pur și simplu coerentă și ω-incoerentă (citiți omega-incoerentă ).
Acest lucru este întotdeauna ușor de înțeles luând exemplul de mai sus:
și înlocuind în paragraful anterior T cu , avem rezultatul scontat.
Astfel, nu este suficient să se demonstreze că pentru toate n , P ( n ) [adică P (0), P (1), P (2), ...] pentru a demonstra ∀ n P ( n ), așa cum se întâmplă, principiul recurenței.
O teorie în care pentru orice predicat P , pentru toate n , implică se spune că este ω-consistent.
Câteva dintre articolele istorice specializate (Acerbi, Rashed ...) încep cu o imagine de ansamblu mai generală.