Set numărabil

O mulțime numărabilă este o mulțime infinită ale cărei elemente pot fi numerotate prin numere naturale . Mai formal: o mulțime este numărabilă dacă există o bijecție cu o mulțime de numere naturale: cu alte cuvinte, o mulțime numărabilă este o mulțime care este echivalentă în putere cu mulțimea de numere naturale. În ierarhia alefelor , cardinalitatea unui set numărabil este notă ("aleph-zero"). $X$ $X\leftrightarrow \mathbb {N}$ $\aleph _{0}$

Proprietăți

O mulțime numărabilă este „cea mai simplă” mulțime infinită în următorul sens: în orice mulțime infinită există o submulțime numărabilă . Într-adevăr, vom alege aleatoriu elemente dintr-o mulțime infinită și vom asocia numere cu ele.Deoarece mulțimea este infinită, pentru orice natural există un element în ea de comparat cu numărul , din care, prin principiul inducției , submulțimea construită. va fi bijectiv cu . $1,\,2,\,3,\,\ldots$ $n$ $n+1$ $\mathbb {N}$

În plus, fiecare submulțime a unei mulțimi numărabile este fie finită, fie numărabilă (nu mai mult decât numărabilă). Enumerăm elementele mulțimii inițiale prin numere naturale, ceea ce este posibil, deoarece este numărabil. Pentru fiecare element, știm dacă se află sau nu în submulțimea noastră. Parcurgând acestea în ordine, dacă elementul următor nu se află în submulțime, îl vom sări peste el; dacă minte, atribuiți-i următorul număr (să începem numerotarea cu ). După principiul inducției, o submulțime va fi echivalentă dacă nu este finită. Rețineți că, sortând în ordine, dintre elementele deja luate în considerare, nu am ratat niciunul. $unu$ $\mathbb {N}$

De asemenea, o uniune cel mult numărabilă (finită sau numărabilă) a cel mult mulțimi numărabile este cel mult o mulțime numărabilă . Enumerăm elementele mulțimilor combinate (setați o bijecție cu ). Dacă există un număr finit de mulțimi inițiale , vom numerota elementele — uniunile lor: Este ușor de observat din inducție că se stabilește o bijecție cu . În cazul unei uniri infinite, această regulă nu se aplică, dar este posibilă o numerotare similară. Poate fi vizualizat după cum urmează (o concluzie ulterioară, totuși, poate fi formalizată): să scriem elementele fiecărei mulțimi (ordonate după numere) într-o coloană. Să facem un tabel din acestea, ale cărui coloane definesc fiecare set inclus în unire, iar rândurile - anumite numere ale fiecăruia dintre ele. Din colțul din stânga sus, vom deveni un șarpe pentru a ocoli întregul tabel, numerotând fiecare celulă pe drum. Prin inducție, ocolim întreaga masă și uniunea rezultată se dovedește a fi numărabilă. În general, masa în sine va trebui să fie „construită” de același șarpe, deoarece este infinită. Elementele mulțimilor finite pot fi întotdeauna atribuite primele, deplasând astfel numerotarea cu un anumit număr. $\mathbb {N}$ $A,\,B,\,C,\,\ldots$ $n$ $S$ $s_{1}=a_{1},\;s_{2}=b_{1},\;\ldots ,\;s_{n+1}=a_{2},\;s_{n+ 2 }=b_{2},\;\ldots$ $\mathbb {N}$

De asemenea, este ușor să arătăm că produsul direct al unui număr finit de nu mai mult de mulțimi numărabile nu este mai mult decât numărabil . Luați în considerare produsul a două mulțimi, numărătoarea acestuia este stabilită prin numerotarea tabelului similar cu cea de mai sus, ale cărui rânduri sunt elementele unui set și coloanele celuilalt. Produsul unui număr finit de mulțimi este împărțit în factori, fiecare dintre care va fi produsul multimii multiplicatoare inițiale și produsul cartezian a două mulțimi. Să extindem produsul final de la sfârșit: să numerotăm produsul a două mulțimi, elementele uneia dintre ele vor fi obținute prin numerotarea produsului a două mulțimi „intrat”, elementele uneia dintre ele vor fi obținute în același mod . Să continuăm de-a lungul recursiunii, care nu se va închide, deoarece există un număr finit de mulțimi. Rețineți că toate numerele vor trebui căutate prin inducție, completând secvențial plăcuțele necesare în locurile potrivite.

În cele din urmă , dacă adăugăm o mulțime finită sau numărabilă la o mulțime infinită, atunci obținem o mulțime care este echivalentă cu originalul [1] . Valabilitatea afirmației este ușor de arătat dacă alegem un submult numărabil în setul original . Astfel, . Atașarea la cel mult setul numărabil nu schimbă cardinalitatea acestuia, deci pentru cel mult setul numărabil este adevărat: . $A$ $B$ $A=(A\setminus B)\cup B\;\leftrightarrow (A\setminus B)\cup \mathbb {N}$ $B$ $C$ $A\cup C=(A\setminus B)\cup (B\cup C)\;\leftrightarrow (A\setminus B)\cup \mathbb {N} \;\leftrightarrow A$

Rețineți că mulțimea tuturor submulților finite ale unei mulțimi numărabile este numărabilă . Mulțimea de submulțimi finite de elemente este numărabilă, deoarece este o submulțime a produsului cartezian al mulțimilor originale. Mulțimea tuturor submulților finite este unirea submulților finite cu un anumit număr de elemente (care sunt numărabile), adică numărătoare. $n$ $n$

Totuși, mulțimea tuturor submulțimii unei mulțimi numărabile este continuă și nu este numărabilă . Să arătăm faptul într-un sens mai general că nu există nicio bijecție între o anumită mulțime și mulțimea tuturor submulțimii sale. Să presupunem contrariul. Alegem setul tuturor elementelor setului original care nu sunt asociate cu seturile care se conțin. Acesta, desigur, este un element al mulțimii tuturor submulților. Nu poate fi comparat cu niciun element care se află în el pe o parte (prin definiție), precum și cu orice element care nu se află în el pe cealaltă parte (pentru că, altfel, un astfel de element s-ar afla deja în el). Astfel, mulțimea pe care am construit-o este goală, dar submulțimile care conțin un anumit element sunt întotdeauna mai multe; Aceasta înseamnă că corespondența nu este unu-la-unu. O contradicție înseamnă că presupunerea existenței unei bijecții este incorectă.

Exemple

Numărabile sunt mulțimile de numere naturale $\mathbb {N}$ , numere întregi $\mathbb {Z}$ , numere raționale $\mathbb {Q}$ , numere algebrice $\mathbb {A}$ . Numărabile sunt obiecte rezultate din proceduri recursive , în special, acestea sunt numere calculabile , numere aritmetice (în consecință, inelul de perioade este și numărabil , deoarece fiecare perioadă este calculabilă ). Setul tuturor cuvintelor finite peste un alfabet numărabil și setul tuturor cuvintelor peste un alfabet finit sunt numărabile. Orice obiecte care pot fi definite cu o comparație unu-la-unu cu o mulțime numărabilă sunt numărabile, de exemplu: orice familie infinită de intervale deschise care nu se intersectează pe axa reală; mulţimea tuturor dreptelor din plan , fiecare dintre ele conţinând cel puţin două puncte cu coordonate raţionale ; orice set infinit de puncte din plan, toate distanțele perechi dintre elementele cărora sunt raționale.

O mulțime nenumărabilă este o mulțime atât de infinită care nu este numărabilă, cum ar fi, în special, mulțimile de numere reale $\mathbb {R}$ , numere complexe $\mathbb {C}$ , cuaternioni , numere Cayley . Astfel, orice mulțime poate fi numită fie finită, fie numărabilă, fie nenumărabilă. $\mathbb {H}$ $\mathbb O$

Fapte interesante

La prima vedere, pare imposibil să se stabilească o corespondență unu-la-unu între, să zicem , și , deoarece elementele celui de-al doilea set, s-ar părea, sunt de două ori mai multe. Dar aici avem de-a face cu percepția noastră asupra conceptului de infinit , ca ceva care nu are sfârșit. Puteți încerca să percepeți acest fapt pe următorul exemplu, absurd într-un sens. $\mathbb {N}$ $\mathbb {Z}$

Să ne imaginăm că a fost construit un hotel cu un număr infinit de camere pentru o ședință a consiliului galactic și s-a întâmplat ca toate camerele să fie ocupate. În acel moment, au sosit diplomații care trebuiau relocați. Deoarece există un număr de camere de hotel și rezidenți înșiși, vom propune următoarea strategie pentru relocarea noilor veniți. Să mutăm oaspeții din camera -a în -a, locuind în -a în -a și apoi în ordine. În primele camere eliberate, de fapt, îi vom găzdui pe cei sosiți. Hotelul, întrucât a fost ocupat în totalitate, va rămâne însă așa. După cum se dovedește, nu erau locuri libere. O contradicție se găsește în reprezentarea infinitului ca o anumită finitate. Cu toate acestea, infinitul se caracterizează tocmai prin absența sfârșitului său, cu alte cuvinte, infinitul cu adăugarea unui capăt este exact același infinit. $n$ $unu$ $(n+1)$ $2$ $(n+2)$ $n$

De asemenea, este posibil să se înfășoare într-o formă destul de elegantă dovada absenței unei bijecții între o anumită mulțime și mulțimea tuturor submulțimii sale. Să-i numim pe primul un set de oameni (se poate presupune că acțiunile au loc în aceeași galaxie), iar pe al doilea o societate. Să presupunem că în fiecare societate există un (și unicul) reprezentant care îl reprezintă doar pe el. Să-i numim eroi pe cei care reprezintă o societate din care nu aparțin. Se pare că un erou nu poate reprezenta toți eroii. Dar nici un non-erou nu poate face asta, pentru că, săvârșind o astfel de faptă eroică, ar deveni un erou. Prin urmare, nu au existat eroi în galaxie, altfel presupunerea noastră este greșită. Dar nu orice societate se poate descurca fără un erou, așa că presupunerea noastră este cu siguranță greșită. Se dovedește că nu există bijecție

Note

↑ Brudno, 1971 , p. paisprezece.

Literatură

Brudno A. L. Teoria funcțiilor unei variabile reale. - M. : Nauka, 1971. - 119 p.