Argumentul diagonal al lui Cantor

Argumentul diagonal al lui Cantor este o tehnică demonstrativă cu care Georg Cantor a dovedit nenumăratul numerelor reale . Tehnica Cantor a fost utilizată în numeroase variații pentru a obține rezultate în logica matematică și teoria calculabilității .

Numere reale necontabilizate

În primul rând putem considera, în locul întregului set R al numerelor reale, intervalul [0,1]; dacă acest interval nu poate fi numărat, cu atât mai mult motiv nu poate fi R.

Dovada se desfășoară în mod absurd , după cum urmează:

Să presupunem în mod absurd că intervalul [0,1] este numărabil.
aceasta înseamnă că elementele [0,1] pot fi plasate în corespondență unu-la-unu cu numerele naturale dând naștere unei succesiuni de numere reale { r ₁ , r ₂ , r ₃ , ...} care epuizează toate numere reale incluse între 0 și 1.
Putem reprezenta fiecare număr al secvenței în formă zecimală și vizualiza secvența numerelor reale ca o matrice infinită care va arăta cam așa:
r ₁ = 0, 5 1 0 5 1 1 0 ...
r ₂ = 0, 4 1 3 2 0 4 3 ...
r ₃ = 0, 8 2 4 5 0 2 6 ...
r ₄ = 0, 2 3 3 0 1 2 6 ...
r ₅ = 0, 4 1 0 7 2 4 6 ...
r ₆ = 0, 9 9 3 7 8 3 8 ...
r ₇ = 0, 0 1 0 5 1 3 5 ...
...

În realitate, există numere care au mai mult de o reprezentare zecimală: cele care se termină cu o succesiune infinită de 9 sau 0 au două, caz în care suntem de acord să luăm reprezentarea care se termină cu 0.

Acum să ne concentrăm atenția asupra cifre de-a lungul diagonalei matricei, adică, pe secvența a cărei K- lea element este k-lea zecimală de r _k, așa cum se arată în figură:
r ₁ = 0, 5 1 0 5 1 1 0 ... r ₁ = 0, 5 1 0 5 1 1 0 ... r ₁ = 0, 5 1 0 5 1 1 0 ...
r ₂ = 0, 4 1 3 2 0 4 3 ... r ₂ = 0, 4 1 3 2 0 4 3 ... r ₂ = 0, 4 1 3 2 0 4 3 ...
r ₃ = 0, 8 2 4 5 0 2 6 ... r ₃ = 0, 8 2 4 5 0 2 6 ... r ₃ = 0, 8 2 4 5 0 2 6 ...
r ₄ = 0, 2 3 3 0 1 2 6 ... r ₄ = 0, 2 3 3 0 1 2 6 ... r ₄ = 0, 2 3 3 0 1 2 6 ...
r ₅ = 0, 4 1 0 7 2 4 6 ... r ₅ = 0, 4 1 0 7 2 4 6 ... r ₅ = 0, 4 1 0 7 2 4 6 ...
r ₆ = 0, 9 9 3 7 8 3 8 ... r ₆ = 0, 9 9 3 7 8 3 8 ... r ₆ = 0, 9 9 3 7 8 3 8 ...
r ₇ = 0, 0 1 0 5 1 3 5 ... r ₇ = 0, 0 1 0 5 1 3 5 ... r ₇ = 0, 0 1 0 5 1 3 5 ...
...
Această secvență de cifre de pe diagonală, văzută ca o expansiune zecimală, definește un număr real 0,5140235 .... Acum să luăm în considerare un nou număr real x care are în schimb toate cifrele diferite de secvența de pe diagonală , o modalitate de a defini un astfel de număr este următoarea:
x este numărul real între 0 și 1 astfel încât
- dacă a zecea cifră zecimală a lui r _k este 5, atunci a zecea cifră a lui x este 4
- dacă a zecea cifră a lui r _k nu este 5 atunci a zecea cifră zecimală a lui x este 5
În exemplu, obținem:
x = 0, 4 5 5 5 5 5 4 ...
În realitate, există diferite moduri de definire a numerelor cu toate cifrele, altele decât diagonala, de exemplu, puteți lua următoarea cifră modulul 9, în scopul demonstrației, important este că nu putem obține un x care se termină cu un 9 periodic ( deoarece în acest caz diferența sa față de numerele enumerate în matrice ar putea fi doar aparentă).
La începutul argumentului am presupus că lista noastră { r ₁ , r ₂ , r ₃ , ...} enumeră toate numerele reale cuprinse între 0 și 1, deci ar trebui să avem r _n = x pentru unele n și din moment ce x are nr 9 între cifrele zecimale reprezentarea sa este unică. Această reprezentare unică trebuie, așadar, să fie cea prezentă în al doilea rând al tabelului.
În acest moment apare o contradicție : fie a zecea a zecimală din r _n = x. Poate fi 4 sau 5. După cum este definit x , figura a trebuie să fie 4 dacă și numai dacă este egală cu 5 și 5 dacă și numai dacă este diferită de 5. Acest lucru este imposibil și rezultă că ipoteza de pornire este fals și adică [0,1] nu poate fi numărat.

Teorema cardinalității

Ideea de mai sus pentru numerele reale poate fi generalizată pentru a arăta că este dat orice set $LA$ ${\ displaystyle A}$ $LA$ și setul său de părți ${\mathcal {P}}(A)$ ${\ displaystyle {\ mathcal {P}} (A)}$ ${\ mathcal P} (A)$ (care conține toate și numai subseturile lui A) nu poate exista o corespondență unu-la-unu între $LA$ ${\ displaystyle A}$ $LA$ Și ${\mathcal {P}}(A)$ ${\ displaystyle {\ mathcal {P}} (A)}$ ${\ mathcal P} (A)$ . Ca și înainte, credem absurd :

presupunem pentru absurditate că $f:A\to {\mathcal {P}}(A)$ ${\ displaystyle f: A \ to {\ mathcal {P}} (A)}$ $f: A \ to {\ mathcal P} (A)$ este o corespondență unu-la-unu.
să construim un subset nou $D.$ ${\ displaystyle D}$ $D.$ din $LA$ ${\ displaystyle A}$ $LA$ astfel încât acesta să nu poată fi nici unul dintre seturi $f(a)$ ${\ displaystyle f (a)}$ $face)$ pentru fiecare $a\in A$ ${\ displaystyle a \ în A}$ $a \ in A$ : cel mai evident mod este să spui asta pentru fiecare $la$ ${\ displaystyle a}$ $la$ noul subset $D.$ ${\ displaystyle D}$ $D.$ conține $la$ ${\ displaystyle a}$ $la$ dacă și numai dacă $a\notin f(a)$ ${\ displaystyle a \ notin f (a)}$ $a \ notin f (a)$ , adică $D=\{a\in A|a\notin f(a)\}$ ${\ displaystyle D = \ {a \ în A | a \ notin f (a) \}}$ $D = \ {a \ în A | a \ notin f (a) \}$ , adică $a\in D\iff a\notin f(a)$ ${\ displaystyle a \ in D \ if a \ notin f (a)}$ $a \ in D \ if a \ notin f (a)$ (care corespunde luării setului "antidiagonal")
după cum am definit $D.$ ${\ displaystyle D}$ $D.$ acest lucru nu poate fi un întreg $f(a)$ ${\ displaystyle f (a)}$ $face)$ pentru nici unul $a\in A$ ${\ displaystyle a \ în A}$ $a \ in A$ , de fapt, dacă există un $d\in A$ ${\ displaystyle d \ în A}$ $d \ în A$ pentru care $D=f(d)$ ${\ displaystyle D = f (d)}$ $D = f (d)$ am avea $d\in D=f(d)\iff d\notin f(d)$ ${\ displaystyle d \ in D = f (d) \ if d \ notin f (d)}$ $d \ in D = f (d) \ if d \ notin f (d)$ , ceea ce este o contradicție .

Observăm că în acest caz nu este posibil să „vizualizăm” ipotetica corespondență unu-la-unu (așa cum s-a întâmplat înainte) deoarece setul $LA$ ${\ displaystyle A}$ $LA$ ar putea fi de nenumărat , totuși ne putem imagina că și în acest caz $f$ ${\ displaystyle f}$ $f$ în mod ideal definiți o matrice infinită cu $|A|$ ${\ displaystyle | A |}$ $| A |$ ( cardinalitatea de $LA$ ${\ displaystyle A}$ $LA$ ) rânduri per $|A|$ ${\ displaystyle | A |}$ $| A |$ coloane, cu valorile 0 și 1 și care are câte un rând pentru fiecare $a\in A$ ${\ displaystyle a \ în A}$ $a \ in A$ compusă dintr-o succesiune de 0 și 1: 1 corespunzătoare elementelor $x\in A$ ${\ displaystyle x \ în A}$ $x \ în A$ că sunt înăuntru $f(a)$ ${\ displaystyle f (a)}$ $face)$ și 0 pentru cei care nu sunt acolo. De asemenea, în acest caz este posibil să se identifice o „diagonală” alcătuită din elementele „coordonatelor” $(a,f(a))$ ${\ displaystyle (a, f (a))}$ $(a, f (a))$ și construiți un "rând" care este opus diagonalei (adică conține un 0 pentru fiecare 1 pe diagonală și invers) și rezultatul este exact setul $D.$ ${\ displaystyle D}$ $D.$ pe care le-am definit mai sus.

Alte utilizări ale argumentului diagonal

Alte dovezi obținute prin intermediul argumentului diagonal se găsesc în principal în domeniile logicii matematice și teoriei calculabilității . Acestea sunt indecidabilitatea problemei de terminare , existența unei funcții calculabile care nu este recursivă primitivă (vezi și funcția Ackermann ), indecidibilitatea aritmeticii lui Peano și, de asemenea, în teorema Ascoli-Arzelà , se folosește. Argumentul diagonal stă la baza paradoxului lui Richard .

Constructivism și argument diagonal

Dovada de mai sus nu este constructivă: este adevărat că numărul diagonală este construit, dar presupunerea inițială de a avea o listă cu toate numerele nu construiește de fapt o astfel de listă sau, dacă preferați, nu oferă un algoritm pentru calcularea în finit timp care este poziția unui număr dat. Prin urmare, este respins de școala constructivistă . Cu toate acestea, majoritatea matematicienilor acceptă această dovadă ca fiind adevărată.

linkuri externe

Text original din 1891, cu traducere în limba engleză , pe uk.geocities.com (arhivat din original la 11 august 2006) .

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