Articles

9.3: Teorema lui Cantor și consecințele sale

abilități de dezvoltare

  • explicați teorema lui Cantor

odată ce Cantor a arătat că există două tipuri de infinit (numărabil și nenumărat), următoarea întrebare a fost firească: „toate mulțimile nenumărabile au aceeași cardinalitate?”

la fel cum nu toți „non-câinii” sunt pisici, nu există niciun motiv să credem că toate seturile nenumărate ar trebui să aibă aceeași dimensiune. Cu toate acestea construirea nenumărate seturi de diferite dimensiuni nu este la fel de ușor cum pare.

de exemplu, ce se întâmplă cu segmentul de linie reprezentat de intervalul \(\) și pătratul reprezentat de setul \ (X = \{(X,y)|0 x,y x, y x1\}\). Desigur, pătratul bidimensional trebuie să fie un set infinit mai mare decât segmentul de linie unidimensional. În mod remarcabil, Cantor a arătat că aceste două seturi erau aceeași cardinalitate. În corespondența sa din 1877 cu acest rezultat prietenului și colegului său matematician, Richard Dedekind, chiar Cantor a remarcat: „îl văd, dar nu îl cred!”

fig 9.3.1.png

figura \(\PageIndex{1}\): Richard Dedekind

următoarele oferă ideea originală a dovezii lui Cantor. Cantor a conceput următoarea funcție \(f: XV \). În primul rând,reprezentăm coordonatele oricărui punct \((x, y) XV\) prin reprezentările lor zecimale \(x = 0.a_1a_2a_3 …\ ) și \(y = 0.b_1b_2b_3….\ ) Chiar și zecimalele terminate pot fi scrise în acest fel, așa cum am putea scrie \(0,5 = 0,5000….\ ) Putem defini apoi \(f (X,y)\) prin

\

această idee relativ simplă are unele dificultăți tehnice legate de următorul rezultat.

exercițiu \(\PageIndex{1}\)

luați în considerare secvența \((0.9,0.99,0.999,…)\). Determinați că această secvență converge și, de fapt, converge la \(1\). Acest lucru sugerează că \(0.999… = 1\).

în mod similar, avem \(0,04999… = 0.05000…\ ), etc. Pentru a face reprezentarea zecimală a unui număr real în \(\) unic, trebuie să facem o alegere consistentă de a scrie o zecimală terminală ca una care se termină într-un șir infinit de zerouri sau un șir infinit de nouari . Indiferent de alegerea pe care o facem, nu am putea face niciodată această funcție. De exemplu, \(109/1100 = 0,09909090…\ ) ar avea ca pre-imagine \((0.0999…,0.9000…)\) care ar fi un amestec al celor două convenții.

Cantor a reușit să depășească această tehnicitate pentru a demonstra o corespondență unu-la-unu, dar în schimb vom observa că în oricare dintre convenții, funcția este unu-la-unu, deci aceasta spune că setul \ (inqq) este aceeași cardinalitate ca un subset (nenumărat) al \ (\mathbb{R}\). Faptul că aceasta are aceeași cardinalitate ca \(\mathbb{R}\) este ceva la care vom reveni. Dar mai întâi vom încerca să construim un set nenumărat care nu are aceeași cardinalitate ca \(\mathbb{R}\). Pentru a aborda această problemă, Cantor a dovedit următoarele în 1891.

Teorema \(\PageIndex{1}\): Teorema lui Cantor

fie \(S\) orice set. Apoi, nu există o corespondență unu-la-unu între \(s\) și \(P(S)\), setul tuturor subseturilor de \(s\).

din moment ce \(s\) poate fi pus într-o corespondență unu-la-unu cu un subset de \(P(s) (a-la-unu \{a\})\), atunci aceasta spune că \(P(S)\) este cel puțin la fel de mare ca \(s\). În cazul finit \(|P (S)|\) este strict mai mare decât \(|S/\) după cum arată următoarea problemă. De asemenea, demonstrează de ce \(P(S)\) se numește setul de putere al \(s\).

Exercițiu \(\PageIndex{2}\)

Dovedește: Dacă \(/s / = n\), atunci \(/P(S) / = 2n\)

indiciu

lasa \(s = a_1, a_2,…, a_n\). Luați în considerare următoarea corespondență între elementele \(P (S)\) și setul \(T\) al tuturor \(n\)-tupluri de da (\(Y\)) sau nu (\(N\)):

\

câte elemente sunt în \(T\)?

exercitarea \(\PageIndex{3}\)

dovedește Teorema lui Cantor.

sugestie

presupunem pentru contradicție, că există o corespondență unu-la-unu \(F: S P (S)\). Luați în considerare \(a = \{X inqq S|x \not {inqq f(x)\}\). Din moment ce \(f\) este pe, atunci există \(un a\) astfel încât \(a = f (a)\). Este \ (a (A) A\) sau este \(a\nu {(a)} a\)?

de fapt se dovedește că \(\mathbb{R}\) și \(P(\mathbb{N})\) au aceeași cardinalitate. Acest lucru poate fi văzut într-un sens giratoriu folosind unele dintre ideile de mai sus din Exercise \(\PageIndex{2}\). Mai exact, lăsați \(T\) să fie setul tuturor secvențelor de zerouri sau unu (puteți utiliza \(Y\)s sau \(N\)S, Dacă preferați). Atunci este simplu să vedem că \(T\) și \(P(\mathbb{N})\) au aceeași cardinalitate.

dacă luăm în considerare \((0,1]\), care are aceeași cardinalitate ca \(\mathbb{R}\), atunci putem vedea că aceasta are aceeași cardinalitate ca \(T\) de asemenea. Mai exact, dacă ne gândim la numerele din binar, atunci fiecare număr real din \(\) poate fi scris ca \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots )\) unde \(a_j_c_{0,1\}\). Trebuie să luăm în considerare faptul că reprezentările binare, cum ar fi \(0.0111…\ ) și \(0.1000…\ ) reprezintă același număr real (spuneți că nicio reprezentare nu se va termina într – un șir infinit de zerouri), atunci putem vedea că \ ( \ ) are aceeași cardinalitate ca \(T-U\), unde \(U\) este mulțimea tuturor secvențelor care se termină într-un șir infinit de zerouri. Se pare că \(U\) în sine este un set numărabil.

exercițiu \(\PageIndex{4}\)

fie \(U_n = \{(a_1, a_2, a_3,…) / a_j(a_j) \{0,1\}\) și \(a_{n+1} = a_{n+2} = ··· = 0\}\). Arătați că pentru fiecare \(n\), \(U_n\) este finit și utilizați acest lucru pentru a concluziona că \(U\) este infinit numărabil.

următoarele două probleme arată că ștergerea unui set numărabil dintr-un set nenumărat nu schimbă cardinalitatea acestuia.

exercițiu \(\PageIndex{5}\)

fie \(s\) un set infinit. Dovedește că \(s\) conține un subset infinit numărabil.

exercitarea \(\PageIndex{6}\)

să presupunem că \(X\) este un set nenumărat și \(Y X X\) este infinit numărabil. Dovediți că \(X\) și \(X – Y\) au aceeași cardinalitate.

Sugestie

Lasa \(Y = Y_0\). Dacă \(X-Y_0\) este un set infinit, atunci prin problema anterioară conține un set infinit numărabil \(Y_1\). De asemenea, dacă \(X – (Y_0 Y_1)\) este infinit conține, de asemenea, un set infinit \(Y_2\). Din nou, dacă \(X – (Y_0 Y_1 Y_1 Y_2)\) este un set infinit, atunci acesta conține un set infinit \(Y_3\), etc. Pentru \(n = 1,2,3,…,\) fie \(f_n: Y_{n-1} y_n\) o corespondență unu-la-unu și să definească \(f : X X – Y X X-Y\) prin

\

arată că \(f\) este unu-la-unu și pe.

problemele de mai sus spun că \(R\), \(T – U\), \(T\), și \(P(N)\) toate au aceeași cardinalitate.

după cum s-a indicat anterior, lucrarea lui Cantor asupra mulțimilor infinite a avut un impact profund asupra matematicii la începutul secolului al XX-lea. De exemplu, examinând dovada teoremei lui Cantor, eminentul logician Bertrand Russell și-a conceput faimosul paradox în 1901. Înainte de acest timp, un set a fost gândit naiv ca doar o colecție de obiecte. Prin opera lui Cantor și a altora, mulțimile deveneau un obiect central de studiu în matematică, deoarece multe concepte matematice erau reformulate în termeni de mulțimi. Ideea era că teoria mulțimilor urma să fie o temă unificatoare a matematicii. Acest paradox a pus lumea matematică la ureche.

Paradoxul lui Russell

luați în considerare mulțimea tuturor mulțimilor care nu sunt elemente ale lor. Noi numim acest set \(D\) și ne întrebăm: „Este \(D D\)?”Simbolic, acest set este

\

în cazul în care\ (D Inqc D\), atunci prin definiție, \(d \ not {inqc} D\). În cazul în care D 6 CTF D, atunci prin definiție, \(D CTF D\).

dacă te uiți înapoi la dovada teoremei lui Cantor, aceasta a fost practic ideea care ne-a dat contradicția. A avea o astfel de contradicție la nivelul cel mai de bază al matematicii a fost scandalos. A forțat un număr de matematicieni și logicieni să elaboreze cu atenție axiomele prin care ar putea fi construite seturile. Pentru a fi sincer, majoritatea matematicienilor încă abordează teoria mulțimilor dintr-un punct de vedere naiv, deoarece mulțimile cu care avem de-a face de obicei se încadrează în categoria a ceea ce am numi „mulțimi normale.”De fapt, o astfel de abordare este numită oficial teoria mulțimilor Naive (spre deosebire de teoria mulțimilor axiomatice). Cu toate acestea, încercările de a pune teoria și logica mulțimilor pe o bază solidă au dus la studiul modern al logicii simbolice și, în cele din urmă, la proiectarea logicii computerului (mașinii).

un alt loc în care opera lui Cantor a avut o influență profundă în logica modernă provine din ceva la care am făcut aluzie înainte. Am arătat mai înainte că unitatea pătrată \ (inqq) avea aceeași cardinalitate ca un subset nenumărat de \ (\mathbb{R}\). De fapt, Cantor a arătat că pătratul unității avea aceeași cardinalitate ca \(\mathbb{R}\) în sine și a fost mutat pentru a avansa următoarele în 1878.

conjectura (ipoteza continuumului)

fiecare subset nenumărat de \(\mathbb{R}\) are aceeași cardinalitate ca \(\mathbb{R}\).

Cantor nu a putut dovedi sau infirma această presupunere (împreună cu orice alt matematician). De fapt, dovedirea sau infirmarea acestei presupuneri, care a fost supranumită ipoteza continuumului, a fost una dintre celebrele probleme ale lui Hilbert \(23\) prezentate ca o provocare pentru matematicieni la Congresul Internațional al Matematicienilor din 1900.

deoarece \ (\mathbb{R}\) are aceeași cardinalitate ca \(P (N)\), atunci ipoteza continuumului a fost generalizată la:

conjectura(ipoteza continuumului generalizat)

dat fiind un set infinit \(s\), nu există un set infinit care să aibă o cardinalitate strict între cel al lui \(s\) și setul său de putere \(P(S)\).

eforturile de a dovedi sau infirma acest lucru au fost în zadar și cu un motiv bun. În 1940, logicianul Kurt G a arătat că ipoteza continuumului nu poate fi respinsă din axiomele Zermelo-Fraenkel ale teoriei mulțimilor 1. În 1963, Paul Cohen a arătat că ipoteza continuumului nu a putut fi dovedită folosind axiomele Zermelo-Fraenkel. Cu alte cuvinte, axiomele Zermelo-Fraenkel nu conțin suficiente informații pentru a decide adevărul ipotezei.

suntem dispuși să pariem că în acest moment capul tău ar putea înota un pic de incertitudine. Dacă da, atunci știți că acestea sunt aceleași sentimente pe care comunitatea matematică le-a experimentat la mijlocul secolului al XX-lea. În trecut, matematica era văzută ca un model de certitudine logică. Este deconcertant să constatăm că există afirmații care sunt ” indecidabile.”De fapt, Gh a demonstrat în 1931 că un sistem consistent de axiome finite care conținea axiomele aritmeticii ar conține întotdeauna afirmații nedecidabile care nu puteau fi dovedite nici adevărate, nici false cu acele axiome. Cunoștințele matematice ar fi întotdeauna incomplete.

fig 9.3.2.png

Figure \(\PageIndex{2}\): Kurt G Inktdel

deci, încercând să punem bazele calculului pe un teren solid, am ajuns la un punct în care nu putem obține niciodată certitudine matematică. Asta înseamnă că ar trebui să ne aruncăm mâinile și să recunoaștem înfrângerea? Ar trebui să fim paralizați de teama de a încerca ceva? Cu siguranță nu! După cum am menționat anterior, majoritatea matematicienilor se descurcă bine adoptând o abordare pragmatică: folosindu-și matematica pentru a rezolva problemele cu care se confruntă. De fapt, este de obicei problemele care motivează matematica. Este adevărat că matematicienii își asumă riscuri care nu ies întotdeauna în evidență, dar totuși își asumă aceste șanse, adesea cu succes. Chiar și atunci când succesele duc la mai multe întrebări, așa cum fac de obicei, abordarea acestor întrebări duce de obicei la o înțelegere mai profundă. Cel puțin, înțelegerea noastră incompletă înseamnă că vom avea întotdeauna mai multe întrebări de răspuns, mai multe probleme de rezolvat.

ce altceva ar putea cere un matematician?