În matematică și mai ales în teoria mulțimilor , se spune că o mulțime poate fi numărată dacă elementele sale au un număr finit sau dacă pot fi plasate într-o corespondență unu-la-unu cu numere naturale .
Dacă o mulțime numărabilă are un număr infinit de elemente, se numește infinit numărabil și, din moment ce poate fi pus într-o corespondență unu-la-unu cu numere naturale, putem spune că o mulțime este infinită numărabilă dacă are cardinalitatea de {\ displaystyle \ mathbb {N}} . Cardinalitatea mulțimilor infinite numărabile este de obicei notată prin simbol {\ displaystyle \ aleph _ {0}} .
Se poate arăta că fiecare subset infinit al unui set numărabil este, de asemenea, numărabil și că fiecare set infinit conține un subset numărabil.
Exemple de mulțimi numărabile sunt mulțimea numerelor întregi și mulțimea numerelor raționale . Cel mai simplu exemplu de set de nenumărate este dat de mulțimea numerelor reale al căror număr nu a fost demonstrat mai întâi de Cantor prin argumentul său diagonal .
Definiție
Un set {\ displaystyle S} se spune că poate fi numărat dacă există o funcție injectivă
- {\ displaystyle f \ colon S \ to \ mathbb {N}}
din {\ displaystyle S} la mulțimea numerelor naturale {\ displaystyle \ mathbb {N} = \ {0,1,2,3, \ ldots \}.} [1]
De sine {\ displaystyle f} este, de asemenea, o funcție surjectivă (prin urmare {\ displaystyle f} Este bijectiv ), atunci {\ displaystyle S} se numește un set infinit numărabil .
Această terminologie nu este universală: unii autori definesc o mulțime numărabilă astfel încât să nu includă mulțimi finite, definind astfel doar corespondența cu o funcție unu-la-unu (considerat aici ca un caz special și numit infinit numărabil).
Alte definiții
Definiții alternative, dar echivalente, ale unui set numărabil pot fi date, în termeni de funcții bijective sau surjective, datorită unor teoreme. O demonstrație a acestora poate fi găsită în textele lui Lang. [2]
Diferitele teoreme care demonstrează echivalența definițiilor alternative într-una pot fi rezumate. Este {\ displaystyle S} un set. Următoarele afirmații sunt echivalente:
- {\ displaystyle S} este numărabil, adică există o funcție injectivă
- {\ displaystyle f \ colon S \ to \ mathbb {N}}
- {\ displaystyle S} este setul gol sau există o funcție surjectivă
- {\ displaystyle g \ colon \ mathbb {N} \ to S}
- {\ displaystyle S} este finit sau există o bijecție
- {\ displaystyle h \ colon \ mathbb {N} \ to S}
Ansamblul numerelor raționale
Pentru a demonstra că mulțimea numerelor raționale este numărabilă (ne limităm la raționalele pozitive, deși generalizarea este banală), observăm că toate raționalele pozitive pot fi scrise sub forma {\ displaystyle {\ tfrac {a} {b}}} cu {\ displaystyle a} Și {\ displaystyle b} numere întregi pozitive. Putem crea următorul tabel de fracții {\ displaystyle {\ tfrac {a} {b}}} :
- {\ displaystyle {\ begin {matrix} {\ tfrac {1} {1}} & {\ tfrac {2} {1}} & {\ tfrac {3} {1}} & {\ tfrac {4} {1 }} & {\ tfrac {5} {1}} & \ dots \\ {\ tfrac {1} {2}} & {\ tfrac {2} {2}} & {\ tfrac {3} {2}} & {\ tfrac {4} {2}} & {\ tfrac {5} {2}} & \ dots \\ {\ tfrac {1} {3}} & {\ tfrac {2} {3}} & { \ tfrac {3} {3}} & {\ tfrac {4} {3}} & {\ tfrac {5} {3}} & \ dots \\ {\ tfrac {1} {4}} & {\ tfrac {2} {4}} & {\ tfrac {3} {4}} & {\ tfrac {4} {4}} & {\ tfrac {5} {4}} & \ dots \\ {\ tfrac {1 } {5}} & {\ tfrac {2} {5}} & {\ tfrac {3} {5}} & {\ tfrac {4} {5}} & {\ tfrac {5} {5}} și \ dots \\\ dots & \ dots & \ dots & \ dots & \ dots & \ end {matrix}}}
Pentru a construi o funcție unu-la-unu cu numere naturale, se poate proceda în diagonală după cum urmează:
- {\ displaystyle {\ begin {matrix} {\ tfrac {1} {1}} && {\ tfrac {2} {1}} && {\ tfrac {3} {1}} && {\ tfrac {4} {1 }} && {\ tfrac {5} {1}} & \ dots \\ {\ tfrac {1} {2}} & ^ {\ nearrow} & {\ tfrac {2} {2}} & ^ {\ nearrow } & {\ tfrac {3} {2}} & ^ {\ nearrow} & {\ tfrac {4} {2}} & ^ {\ nearrow} & {\ tfrac {5} {2}} & \ dots \ \ {\ tfrac {1} {3}} & ^ {\ nearrow} & {\ tfrac {2} {3}} & ^ {\ nearrow} & {\ tfrac {3} {3}} & ^ {\ nearrow } & {\ tfrac {4} {3}} && {\ tfrac {5} {3}} & \ dots \\ {\ tfrac {1} {4}} & ^ {\ nearrow} & {\ tfrac {2 } {4}} & ^ {\ nearrow} & {\ tfrac {3} {4}} && {\ tfrac {4} {4}} && {\ tfrac {5} {4}} & \ dots \\ { \ tfrac {1} {5}} & ^ {\ nearrow} & {\ tfrac {2} {5}} && {\ tfrac {3} {5}} && {\ tfrac {4} {5}} && { \ tfrac {5} {5}} & \ dots \\\ dots && \ dots && \ dots && \ dots && \ dots & \ end {matrix}}}
Astfel, se obține următoarea listă:
- {\ displaystyle {\ frac {1} {1}}, \ {\ frac {1} {2}}, \ {\ frac {2} {1}}, \ {\ frac {1} {3}}, \ {\ frac {2} {2}}, \ {\ frac {3} {1}}, \ {\ frac {1} {4}}, \ {\ frac {2} {3}}, \ { \ frac {3} {2}}, \ {\ frac {4} {1}}, \ {\ frac {1} {5}}, \ {\ frac {2} {4}}, \ {\ frac {3} {3}}, \ {\ frac {4} {2}}, \ {\ frac {5} {1}}, \ dots}
Dacă eliminăm din această listă fracțiile care nu se află în fund, rămânem cu următoarea secvență :
- {\ displaystyle {\ begin {array} {cccccccccccc} 1, & {\ tfrac {1} {2}}, & 2, & {\ tfrac {1} {3}}, & 3, & {\ tfrac {1 } {4}}, & {\ tfrac {2} {3}}, & {\ tfrac {3} {2}}, & 4, & {\ tfrac {1} {5}}, & 5, & \ puncte \\\ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \ dots \ end {array}}}
care conține exact toate numerele raționale. Cu toate acestea, această succesiune nu respectă ordinea numerelor raționale (adică nu este sigur că, între două numere care apar consecutiv în această listă, al doilea este cel mai mare); într-adevăr, este imposibil să construim o listă completă de numere raționale care să le respecte ordinea.
Produs cartezian al seturilor numărabile
Cu aceeași tehnică utilizată pentru setul de numere raționale, putem demonstra că dacă {\ displaystyle A} Și {\ displaystyle B} produsul cartezian este, de asemenea, două seturi numărabile {\ displaystyle A \ times B} este un set numărabil și mai general produsul cartezian al unui număr finit de seturi numărabile este, de asemenea, un set numărabil.
Demonstrație
De cand {\ displaystyle A} este un set numărabil care poate fi pus în corespondență unu-la-unu cu mulțimea numerelor naturale și, prin urmare, elementele lui {\ displaystyle A} poate fi indexat după cum urmează:
- {\ displaystyle a_ {1}, \ a_ {2}, \ a_ {3}, \ a_ {4}, \ a_ {5}, \ dots}
și același lucru este valabil pentru întreg {\ displaystyle B} :
- {\ displaystyle b_ {1}, \ b_ {2}, \ b_ {3}, \ b_ {4}, \ b_ {5}, \ dots}
Amintiți-vă că produsul cartezian {\ displaystyle A \ times B} este mulțimea formată din toate elementele tipului {\ displaystyle (a, b)} cu {\ displaystyle a} aparținând {\ displaystyle A} Și {\ displaystyle b} aparținând {\ displaystyle B} . Apoi puteți aranja elementele {\ displaystyle A \ times B} într-un mod similar cu cel folosit pentru elementele de {\ displaystyle \ mathbb {Q}} :
- {\ displaystyle {\ begin {matrix} (a_ {1}, b_ {1}) & (a_ {2}, b_ {1}) & (a_ {3}, b_ {1}) & (a_ {4} , b_ {1}) & (a_ {5}, b_ {1}) & \ dots \\ (a_ {1}, b_ {2}) & (a_ {2}, b_ {2}) & (a_ { 3}, b_ {2}) & (a_ {4}, b_ {2}) & (a_ {5}, b_ {2}) & \ dots \\ (a_ {1}, b_ {3}) & ( a_ {2}, b_ {3}) & (a_ {3}, b_ {3}) & (a_ {4}, b_ {3}) & (a_ {5}, b_ {3}) & \ dots \ \ (a_ {1}, b_ {4}) & (a_ {2}, b_ {4}) & (a_ {3}, b_ {4}) & (a_ {4}, b_ {4}) & ( a_ {5}, b_ {4}) & \ dots \\ (a_ {1}, b_ {5}) & (a_ {2}, b_ {5}) & (a_ {3}, b_ {5}) & (a_ {4}, b_ {5}) & (a_ {5}, b_ {5}) & \ dots \\\ dots & \ dots & \ dots & \ dots & \ dots & \ end {matrix}} }
În acest fel am aranjat într-un tabel toate elementele {\ displaystyle A \ times B} și procedând prin diagonale ca în cazul numerelor raționale putem crea următoarea succesiune:
- {\ displaystyle {\ begin {array} {cccccccccccccccc} (a_ {1}, b_ {1}) & (a_ {1}, b_ {2}) & (a_ {2}, b_ {1}) & (a_ {1}, b_ {3}) & (a_ {2}, b_ {2}) & (a_ {3}, b_ {1}) & (a_ {1}, b_ {4}) & (a_ {2 }, b_ {3}) & (a_ {3}, b_ {2}) & (a_ {4}, b_ {1}) & (a_ {1}, b_ {5}) & (a_ {2}, b_ {4}) & (a_ {3}, b_ {3}) & (a_ {4}, b_ {2}) & (a_ {5}, b_ {1}) & \ dots \\\ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \ updownarrow & \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 12 & 13 & end matrici}}}
care este în mod evident o aplicație one-to-one în ansamblu {\ displaystyle A \ times B} Și {\ displaystyle \ mathbb {N}} .
Acum sunt {\ displaystyle A_ {1}, A_ {2}, A_ {3}, \ dots, A_ {n}} seturi numărabile, pentru ceea ce s-a spus mai sus, avem deci asta {\ displaystyle A_ {1} \ times A_ {2}} este un set care poate fi numărat și, prin urmare, și setul
- {\ displaystyle (A_ {1} \ times A_ {2}) \ times A_ {3} = A_ {1} \ times A_ {2} \ times A_ {3}}
este numărabil și, în general, se repetă {\ displaystyle n} de două ori raționamentul pe care îl avem ca întregul
- {\ displaystyle A_ {1} \ times A_ {2} \ times A_ {3} \ times \ dots \ times A_ {n}}
este numărabil și, prin urmare, produsul cartezian al unui număr finit de mulțimi numărabile este un set numărabil.
Notă
- ^ Deoarece există o bijecție evidentă între {\ displaystyle \ mathbb {N}} Și {\ displaystyle \ mathbb {N} ^ {*} = \ {1,2,3, \ ldots \}} , nu există nicio diferență dacă 0 este considerat sau nu un număr natural. În orice caz, acest articol urmează ISO 31-11 și convenția standard în logica matematică , conform căreia 0 este un număr natural.
- ^ Lang 1993 , §2 din capitolul I.
Bibliografie
- Richard Courant și Herbert Robbins , Ce este matematica? , Ediția a doua, Torino , Universale Bollati Boringhieri , 2000, ISBN 88-339-1200-0 .
- Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi și Luigi Laura, Limbi, modele, complexitate , Milano , FrancoAngeli , 2003, ISBN 88-464-4470-1 .
- ( EN ) WS Brainerd și LH Landweber, Theory of Computation , New York , Wiley , 1974, ISBN 04-710-9585-0 .
- ( EN ) Serge Lang , Real and Functional Analysis , Berlin , Springer Verlag , 1993, ISBN 0-387-94001-4 .
Elemente conexe
Alte proiecte
linkuri externe