Mulțimi numărabile

Numărabilitatea unei mulțimi este un fel de echivalent al mărimii mulțimilor, pentru că la mulțimile infinite nu putem vorbi de numărul de elemente: numărul de elemente este, în mod surprinzător, … infinit. Mărimea unei mulțimi se mai numește și cardinal.

Mărimea unei mulțimi infinite

Mărimea unei mulțimi finite se stabilește simplu: numărăm elementele. Astfel, mulțimea M = {a, b, c, d, e} are mărimea 5, ceea ce scriem |M| = 5.

La mulțimile infinite situația este mult mai complicată. Cum am putea compara mărimea unor mulțimi infinite? Se poate oare, sau toate mulțimile infinite sunt „la fel de mari”?

Să luăm ca exemplu mulțimea numerelor naturale și mulțimea numerelor naturale pare. Pentru ce urmează lucrăm cu numerele naturale nenule (în România ℕ îl include și pe 0, deci mulțimea de mai jos este ℕ^∗). Avem mulțimile ℕ^∗ = {1, 2, 3, 4, 5, 6, …} și S = {2, 4, 6, …}. Ar părea firesc să spunem că mulțimea numerelor naturale este mai mare decât mulțimea numerelor pare, pentru că numerele naturale conțin toate numerele pare și, în plus, încă niște elemente – numerele impare.

Am putea deci scrie că S ⊂ ℕ^∗, adică S este submulțime proprie a mulțimii ℕ^∗. Și am putea spune că, dacă S ⊂ ℕ^∗, atunci mulțimea ℕ^∗ este mai mare – conține totuși mai multe elemente decât mulțimea S.

Unul dintre motivele pentru care nu putem măsura mulțimile după relația de incluziune este că mulțimile pot avea mărimi diferite chiar dacă niciuna nu este submulțime a celeilalte. Se vede asta și la mulțimi finite: A = {1, 3, 4, 9} și B = {b, u, r, z, m}. Avem |A| = 4 și |B| = 5. Mulțimea B este mai mare decât mulțimea A, și totuși nu are loc A ⊂ B. În cazul mulțimilor infinite putem vedea același lucru la numerele pare și impare: niciuna dintre mulțimi nu este submulțime a celeilalte.

Incluziunea nu este, așadar, un criteriu potrivit pentru a decide dacă o mulțime este mai mare decât alta.

Bijecția

Să încercăm altă abordare. Avem două mulțimi, A și B. Putem spune că au aceeași mărime dacă între ele există o funcție bijectivă. Ce înseamnă asta? Luăm un element din mulțimea A, un element din mulțimea B și formăm perechea (a, b). Scoatem aceste elemente din mulțimi și continuăm. Dacă reușim să „golim” ambele mulțimi, am găsit o funcție bijectivă.

Exemplu pe mulțimi finite: A = {a, b, c} și B = {1, 2, 3}. Prima pereche ar putea fi (a, 1), apoi (b, 2) și, în final, (c, 3). Am epuizat toate elementele din ambele mulțimi, deci am găsit o funcție bijectivă. Important este că aceasta nu este singura funcție bijectivă. Și aceasta este o soluție validă: (a, 3), (b, 1), (c, 2).

La mulțimile infinite lucrurile devin ceva mai interesante. Să încercăm cu numerele naturale impare și pare. Intuitiv simțim că ar trebui să fie tot atâtea. Să verificăm. Luăm primul număr impar și îl asociem primului număr par: (1, 2). Apoi al doilea impar cu al doilea par: (3, 4). Și așa mai departe. Obținem perechile (1, 2), (3, 4), (5, 6), (7, 8), … Am putea scrie că fiecare număr impar l se asociază numărului par l + 1, iar fiecare număr par s este imaginea numărului impar s − 1. Pentru fiecare număr impar și pentru fiecare număr par avem astfel o pereche care îl conține. Mulțimile numerelor impare și pare au deci aceeași mărime.

Numerele pare și numerele naturale

Acum aplicăm aceeași metodă și comparăm mulțimea numerelor naturale cu cea a numerelor pare. Avem mulțimile ℕ^∗ = {1, 2, 3, 4, 5, 6, …} și S = {2, 4, 6, …}. Ne așteptăm intuitiv ca mulțimea numerelor naturale să fie mai mare.

Să încercăm totuși să găsim funcția bijectivă. Putem spune că fiecare număr natural nenul n se asociază dublului său, adică lui 2n. Obținem perechile (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … Pentru fiecare număr natural nenul n avem astfel perechea (n, 2n), iar pentru fiecare număr par s avem perechea (s/2, s). Am găsit o funcție bijectivă, deci mulțimea numerelor pare și mulțimea numerelor naturale au aceeași mărime, același cardinal.

Poate părea derutant, pentru că numerele naturale conțin totuși mai multe elemente decât numerele pare. Numerele naturale conțin toate numerele pare și, în plus, toate numerele impare. Cu toate acestea, am găsit o bijecție, deci cele două mulțimi sunt la fel de mari.

Comparația cu numerele naturale

De fapt, numerele naturale dau cea mai mică mărime a unei mulțimi infinite. Dacă o altă mulțime are aceeași mărime ca mulțimea numerelor naturale se poate afla adesea destul de ușor – este suficient să găsim o bijecție cu numerele naturale, ceea ce în practică înseamnă că este suficient să putem numerota, ordona elementele mulțimii noastre M.

Așadar, dacă putem aranja elementele unei mulțimi astfel încât să știm care este primul, care al doilea, al treilea, al patrulea, al zecelea etc., atunci mulțimea are aceeași mărime ca ℕ. O astfel de mulțime se numește numărabilă.

Vedem ușor că numerele naturale pare și impare formează mulțimi numărabile, pentru că putem spune care este primul, al doilea, al treilea etc. număr par/impar. Dar numerele întregi pare? Adică mulțimea S = {…, −4, −2, 0, 2, 4, …}. Le putem ordona? Da, e suficient să luăm aceeași ordonare ca mai înainte și să scriem imediat după fiecare număr par pozitiv și opusul său: S = {0, 2, −2, 4, −4, 6, −6, …}. La fel procedăm, de exemplu, pentru numerele întregi.

Mărimea mulțimii numerelor raționale

Un exemplu mai interesant sunt numerele raționale, fracțiile. Le putem ordona? Da, dar va fi ceva mai complicat. Construim un tabel cu o infinitate de linii și coloane. În fiecare celulă va fi o fracție. În coloana a n-a și linia a m-a vom avea fracția n/m. Așadar, în coloana 1 și linia 2 avem $\frac{1}{2}$, iar în coloana a treia și linia a patra avem 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Cum le ordonăm acum, cum le numerotăm? Nu le putem numerota pe linii sau pe coloane, pentru că ne-am „îneca” imediat în linia/coloana respectivă. În schimb luăm numerele pe diagonale: (prima diagonală:) 1/1, (a doua diagonală:) 2/1, 1/2, (a treia diagonală:) 3/1, 2/2, 1/3, (a patra diagonală:) 4/1, 3/2, 2/3, 1/4, … Mai sunt încă multe fracții care se repetă, dar asta nu deranjează. Mai supărător este că nu avem numere negative. Se rezolvă simplu: de fiecare dată când scriem o fracție, punem imediat după ea opusa ei. Apoi ne lipsește doar zero, chiar de la început. Și gata, avem toate numerele raționale într-un șir.

În total obținem șirul: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Mărimea mulțimii numerelor reale

Sunt numerele reale tot atât de multe ca numerele naturale? Decizia va fi și mai grea decât în cazul numerelor raționale. Vom face o demonstrație prin reducere la absurd. Presupunem că numerele reale sunt numărabile și că există o funcție bijectivă către numerele naturale. Adică presupunem că pot fi ordonate. Și să zicem că următorul tabel este acea ordonare:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

În tabel sunt primele șapte numere reale din ordonarea noastră. Evident, ordonarea poate fi oricare, nu trebuie să fie în ordinea crescătoare a valorilor.

Conform ipotezei, în acest tabel infinit sunt ordonate toate numerele reale. (Tabelul este din nou infinit, aici sunt doar primele șapte rânduri.) Acum vom încerca să găsim/construim un număr real care nu apare în tabel. Dacă găsim un astfel de număr, obținem o contradicție cu faptul că în tabel sunt toate numerele reale, din care putem trage concluzia că mulțimea numerelor reale nu este numărabilă.

Numărul care nu se află în tabel îl construim astfel:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Începem scriind 0,… Așa va arăta la început noul nostru număr real. La prima zecimală va fi o cifră care nu este cifra de pe prima poziție a primului număr real din ordonarea noastră (în tabel este încadrată). Acolo este cifra 3, așa că alegem, de exemplu, 1 și obținem numărul 0,1…

Continuăm. La a doua zecimală va fi o cifră care nu este cifra de pe a doua poziție a celui de-al doilea număr real. Acolo este 9, deci, de exemplu, 2. Obținem numărul 0,12… La a treia zecimală va fi o cifră diferită de a treia cifră a celui de-al treilea număr real. Acolo este 3, deci alegem, să zicem, 7. Obținem 0,127…

Și așa mai departe. Pe poziția a n-a a noului număr va fi mereu o cifră diferită de cifra aflată pe poziția a n-a a numărului al n-lea din ordonarea noastră.

Ce obținem astfel? Obținem un număr care se deosebește de toate numerele din ordonarea noastră prin cel puțin o cifră. Să luăm ultimul rezultat provizoriu: 0,127… Acest număr se deosebește cu siguranță de primul număr din ordonarea noastră cel puțin prin prima cifră – pentru că l-am construit așa. De al doilea număr se deosebește cel puțin prin a doua cifră. De al treilea, prin a treia cifră. În general, noul număr se deosebește de numărul aflat pe locul al n-lea în ordonare cel puțin prin cifra de pe poziția a n-a.

Prin urmare, acest număr nou construit nu se află în tabelul care trebuia să reprezinte bijecția dintre numerele naturale și numerele reale. Numerele reale sunt deci mai multe decât cele naturale. Numerele reale nu sunt numărabile, sunt nenumărabile.

Alte surse

• Are there more odd or even numbers?