Dette er en fremragende artikel som er værd at læse.

Komplet induktion

fra Wikipedia, den gratis encyklopædi
Spring til navigation Spring til søgning

Komplet induktion er en matematisk bevismetode, der beviser et forslag til alle naturlige tal, der er større end eller lig med en bestemt startværdi. Da der er uendeligt mange tal, kan der ikke foretages en afledning for hvert tal individuelt.

Bevis for, at erklæringen for alle ( normalt 1 eller 0), udføres det derfor i to faser:

  1. I begyndelsen af ​​induktion bliver udsagnet for et mindste antal afledt.
  2. Induktionstrinnet bruges til evt erklæringen fra erklæringen afledt.

Eller for at sige det mindre "matematisk":

  1. Induktionsstart : Det er bevist, at udsagnet gælder for det mindste tal, startværdien.
  2. Induktionstrin : Følgende er bevist: Hvis sætningen gælder et hvilket som helst tal, gælder det også for nummer et større.

Baseret på beviset for startværdien gør induktionstrinnet beviset for alle naturlige tal over startværdien.

Denne bevisprocedure er af grundlæggende betydning for regning og sætteori og dermed for alle matematikområder.

Erklæringsformer

Komplet induktion omhandler gyldigheden af ​​forslagsformularer .

Eksempel (se den gaussiske empiriske formel ):

til

Hvis du har værdier for starter, får du udsagn, der er sande eller falske.

Det er klart, at udsagnene i eksemplet ovenfor er alle sande. Da man ikke kan genberegne dette for alle (uendeligt mange) tal, kræves en særlig bevisprocedure. Dette giver hele induktionen.

Erklæringens form er universel, hvis den gælder for alle sandt er.

Til den generelle gyldighed af erklæringens form For at bevise det viser man følgende:

  1. (Start af induktion) og
  2. fra erklæringen (induktionsforudsætningen) udsagnet følger altid , Og det for alle . (Dette er induktionstrinnet.) [1]

illustration

Komplet induktion som en dominoeffekt med et uendeligt antal sten

Metoden til komplet induktion kan sammenlignes med dominoeffekten : hvis den første domino falder, og den næste vælter af hver faldende domino, vil hver domino i kæden, der menes at være uendelig lang, til sidst vælte.

Den generelle gyldighed af en form for erklæring er for bevist hvis er gyldig (den første sten vælter) og hvis den også gælder til (hver sten trækker den næste sten med sig, når den falder).

Etymologi og historie

Begrebet induktion stammer fra det latinske inductio , bogstaveligt talt "introduktion". Tilføjelsen fuldstændig signalerer, at dette i modsætning til filosofisk induktion , der udleder en generel lov fra særlige sager og ikke er en nøjagtig endelig procedure, er en anerkendt deduktiv bevisprocedure .

Ligger princippet induktion latent allerede i af Euclid traditionelle Pythagoræisk nummer Definition: "nummer er den sammensatte enheder mængde" [2] Euclid førte men ingen induktion beviser, men var indhold med intuitive, eksemplariske induktioner der kan, men fuldstændig. Andre vigtige matematikere i antikken og middelalderen havde heller ikke behov for præcise induktionsbeviser. Et par undtagelser i de hebraiske og arabisktalende områder forblev uden efterfølgere. [3] [4]

I lang tid blev et bevis af Franciscus Maurolicus fra 1575 betragtet som den ældste eksplicitte komplette induktion (detaljeret nedenfor). [5] Han har dog endnu ikke diskuteret den generelle bevisproces. Det var Blaise Pascal, der først tog fat på induktionsprincippet med induktionsstart og induktionstrin i sin Traité du triangel arithmétique fra 1654. [6] Fra 1686 bidrog Jakob I Bernoulli betydeligt til formidlingen af ​​induktionsbeviser. [7]

Bevisproceduren blev derefter først omtalt som induktion eller successiv induktion af Augustus De Morgan i 1838. [8] I 1888 opfandt Richard Dedekind endelig, hvad der er, og hvad er tallene? udtrykket komplet induktion . [9] Gennem dette arbejde fra begyndelsestiden for sætteorien blev det et velkendt, fastlagt bevisprincip, som ingen gren af ​​matematik har kunnet undvære siden da. Et år senere, i 1889, formulerede Giuseppe Peano den første formaliserede beregning for naturlige tal med et induktionsaksiom med det peanosiske aksiom, hvorfra beviset for den komplette induktion kan udledes. [10] Han viste med formel stringens, at fra hans talaksiomer, som induktionens aksiom tilhører, kan hele aritmetikken ned til de reelle tal udledes. Ved at gøre det gjorde han fuldt ud opmærksom på induktionens grundlæggende betydning og kraft.

definition

Siden Richard Dedekind er komplet induktion blevet defineret som følger:

At bevise, at en sætning for alle naturlige tal det er nok at vise
  • at han for gælder og
  • det ud fra forslagets gyldighed for et tal altid dens gyldighed også for det følgende nummer følger. [9]

Som en formel slutningsregel med en afledt operatør er den fulde induktion for et forslag og et naturligt tal :

og

Denne sidste regel er en kompakt formulering af beviset for den komplette induktion, som kan formuleres på en mere detaljeret didaktisk måde:

Skal formlen for alle naturlige tal er bevist, så er to tilstrækkelige bevis trin:
  1. begyndelsen på induktion : den bevis fra ,
  2. induktionstrinnet (også »afslutning af « [9] kaldes): den bevis induktionskravet slutningen og induktionshypotesen (også induktionshypotese, engl. induktionshypotese) .
Ifølge slutreglen ovenfor generaliseres formlen derefter på alle naturlige tal (den endelige induktionskonklusion ).

Den for naturlige tal ud af en mængde erklæring, der skal bevises forekommer i mindst 3 roller :

(1) som en induktionskrav for enhver (single)
(2) som induktionskrav for endelig mange mindre naturlige tal
(3) som en generel erklæring, der skal bevises for alle (og dermed for et uendeligt antal)

Mest er det eller . dog er det muligt.

For der er udsagnet til svarer til erklæringen til , Dedekinds induktion kan reduceres til den komplette induktion fra 0:

Axiomatikken af ​​naturlige tal af Peano

I 1889 beviste Peano med fuldstændig induktion de grundlæggende aritmetiske regler for addition og multiplikation : associativ lov , kommutativ lov og distributiv lov . [11] [12]

Axiomet for komplet induktion

Komplet induktion er et aksiom af naturlige tal. For det meste stammer det imidlertid fra det ækvivalente femte Peano -aksiom , induktionsaksiomet . Dette lyder:

er en delmængde af de naturlige tal med egenskaberne:

  1. er et element af
  2. med slutningen er altid også slutningen ,

derefter .

Peano -aksiomerne og dermed bevisproceduren for komplet induktion kan også udledes af andre begreber om naturlige tal, for eksempel i definitionen af ​​naturlige tal

  • som en ordnet halvgruppe genereret af 1, hvilket svarer til den citerede Pythagorean -taldefinition [2]
  • som en monoid genereret fri for 1, som er baseret på tilføjelsen af ​​tallene [13]
  • som algebra med efterfølgende kortlægning, der svarer til Dedekinds taldefinition [14] [15]
  • som det mindste induktive sæt , nemlig som det mindste sæt, der opfylder uendelighedens aksiom , som det er sædvanligt i sætteori
  • som en klasse af begrænsede ordinære tal , som kun forudsætter en generel sætteori uden uendelighedens aksiom

Eksempler

Gaussisk empirisk formel

Den gaussiske empiriske formel er:

For alle naturlige tal erklæringen gælder
.

Det kan bevises ved fuldstændig induktion.

Induktionsstartresultaterne straks:

.

I induktionstrinnet skal det vises, at for fra induktionshypotesen

induktionskravet

(med i stedet for induktionsforudsætningen) følger.

Dette opnås som følger:

(rød markerer induktionsantagelsen)
(Efter factoring ud overgav sig ...)
(... induktionskravet som du kan læse ovenfor.)

Endelig induktion lukning:
Det er udsagnet for alle bevist.

Summen af ​​ulige tal (Maurolicus 1575)

Bevis for den empiriske formel over ulige tal ved hjælp af komplet induktion

Den gradvise beregning af summen af ​​den første ulige tal antyder: Summen af ​​alle ulige tal af så længe er lig med kvadratet af :

Den generelle sætning, der skal bevises, er: . Maurolicus beviste det i 1575 med fuldstændig induktion. [5] Et bevis med beregningsregler, der er almindelige i dag, lyder som følger:

Begyndelsen på induktion med er fordi let verificeret.

Som et induktionstrin skal det vises: If , derefter . Det stammer fra følgende ligningskæde, hvor induktionsantagelsen anvendes i den anden transformation:

(Induktionshypotesen er markeret med rødt.)

Bernoullis ulighed

Bernoullis ulighed er et reelt tal med og naturlige tal

.

Induktionen starter med gælder her pga (med definitionsgabet på det punkt igennem suppleres konstant ).

Induktionstrinnet opnås fra følgende afledning, der anvender induktionsantagelsen i det andet trin, med ovenstående betingelse for sikrer, at udtrykket ikke bliver negativt:

(Induktionshypotesen er markeret med rødt.)

De to forekomster af -Sign (i samme retning) kan forenkles til:

Hestens paradoks

Hesteparadokset er et standardeksempel på en forkert anvendelse af fuld induktion og illustrerer betydningen af ​​samspillet mellem induktionsforankring og induktionstrin. Med ham den useriøse erklæring, der i en flok af Heste har altid den samme farve, bevist ved en tilsyneladende korrekt induktion. Selve induktionstrinnet er korrekt, men ville forankre induktionsforankringen i et brug, mens det (fejlbehæftede) bevis er induktion kl forankret og allerede skridtet til mislykkes.

Induktionsvarianter

Induktion med enhver begyndelse

Induktionsbevis for uligheden for naturlige tal :

Begyndelsen på induktion for resultater med .
Induktionstrinnet gælder på grund af følgende afledning, induktionskravet i det andet trin og kravet i det fjerde og sjette trin gælder:

Det begrænsede antal sager, som et sådant mere generelt induktionsbevis ikke dækker, kan undersøges individuelt. I eksemplet er uligheden for tilsyneladende forkert.

Stærk induktion

Induktion med flere forgængere

I nogle induktionsbeviser er det ikke tilstrækkeligt at henvise til en enkelt forgænger i induktionshypotesen, f.eks. Hvis en rekursionsformel indeholder flere forgængere. [16] Induktionsstarten skal derefter udføres for flere startværdier. Er induktionsantagelsen for at udlede en formel for og nødvendigt, så er en induktionsstart for to på hinanden følgende tal, f.eks. 0 og 1, påkrævet. Sætningen for alle tal mellem startværdien og tjene. Et eksempel [17] er beviset på, at hvert naturligt tal har en primær divisor:

Induktionsstart: 2 er delelig med primtal 2.
Induktionstrin: Udtalelsen er for alle med Opfylder. Er nu et primtal er altså selv den deler, vi leder efter, og påstanden er bevist. er ikke et primtal, så der er to tal med og . I dette tilfælde ejer ifølge induktionsantagelsen (= induktionsantagelse) en primær divisor, f.eks . Del derefter også og er hoveddeleren for . Dette beviser også påstanden for denne anden sag.

Formel definition

Erklæringen er for alle gyldigt, hvis følgende er sandt for nogen vil blive vist:

(Induktionstrin :) .

Bevisordningen for stærk induktion består derfor kun af induktionstrinnet.

Induktionstrinnet er derfor beviset på, at
for hver
induktionshypotesen [18]
induktionskravet medfører.
Så følger generaliseringen
(induktionslukning): Erklæringen gælder for alle .

Induktion begynder som de forekommer i almindelig induktion, f.eks. Beviset på udsagnet , er inkluderet i induktionstrinnet . [19] Det kan også ske, at mere end en indledende erklæring skal vises på forhånd (se Fibonacci -sekvensen ).

Det er klart, at den almindelige komplette induktion (formuleret i indledningen) følger af den stærke induktion. Men man kan også bevise den stærke induktion ved hjælp af den almindelige komplette induktion. [20]

bevis

At vise er:

Hvis for alle
slutningen (Induktionsantagelse normalt ⇒ stærk)
følger,
gælder derefter
til Alle sammen . (Induktionslukning normalt ⇒ stærk)

Vi definerer følgende udsagn for naturlige tal

og vise deres gyldighed ved hjælp af almindelig fuldstændig induktion.

Induktionsstart: Der , som er den tomme OG -forbindelse , gælder ifølge note [19] med det samme.

(Almindeligt) induktionstrin af til :

Være vilkårlig, og det gælder , dvs det gælder
.
På grund af (induktionsantagelsen normalt ⇒ stærk) følger det af dette
.
Taget sammen med resulterer i dette
.

Med det har vi vist hvilket er, og det sædvanlige induktionstrin er udført. Vi konkluderer (almindelig induktionslukning):

til Alle sammen er gældende .

På grund af a fortiori får vi den stærke induktionskonklusion:

til Alle sammen er gældende . ■

Trotz dieser prinzipiellen Gleichwertigkeit in der Beweisstärke ist der Unterschied in der Ausdrucksstärke wegen der beliebig vielen Startwerte und der Möglichkeit des Rückgriffs auf beliebig viele Vorgänger groß, besonders bei rekursiven Definitionen . Das bedeutet aber keineswegs, dass letztere Definitionen nicht in gewöhnliche Rekursionen überführt werden können.

Beispiel
  • Die Folge sei definiert durch die Rekursionsformel
    .
    Dann gilt:
    .
    Der Beweis mittels starker Induktion ist trivial.
    Die Rekursion lässt sich jedoch auch unschwer in eine auf einen einzigen Vorgänger umformen:
    .

Induktion mit Vorwärts-Rückwärts-Schritten

Augustin-Louis Cauchy führte 1821 eine Induktionsvariante vor, bei der der vorwärts gerichtete Induktionsschritt Sprünge macht (nämlich von nach ) und die entstandenen Lücken nachträglich durch eine rückwärts gerichtete Herleitung von nach auf einen Schlag gefüllt werden. [21] [22]

Beispiel: Ungleichung vom arithmetischen und geometrischen Mittel

Weitere Induktionsvarianten

Es gibt auch Sachlagen, bei denen Aussagen über alle ganzen Zahlen (positive und negative) mit vollständiger Induktion bewiesen werden können. Der Beweis in die positive Richtung geschieht wie gewohnt mit einem beliebigen Induktionsanfang und dem positiven Induktionsschritt von nach . Danach kann es möglich sein, den Induktionsschritt in die negative Richtung von nach auszuführen. Beispielsweise lässt sich bei der Fibonacci-Folge die Rekursionsgleichung in die Gegenrichtung umstülpen .

Die vollständige Induktion ist von natürlichen Zahlen verallgemeinerbar auf Ordinalzahlen . Bei Ordinalzahlen, die größer als die natürlichen Zahlen sind, spricht man dann von transfiniter Induktion .

Die Induktion ist auch übertragbar auf sogenannte fundierte Mengen , die eine der Zahlenordnung vergleichbare Ordnungsstruktur aufweisen; hier spricht man zuweilen von struktureller Induktion .

Rekursive oder induktive Definition

Die rekursive Definition – auch induktive Definition genannt [23] [24] – ist ein der vollständigen Induktion analoges Verfahren, bei der ein Term durch einen Rekursionsanfang und einen Rekursionsschritt definiert wird.

Beispiel einer rekursiven Funktion

Mit Hilfe der vollständigen Induktion kann man beweisen ( Gaußsche Summenformel ):

Die geschlossene Formel erspart die umständliche rekursive Berechnung.

Umgekehrt zeigt das nächste Beispiel, dass eine rekursive Berechnung günstiger sein kann.

Beispiel einer rekursiv definierten Funktion:

für ,
für und ungerade,
für und gerade.

Man kann mit Hilfe der vollständigen Induktion nach zeigen, dass

für ist.

Der Vorteil dieser rekursiven Definition ist, dass man bei der Berechnung hoher Potenzen nicht Multiplikationen, sondern nur Multiplikationen in der Größenordnung von hat. [25] Sehr hohe Potenzen werden zum Beispiel bei der RSA-Verschlüsselung von Nachrichten verwendet.

Die rekursive Definition hat wie die Induktion allerlei differenzierte Varianten.

Weblinks

Einzelnachweise

  1. Induktionsanfang und Induktionsschritt sind oft mit Methoden der „Schullogik“ herleitbar. Bei der vollständigen Induktion handelt es sich jedoch um ein Verfahren der Prädikatenlogik zweiter Stufe .
  2. a b Euklids Elemente VII, Definition 2. Dazu: Wilfried Neumaier: Antike Rhythmustheorien , Kap. 1 Antike mathematische Grundbegriffe , S. 11–12.
  3. Rabinovitch: Rabbi Levi Ben Gershon and the Origins of Mathematical Induction , in: Archive for History of Exact Sciences 6 (1970), S. 237–248.
  4. Roshdi Rashed : L'induction mathématique: al-Karajī, as-Samaw'al , in: Archive for History of Exact Sciences 9 (1972), S. 1–21.
  5. a b Maurolycus: Arithemticorum Liber primus , S. 7, Proposition 15 a . eingeschränkte Vorschau in der Google-Buchsuche.
  6. Blaise Pascal: Traité du triangle arithmétique , S. 7, Conséquence douziesme, Le 1. (Induktionsanfang), Le 2. (Induktionsschritt), digital eingeschränkte Vorschau in der Google-Buchsuche.
  7. Lexikon bedeutender Mathematiker, Leipzig 1990, Artikel „Jakob Bernoulli“, S. 48.
  8. De Morgan: Artikel Induction (Mathematics) in: Penny Cyclopædia XII (1838), S. 465–466.
  9. a b c Richard Dedekind: Was sind und was sollen die Zahlen? , Braunschweig 1888, § 6 Satz 80, Originalwortlaut: Satz der vollständigen Induktion (Schluss von n auf n'). Um zu beweisen, dass ein Satz für alle Zahlen n einer Kette m 0 gilt, genügt es zu zeigen, dass er für n = m gilt und dass aus der Gültigkeit des Satzes für eine Zahl n der Kette m 0 stets seine Gültigkeit auch für die folgende Zahl n' folgt.
  10. Peano: Arithmetices principia nova methodo exposita , 1889, in: G. Peano, Opere scelte II, Rom 1958, S. 20–55.
  11. Peano: Arithmetices principia nova methodo exposita. 1889. In: G. Peano: Opere scelte. Band II. Rom 1958. S. 35–36, 40–41.
  12. ausführliche Beweise auch in: Edmund Landau : Grundlagen der Analysis. Leipzig 1930.
  13. Felscher: Naive Mengen und abstrakte Zahlen I, S. 130–132.
  14. Dedekind: Was sind und was sollen die Zahlen? , § 6, Erklärung 71.
  15. dargestellt als Dedekind-Tripel in: Felscher: Naive Mengen und abstrakte Zahlen I, S. 147.
  16. S. Beweis der Formel von Binet für die Fibonacci-Folge
  17. Ein weiteres Beispiel ist der Beweis des Zeckendorf-Theorems ; s. Der Satz von Zeckendorf .
  18. Definitionsgemäß ist .
    Die Induktionsvoraussetzung (die Induktionsannahme) besteht also darin, dass
    für alle Zahlen von bis als gültig angenommen wird.
  19. a b Da das neutrale Element der Und-Verknüpfung ist und deshalb die leere Und-Verknüpfung den Wahrheitswert hat, ist die Implikation durch das Zutreffen von nachzuweisen. So betrachtet "steckt/stecken" der/die Induktionsanfang/anfänge bei der starken Induktion alle im Induktionsschritt.
  20. Oliver Deiser Einführung in die Mathematik .
    Der hauptsächliche Unterschied des starken Induktionsschemas zum gewöhnlichen ist – wie der Beweis zeigt, dass beim gewöhnlichen Schema jede Induktionsvoraussetzung genau einmal (in einer einzigen Induktionsstufe) benutzt wird, während beim starken Schema von mehreren höheren Induktionsstufen aus auf sie Bezug genommen werden kann.
  21. Cauchy, Augustin-Louis. Analyse algebrique. Paris 1821. Der Beweis der Ungleichung vom arithmetischen und geometrischen Mittel ist dort auf Seite 457 ff.
  22. Eine Vorwärts-Rückwärts-Induktion ist auch der Beweis der jensenschen Ungleichung . Jensen: Sur les fonctions convexes et les inégalités entre les valeurs moyennes. In: Acta Math. 30, 1906, S. 175–193.
  23. Hausdorff: Grundzüge der Mengenlehre. 1914. S. 112–113 eingeschränkte Vorschau in der Google-Buchsuche.
  24. Peano: Le Definitione in Matematica. In: Opere scelte. Band II, 1921. S. 431, § 7 Definizioni per induzione.
  25. Zum Beispiel errechnet sich
    für x=3 wird
    wird in 6 Rechenschritten berechnet:
    1.

    2.

    3.
    6 561
    4.
    43 046 721
    5.
    1 853 020 188 851 841
    6.
    12 157 665 459 056 928 801