Principiul inducției

Efectul domino oferă o metaforă explicativă pentru principiul inducției

Principiul inducției (care nu trebuie confundat cu metoda inducției ) este o afirmație privind numerele naturale care este utilizată pe scară largă în matematică în dovezi , pentru a demonstra că o anumită proprietate este valabilă pentru toți numerele întregi. Ideea intuitivă din spatele acesteia este efectul domino : pentru ca plăcile de domino dispuse de-a lungul unui rând să cadă, sunt suficiente două condiții:

că prima carte cade
că fiecare țiglă este poziționată în așa fel încât căderea să provoace căderea următoarei.

Principiul inducției extinde această idee la cazul în care rândul este alcătuit din dale infinite.

Declarație formală

Principiul inducției afirmă că dacă $P.$ ${\ displaystyle P}$ $P.$ este o proprietate care deține numărul 0 și dacă $P(n)\Rightarrow P(n+1)$ ${\ displaystyle P (n) \ Rightarrow P (n + 1)}$ ${\ displaystyle P (n) \ Rightarrow P (n + 1)}$ pentru fiecare $n$ ${\ displaystyle n}$ $n$ , asa de $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ se aplică tuturor $n$ ${\ displaystyle n}$ $n$ .

În simboluri:

(\forall P)[P(0)\land (\forall k\in \mathbb {N} )(P(k)\Rightarrow P(k+1))]\Rightarrow (\forall n\in \mathbb {N} )[P(n)]

{\ displaystyle (\ forall P) [P (0) \ land (\ forall k \ in \ mathbb {N}) (P (k) \ Rightarrow P (k + 1))] \ Rightarrow (\ forall n \ in \ mathbb {N}) [P (n)]}

{\ displaystyle (\ forall P) [P (0) \ land (\ forall k \ in \ mathbb {N}) (P (k) \ Rightarrow P (k + 1))] \ Rightarrow (\ forall n \ in \ mathbb {N}) [P (n)]}

unde este $k$ ${\ displaystyle k}$ $k$ Și $n$ ${\ displaystyle n}$ $n$ sunt numere naturale .

Istorie

Prima atestare specifică a principiului datează din 1861, de Robert Grassmann ^[1] . Prima sa utilizare într-o demonstrație datează din 1575 de italianul Francesco Maurolico ^[2] . În secolul al XVII-lea, Pierre de Fermat și-a perfecționat utilizarea formulându-l ca principiul descendenței infinite ^[2] , iar noțiunea apare clar și în lucrările ulterioare ale lui Blaise Pascal (1653) ^[2] . Expresia „inducție matematică” pare să fi fost inventată de logicianul și matematicianul A. De Morgan la începutul secolului al XIX-lea ^[2] . Formularea sa completă, utilizată și astăzi, este în esență cea dată de Giuseppe Peano în Arithmetices Principia , publicată în 1889. Principiul inducției derivă direct din a cincea axiomă a lui Peano și este echivalent cu acesta: adică presupunându-l ca o axiomă, derivă a cincea axiomă a lui Peano.

Dovezi prin inducție

Principiul de inducție oferă un instrument important pentru demonstrații . Pentru a demonstra că o anumită afirmație $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ în care apare un număr natural $n$ ${\ displaystyle n}$ $n$ se aplică oricărui $n\in \mathbb {N}$ ${\ displaystyle n \ in \ mathbb {N}}$ $n \ in \ mathbb {N}$ principiul inducției poate fi exploatat în felul următor:

Se ridică $U=\{n\in \mathbb {N} :{\mbox{vale }}P(n)\}$ ${\ displaystyle U = \ {n \ in \ mathbb {N}: {\ mbox {is}} P (n) \}}$ ${\ displaystyle U = \ {n \ in \ mathbb {N}: {\ mbox {worth}} P (n) \}}$ ,

se dovedește că merită $P(1)$ ${\ displaystyle P (1)}$ $P (1)$ (sau $P(0)$ ${\ displaystyle P (0)}$ $P (0)$ ), asta este ceea ce $1$ ${\ displaystyle 1}$ $1$ (o) se află în subgrupul numerelor naturale $U$ ${\ displaystyle U}$ $U$ pentru care este valabil $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ ;
se presupune ca ipoteză că afirmația $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ se aplică unui generic $n$ ${\ displaystyle n}$ $n$ și din această presupunere se arată că deține și ea $P(n+1)$ ${\ displaystyle P (n + 1)}$ $P (n + 1)$ (asta este ceea ce $n\in U\Rightarrow n+1\in U$ ${\ displaystyle n \ în U \ Rightarrow n + 1 \ în U}$ $n \ in U \ Rightarrow n + 1 \ in U$ )

și, prin urmare, concluzionăm că setul $U$ ${\ displaystyle U}$ $U$ dintre numerele pentru care se aplică $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ coincide cu mulțimea numerelor naturale. Punctul 1 se numește în general baza inducției , punctul 2 pas inductiv .

O modalitate intuitivă de a privi acest tip de dovadă este următoarea: dacă avem o dovadă a bazei

P(0)

{\ displaystyle P (0)}

P (0)

iar pasul inductiv

\forall n\,P(n)\Rightarrow P(n+1)

{\ displaystyle \ forall n \, P (n) \ Rightarrow P (n + 1)}

\ forall n \, P (n) \ Rightarrow P (n + 1)

atunci în mod clar putem folosi aceste dovezi pentru a demonstra $P(1)$ ${\ displaystyle P (1)}$ $P (1)$ folosind regula logică modus ponens su $P(0)$ ${\ displaystyle P (0)}$ $P (0)$ (baza) e $P(0)\Rightarrow P(1)$ ${\ displaystyle P (0) \ Rightarrow P (1)}$ $P (0) \ Rightarrow P (1)$ (care este un caz special al pasului inductiv pentru $n=0$ ${\ displaystyle n = 0}$ $n = 0$ ), atunci putem demonstra $P(2)$ ${\ displaystyle P (2)}$ $P (2)$ de acum folosim modus ponens su $P(1)$ ${\ displaystyle P (1)}$ $P (1)$ Și $P(1)\Rightarrow P(2)$ ${\ displaystyle P (1) \ Rightarrow P (2)}$ $P (1) \ Rightarrow P (2)$ , prin urmare $P(3)$ ${\ displaystyle P (3)}$ $P (3)$ , $P(4)$ ${\ displaystyle P (4)}$ $P (4)$ , etc ... este clar în acest moment că putem produce o dovadă într-un număr finit de pași (posibil foarte lungi) din $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ pentru orice număr natural $n$ ${\ displaystyle n}$ $n$ , din care deducem că $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ este adevărat pentru fiecare $n\in \mathbb {N}$ ${\ displaystyle n \ in \ mathbb {N}}$ $n \ in \ mathbb {N}$ .

Exemplu

Arătăm că afirmația este valabilă: pentru fiecare $n\in \mathbb {N} ^{+}$ ${\ displaystyle n \ in \ mathbb {N} ^ {+}}$ ${\ displaystyle n \ in \ mathbb {N} ^ {+}}$ rezultă:

1+2+3+4+...+n={\frac {n(n+1)}{2}}

{\ displaystyle 1 + 2 + 3 + 4 + ... + n = {\ frac {n (n + 1)} {2}}}

1 + 2 + 3 + 4 + ... + n = {\ frac {n (n + 1)} {2}}

.

În acest caz, am definit $P(n)=1+2+3+4+...+n={\frac {n(n+1)}{2}}$ ${\ displaystyle P (n) = 1 + 2 + 3 + 4 + ... + n = {\ frac {n (n + 1)} {2}}}$ $P (n) = 1 + 2 + 3 + 4 + ... + n = {\ frac {n (n + 1)} {2}}$ .

Baza inducției : afirmarea $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ este adevărat pentru $n=1$ ${\ displaystyle n = 1}$ $n = 1$ , de fapt, prin substituție, se întâmplă că $P(1)={\frac {1\cdot (1+1)}{2}}={\frac {1\cdot 2}{2}}=1$ ${\ displaystyle P (1) = {\ frac {1 \ cdot (1 + 1)} {2}} = {\ frac {1 \ cdot 2} {2}} = 1}$ $P (1) = {\ frac {1 \ cdot (1 + 1)} 2} = {\ frac {1 \ cdot 2} 2} = 1$
Pas inductiv : trebuie să arătăm că pentru fiecare n valabilitatea formulei, adică aceea $P(n)={\frac {n(n+1)}{2}}$ ${\ displaystyle P (n) = {\ frac {n (n + 1)} {2}}}$ $P (n) = {\ frac {n (n + 1)} {2}}$ , implică faptul că formula este valabilă și pentru n + 1 sau, în mod explicit:

{\frac {n(n+1)}{2}}\quad \Rightarrow \quad {\frac {(n+1)((n+1)+1)}{2}}

{\ displaystyle {\ frac {n (n + 1)} {2}} \ quad \ Rightarrow \ quad {\ frac {(n + 1) ((n + 1) +1)} {2}}}

{\ frac {n (n + 1)} {2}} \ quad \ Rightarrow \ quad {\ frac {(n + 1) ((n + 1) +1)} {2}}

dovada acestei afirmații devine mai simplă după ce am afirmat că adăugarea primelor n + 1 numere întregi este echivalentă cu adăugarea n + 1 la suma primelor n numere întregi, adică:

\ P(n+1)=1+2+3+4+...+n+(n+1)=P(n)+(n+1)

{\ displaystyle \ P (n + 1) = 1 + 2 + 3 + 4 + ... + n + (n + 1) = P (n) + (n + 1)}

\ P (n + 1) = 1 + 2 + 3 + 4 + ... + n + (n + 1) = P (n) + (n + 1)

de aceea dovada pe care o căutăm se obține prin adăugarea n + 1 a $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ și verificarea faptului că rezultatul coincide cu $P(n+1)$ ${\ displaystyle P (n + 1)}$ $P (n + 1)$ pasajele algebrice sunt deci:

P(n)+(n+1)=1+2+3+4+...+n+(n+1)={\frac {n(n+1)}{2}}+(n+1)={\frac {n(n+1)+2(n+1)}{2}}={\frac {(n+1)(n+2)}{2}}=

{\ displaystyle P (n) + (n + 1) = 1 + 2 + 3 + 4 + ... + n + (n + 1) = {\ frac {n (n + 1)} {2}} + (n + 1) = {\ frac {n (n + 1) +2 (n + 1)} {2}} = {\ frac {(n + 1) (n + 2)} {2}} =}

P (n) + (n + 1) = 1 + 2 + 3 + 4 + ... + n + (n + 1) = {\ frac {n (n + 1)} {2}} + (n + 1) = {\ frac {n (n + 1) +2 (n + 1)} {2}} = {\ frac {(n + 1) (n + 2)} {2}} =

={\frac {(n+1)((n+1)+1)}{2}}=P(n+1)

{\ displaystyle = {\ frac {(n + 1) ((n + 1) +1)} {2}} = P (n + 1)}

= {\ frac {(n + 1) ((n + 1) +1)} {2}} = P (n + 1)

.

Aceasta încheie dovada pasului inductiv .

Prin urmare, verificând validitatea atât a bazei inducției, cât și a etapei inductive, putem concluziona că formula

1+2+3+4+...+n={\frac {n(n+1)}{2}}

{\ displaystyle 1 + 2 + 3 + 4 + ... + n = {\ frac {n (n + 1)} {2}}}

1 + 2 + 3 + 4 + ... + n = {\ frac {n (n + 1)} {2}}

este adevărat pentru fiecare $n\in \mathbb {N} ^{+}$ ${\ displaystyle n \ in \ mathbb {N} ^ {+}}$ ${\ displaystyle n \ in \ mathbb {N} ^ {+}}$ .

Principiul inducției puternice

Principiul inducției puternice derivă dintr-o versiune cu ipoteze aparent mai restrictive ale celei de-a cincea axiome a lui Peano , dar echivalentă: dacă $U$ ${\ displaystyle U}$ $U$ este un subset al setului $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ de numere naturale astfel încât

$U$ ${\ displaystyle U}$ $U$ conține $1$ ${\ displaystyle 1}$ $1$ (sau),
de sine $U$ ${\ displaystyle U}$ $U$ conține toate numerele mai mici decât $n$ ${\ displaystyle n}$ $n$ apoi conține și $n$ ${\ displaystyle n}$ $n$

asa de $U=\mathbb {N}$ ${\ displaystyle U = \ mathbb {N}}$ $U = {\ mathbb N}$

Cuvântul „puternic” este legat de faptul că această formulare necesită ipoteze aparent mai puternice și mai stricte pentru a deduce că întregul $U$ ${\ displaystyle U}$ $U$ coincide cu $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ : În scopul de a admite un număr ca întreg este necesar ca toate cele anterioare deja aparțin de ea (și nu doar numărul anterior). În practică, proprietatea ${\mathcal {P}}$ ${\ displaystyle {\ mathcal {P}}}$ ${\ mathcal {P}}$ trebuie să se mențină nu numai pentru n , ci pentru fiecare $x\in \mathbb {N} :x<n$ ${\ displaystyle x \ in \ mathbb {N}: x <n}$ $x \ in {\ mathbb N}: x <n$ . Nu este dificil să-și demonstreze echivalența logică cu principiul inducției, argumentând astfel: dacă păstrează pentru 1 (sau 0), deține și pentru succesorul său, și pentru succesorul acestuia din urmă etc., până la n . Mai mult, dacă proprietatea este valabilă pentru orice număr mai mic decât n, este valabilă și pentru 1 (sau 0) și, dacă este valabilă pentru b, este valabilă și pentru b + 1 ≤ n și, prin urmare, este echivalentă cu principiul inducției.

Utilitatea principiului puternic de inducție

Această formulare facilitează uneori demonstrarea prin inducție, având în vedere posibilitatea de a avea o gamă mai largă de ipoteze (toate numerele mai mici decât $n$ ${\ displaystyle n}$ $n$ ) pentru demonstrarea următorului „pas inductiv”. Acest lucru se întâmplă, de exemplu, în dovada factorizabilității numerelor întregi (a se vedea teorema fundamentală a aritmeticii ): unde, în dovadă, dorim să folosim principiul inducției, regresia de la un număr n la factori mai mici nu duce la numărul anterior m, dar la numere mai mici. În acest caz, principiul slab de inducție nu ar fi util. Aceeași situație este întâlnită și în factorizarea polinoamelor .

Forme echivalente ale principiului inducției

În total, formele principiului inducției sunt 4:

Aceste forme sunt echivalente în sensul că asumarea uneia adevărate poate dovedi celelalte trei.

Inducția este o axiomă sau o teoremă?

În general, principiul inducției este indicat ca axiomă a numerelor naturale: uneori este considerat în locul celei de-a cincea axiome a lui Peano, obținându-se un model echivalent, deoarece, așa cum am menționat anterior, cele două sunt echivalente. Teoria obținută prin luarea în considerare axiomelor clasice ale lui Peano (adică axiomele aritmeticii lui Peano ), cu excepția principiului inducției, se numește aritmetică Robinson și admite modele alternative în care principiul inducției este fals.

Cu toate acestea, există unele sisteme logice în care se poate dovedi: de exemplu, când se folosește axioma

Mulțimea numerelor naturale este bine ordonată

adică

Fiecare subset ne-gol al setului de numere naturale are un număr minim

cunoscut și ca principiul bunei ordonări pentru numerele naturale . În realitate, această axiomă suplimentară este o formulare alternativă a principiului inducției matematice: cele două axiome sunt de fapt echivalente .

De fapt, dacă un set ne-gol nu are minimum 0, nu îi aparține. Presupunând atunci că numerele mai mici de m numere nu îi aparțin, atunci și m nu îi aparține (altfel ar fi minimul. Aplicând o inducție puternică obținem că niciun număr nu îi aparține.

Dimpotrivă, având în vedere un set, se bucură de cele două proprietăți enunțate de principiul inducției fără a acoperi totul $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ . Va exista, pentru buna ordine, numărul minim care nu îi aparține și acesta este m . Atunci m nu poate fi 0 . M-1 anterior său nu respectă ipoteza inductivă.

Cu toate acestea, în unele cazuri, principiul inducției nu este considerat o axiomă, aceasta depinde de modul în care este definit setul numerelor naturale. Dacă definesc întregul $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ axiomatic (cu axiomele lui Peano) voi avea ca principiul inducției să fie o axiomă, așa cum am spus anterior, invers dacă definesc setul $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ ca cel mai mic set inductiv cuprins în $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ mathbb R$ , și mai precis ca intersecție a tuturor seturilor inductive conținute în $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ mathbb R$ , Voi avea că principiul inducției nu poate fi considerat o axiomă, deoarece nu este setul $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ definit axiomatic, dar va fi o consecință a faptului că $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ este cel mai mic set inductiv.

Generalizări

Punct de plecare diferit de zero

O primă generalizare foarte de bază constă în pornirea inducției de la un număr natural k diferit de zero. Adică: dacă vrem să demonstrăm că o afirmație $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ păstrează pentru orice număr natural $n$ ${\ displaystyle n}$ $n$ mai mare sau egal cu un număr prestabilit $k$ ${\ displaystyle k}$ $k$ aplicăm tehnica dovezii inducției considerând inducția ca bază $P(k)$ ${\ displaystyle P (k)}$ $P (k)$ Decat $P(0)$ ${\ displaystyle P (0)}$ $P (0)$ .

Inducție transfinită

Același subiect în detaliu: inducția transfinită .

Principiul inducției transfinite generalizează principiul inducției la clasa ordinalelor transfinite On (din care numerele naturale sunt un subset).
Se afirmă că dacă $U$ ${\ displaystyle U}$ $U$ este un subset al clasei $SAU n$ ${\ displaystyle On}$ $Onorabil$ dintre toate ordinale care verifică următoarele două proprietăți:

$U$ ${\ displaystyle U}$ $U$ conține,
de fiecare dată când $U$ ${\ displaystyle U}$ $U$ conține toate ordinalele $la$ ${\ displaystyle a}$ $la$ mai puțin decât $b$ ${\ displaystyle b}$ $b$ asa de $U$ ${\ displaystyle U}$ $U$ conține și $b$ ${\ displaystyle b}$ $b$ ,

asa de $U$ ${\ displaystyle U}$ $U$ coincide cu întreaga clasă de ordinali $SAU n$ ${\ displaystyle On}$ $Onorabil$ .

Principiul inducției transfinite , spre deosebire de principiul inducției puternice , este un principiu strict mai puternic decât principiul inducției , de fapt există teoreme precum Teorema lui Goodstein care pot fi dovedite prin inducție transfinită, dar nu pot fi dovedite prin simpla inducție.

Erori și neînțelegeri

O aplicare greșită clasică a principiului inducției este următoarea „dovadă” care duce la concluzia că

Toți caii au aceeași culoare

Raționăm prin inducție asupra mărimii posibilelor ansambluri de cai: dovedim că pentru fiecare $n\in \mathbb {N}$ ${\ displaystyle n \ in \ mathbb {N}}$ $n \ in {\ mathbb N}$ merita $P(n)$ ${\ displaystyle P (n)}$ $P (n)$ = "un set de $n$ ${\ displaystyle n}$ $n$ caii conțin toți caii de aceeași culoare ":

1. Bază de inducție: un set format dintr-un singur cal ( n = 1) conține toți caii de aceeași culoare.

2. Pas inductiv: presupunem adevărat

P(n)

{\ displaystyle P (n)}

P (n)

= "un set de

n

{\ displaystyle n}

n

caii conțin toți caii de aceeași culoare "și demonstrăm

P(n+1)

{\ displaystyle P (n + 1)}

P (n + 1)

: un set de

n+1

{\ displaystyle n + 1}

n + 1

caii pot fi priviți ca unirea a două seturi de

n

{\ displaystyle n}

n

cai pe care îi au în comun

n-1

{\ displaystyle n-1}

n-1

elemente, prin urmare, din ipoteza inductivă, aceste seturi au toate cai de aceeași culoare și din faptul că au intersecție ne-goală deducem că toate

n+1

{\ displaystyle n + 1}

n + 1

caii au aceeași culoare, adică am arătat

P(n+1)

{\ displaystyle P (n + 1)}

P (n + 1)

.

Din principiul inducției rezultă că oricare ar fi numărul de cai prezenți în lume, toți au aceeași culoare.

Dovada pasului inductiv anterior este doar aparentă: de fapt pentru n = 1 cele două seturi de n elemente au n -1 = 0 elemente în comun și, prin urmare, nu se poate deduce că n +1 = 2 cai au aceeași culoare.

Notă

^ Robert Grassmann, Lehrbuch der Arithmetik , Berlin, 1861.
^ ^a ^b ^c ^d Donald E. Knuth , Algoritmul fundamental , în The Art of Computer Programming , vol. 1, ediția a 3-a, Addison-Weseley Professional, 1996, p. 17.

Elemente conexe

linkuri externe

Giovanni Vacca, Induzione , pe Enciclopedia Italiana Treccani , 1933. Adus la 24 octombrie 2014 .

Controlul autorității	LCCN (EN) sh85065806 · GND (DE) 4124408-4

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Robert Grassmann, Lehrbuch der Arithmetik , Berlin, 1861.

[k-2] Donald E. Knuth , Algoritmul fundamental , în The Art of Computer Programming , vol. 1, ediția a 3-a, Addison-Weseley Professional, 1996, p. 17.

[1]

[2]

V · D · M Teoria numerelor
Cele mai utilizate numere	Natural · Întreg · Par și impar
Principii generale	Principiul inducției · Principiul unei bune ordonări · Relația de echivalență
Secvențe de numere întregi	Factorial · Fibonacci · Număr de catalană · Număr Perrin · Număr de Euler · Secvență Mian-Chowla · Succesiunea lui Thue-Morse
Caracteristicile numerelor prime	Primul număr · lema lui Euclid · Teorema infinitate de numere prime · ciurul Eratostene · teste primality · Teorema fundamentală a aritmeticii · Total acoperire mine · Bézout Identitate · MCD · mcm · algoritmul lui Euclid · Teorema de Prime Numbers
Funcții aritmetice	Funcție multiplicativă · funcție aditivă · Convoluție Dirichlet · Funcția Euler Euler · Funcția Möbius · funcția tau pe pozitiv · funcția sigmoidă · Funcția Liouville · Funcția Mertens
Aritmetica modulară	Teorema a restului chinez · teorema lui Fermat mici · teorema lui Euler · Criterii de divizibilitate · teorema lui Fermat pe sume de două pătrate · Wilson Teorema · reciprocitatea pătratică
Conjecturi	Conjectura lui Goldbach · Conjectura Polignac · Guess abc · conjectura primelor gemene · Conjectura lui Legendre · Noua conjectură Mersenne · Conjectura Collatz · Ipoteza Riemann
Alte	Problema lui Waring
Principalii teoreticieni	Fibonacci · Fermat · Gauss · Euler · Legendre · Riemann · Dirichlet
Disciplinele conexe	Teoria algebrică a numerelor · Teoria analitică a numerelor · Criptografie · Teoria computațională a numerelor