Demonstrația prin reducere la absurd

Demonstrația prin reducere la absurd este o tehnică de demonstrare foarte folosită. Dacă vrem să demonstrăm că o afirmație este adevărată, o negăm, presupunem că negația ei este adevărată și încercăm să ajungem la o contradicție. Scopul este să arătăm că presupunerea făcută duce la o absurditate.

Un exemplu banal

Fie afirmația „nu există cel mai mic număr rațional pozitiv”. Demonstrăm această afirmație prin reducere la absurd: mai întâi o negăm, „există cel mai mic număr rațional pozitiv”, și notăm acest număr cu q. Dacă q este cel mai mic număr rațional pozitiv, atunci nu putem găsi un număr rațional pozitiv mai mic – pentru că altfel q nu ar fi cel mai mic.

Folosim asta ca să căutăm contradicția. Dacă totuși găsim un număr mai mic decât q, pe care îl putem alege oricum, am ajuns la o contradicție, iar afirmația negată nu este adevărată. Dacă alegem drept cel mai mic număr, de exemplu, 0,1, vedem că 0,01 este mai mic. Apoi 0,001 este și mai mic, 0,0001 este iar mai mic și tot așa. Ajunge să împărțim numărul q la zece și obținem un număr mai mic. De fapt ajunge să îl împărțim la orice număr mai mare decât unu, de exemplu la doi – jumătatea numărului q este cu siguranță mai mică decât q întreg.

Deci numărul q/2 este cu siguranță mai mic decât q și, în același timp, este un număr rațional pozitiv. Am ajuns astfel la o contradicție cu afirmația negată, deci afirmația negată nu este adevărată și, prin urmare, este adevărată afirmația inițială, nenegată.

Numerele interesante

Un exemplu clasic, hazliu, care ilustrează principiul reducerii la absurd este următorul. Să presupunem că există numere naturale care sunt într-un fel interesante. De exemplu, numărul 2 este interesant, deoarece are loc 2 · 2 = 2 + 2, o proprietate destul de neobișnuită. Numărul 42 este interesant, deoarece este răspunsul la marea întrebare despre viață, univers și tot ce există. Și așa mai departe. Întrebarea este: există o infinitate de numere interesante?

Să presupunem contrariul, adică că există doar un număr finit de numere interesante și că unele numere sunt neinteresante. Aceste numere naturale neinteresante le strângem în mulțimea numerelor neinteresante. Acum alegem cel mai mic număr neinteresant. Stai puțin, cel mai mic număr neinteresant? Sună destul de interesant, nu? :-)

Am ajuns astfel la o contradicție, deoarece cel mai mic număr neinteresant este de fapt destul de interesant, deci nu poate exista un cel mai mic număr neinteresant, prin urmare mulțimea numerelor neinteresante trebuie să fie în mod necesar vidă.

Bineînțeles, este o absurditate, nu am definit cum trebuie ce este un număr interesant, dar procedeul de demonstrare în sine este corect.

Demonstrarea infinității numerelor prime

În acest exemplu vedem un procedeu asemănător cu cel din secțiunea precedentă, dar de data aceasta este corect din toate punctele de vedere.

Numărul prim este un număr divizibil doar cu două numere diferite – el însuși și unu. Observă că definiția nu este îndeplinită de unu, dar este îndeplinită de doi.

Descompunerea în factori primi, numită și factorizare, înseamnă scrierea unui număr natural mai mare decât unu ca produs de numere prime. Este o proprietate destul de interesantă a numerelor naturale. Orice număr natural mai mare decât unu ai alege, el poate fi descompus într-un produs de câteva numere prime (eventual egale). Exemple:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

Afirmația despre descompunerea în factori primi se numește teorema fundamentală a aritmeticii. Ea ne spune, printre altele, că o astfel de descompunere este unică, adică nu găsim două descompuneri în factori primi diferite ale aceluiași număr natural. Mai mult, doar numerele prime au o descompunere în factori primi formată dintr-un singur număr – ele însele. Deci descompunerea în factori primi a lui șapte ar fi numărul șapte. Aceste fapte le folosim la construirea demonstrației următoarei afirmații.

Acum demonstrăm afirmația „există o infinitate de numere prime”. Negăm din nou afirmația: „numărul numerelor prime este finit”. Presupunem că șirul de numere

$$a_1,a_2,a_3,\dots ,a_n$$

reprezintă toate numerele prime existente. Dacă în acest șir se află toate numerele prime, atunci sigur nu vom mai putea găsi un număr care să fie prim și, în același timp, să nu se afle în acest șir. Toate numerele prime sunt în șir, în afara șirului nu mai are voie să apară niciun număr prim.

Dacă vrem să ajungem la o contradicție, trebuie deci să construim un număr prim care nu se află în acest șir. Ne ajută numărul q. Îl construim înmulțind toate numerele prime din șir și adunând unu:

$$q=a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1$$

Acum trebuie să arătăm că acest număr fie este prim, fie generează, într-un fel, un număr prim. Știm că q este număr natural mai mare decât unu și că orice astfel de număr poate fi scris ca produs de numere prime. Totuși, niciun număr prim a_i nu îl divide exact pe q, mereu rămâne restul unu după împărțire. Dacă am încerca să îl împărțim pe q, de exemplu, la numărul prim a₂, am obține:

$$\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1}{a_2}=\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1\cdot a_3\cdot a_4\cdot \dots \cdot a_n+\frac{1}{a_2}$$

Mai întâi descompunem fracția în două. În prima fracție simplificăm cu a₂ și ne rămâne un produs de numere prime, care este pur și simplu un alt număr întreg, fără importanță. În a doua fracție nu avem ce simplifica, această fracție va fi mereu un număr neîntreg (pentru că numitorul nu poate fi unu, unu nu este număr prim). În sumă obținem deci un număr care nu este întreg, adică numărul prim a₂ nu îl divide pe q.

Am demonstrat astfel că niciunul dintre numerele prime din șirul a_n nu îl divide pe q. (Observație: am arătat asta doar pentru a₂, dar se generalizează ușor dacă înlocuim a₂ cu un a_i oarecare.) Dar, deoarece orice număr natural mai mare decât unu poate fi descompus într-un produs de numere prime, trebuie să existe alte numere prime, care nu se află în șirul a_n, dar care apar în factorizarea lui q. Însuși numărul q poate fi, de altfel, prim, iar descompunerea în factori primi va conține atunci doar numărul q. Să recapitulăm încă o dată ultimul raționament:

1. Orice număr natural mai mare decât unu poate fi scris ca un produs de numere prime.
2. Conform presupunerii, șirul a_n conține toate numerele prime existente.
3. Modificăm prima afirmație: orice număr natural mai mare decât unu poate fi scris ca produs de termeni aleși din șirul a_n, deoarece acesta conține toate numerele prime.
4. Am demonstrat că niciun număr din șirul a_n nu îl divide pe q.
5. Astfel apare o contradicție cu presupunerea → dacă trebuie să putem descompune orice număr natural mai mare decât unu într-un produs de numere prime, iar șirul a_n nu conține niciun număr care îl divide pe q, atunci trebuie să existe alte numere prime care îl divid pe q și care formează descompunerea lui q în factori primi.

Am ajuns astfel la o contradicție. Descompunerea în factori primi a lui q cuprinde numere prime care nu se află în șirul despre care am presupus că conține toate numerele prime. Deci afirmația negată nu este adevărată, este adevărată afirmația inițială, nenegată. Există o infinitate de numere prime.