Prebrojiv skup

U matematici, prebrojiv skup je skup čija je kardinalnost (tj. broj elemenata) jednaka kardinalnosti nekog podskupa skupa prirodnih brojeva. Ovaj termin je uveo Georg Kantor; potiče iz činjenice da za brojanje koristimo prirodne brojeve. Skup koji nije prebrojiv, nazivamo neprebrojiv skup.

Pod prebrojivim skupovima najčešće se podrazumevaju i konačni skupovi, pa zato kada želimo da naglasimo da je skup beskonačan i prebrojiv, nazivamo ga prebrojivo beskonačan skup.

Prebrojive skupove možemo zamisliti kao neki skup čije elemente možemo poređati u niz. Dakle, prebrojive skupove možemo preurediti tako da imamo tačno jedan prvi element, tačno jedan drugi, tačno jedan treći element itd. kao kod prirodnih brojeva {1,2,3,...}. Važno je primetiti, pošto i beskonačni skupovi mogu biti prebrojivi, da ne zahtevamo da se može odrediti (konačan) broj elemenata, samo treba da svakom broju možemo reći koji je on u nizu elemenata tog skupa. Tako, na primer, skup svih racionalnih brojeva, premda beskonačan, je prebrojiv.

Formalna definicijaUredi

Neki skup   je prebrojiv ako je ekvipotentan sa skupom  , odnosno ako postoji bijekcija  .

(Pošto se radi o bijekciji, sve jedno je da li je bijekcija sa   na  , ili sa   na  ).

Kada znamo da je skup konačan, ili beskonačno prebrojiv, kažemo da je on najviše prebrojiv skup.


PrimeriUredi

Poznatiji primeri prebrojivo beskonačnih skupova:

Skup prirodnih brojeva  Uredi

Da bi skup   bio prebrojiv, mora biti ekvipotentan sam sebi, a kako je ekvipotencije refleksivna relacija sledi da je   ~  .


Skup svih parnih brojevaUredi

Definišimo funkciju  , koja preslikava skup svih prirodnih brojeva u skup parnih brojeva. Ova funkcija je bijekcija, pa to povlači i prebrojivost parnih brojeva.

Obratimo pažnju da ovo prema definiciji ekvipotentnih skupova znači da je skup prirodnih brojeva ekvipotentan skupu parnih brojeva, odnosno da su oni „jednaki“. Ova osobina beskonačnog skupa je iskorišćena za njegovo definisanje.


Skup celih brojeva  Uredi

U ovom slučaju možemo koristiti definiciju koja se koristi bijekcijom. Dakle, svaki element skupa   se mora preslikati na jedan i samo jedan element skupa  .

Ovo možemo posmatrati tako da svaki broj iz   ima svoju sliku na skupu prirodnih brojeva. Tako možemo definisati funkciju koja:

  • 0 preslikava na 1
  • 1 preslikava na 2
  • -1 preslikava na 3
  • 2 preslikava na 4
  • -2 preslikava na 5

.

.

.

  • n preslikava na 2n
  • -n preslikava na 2n+1...

Ovako definisana funkcija je bijekcija između skupova   i  , pa prema definiciji sledi da je   prebrojiv skup.


Ovo pridruživanje možemo opisati i funkcijom:

 

Skup racionalnih brojeva  Uredi

Kao i kod prethodnog primera, trebamo da nađemo bijekciju koja će racionalne brojeve „slagati u niz“, odnosno dodeljivati im slike, ili mesta, iz skupa {1,2,3,...,n,...}.

 

Ako pratimo strelice, možemo zaključiti da svakom racionalnom broju možemo dodeliti njegovo mesto u nizu, odnosno možemo definisati bijekciju na gore opisan način, pa sledi da su racionalni brojevi prebrojivi.

LiteraturaUredi

  • Lang, Serge (1993), Real and Functional Analysis, Berlin, New York: Springer-Verlag, ISBN 0-387-94001-4 
  • Rudin, Walter (1976), Principles of Mathematical Analysis, New York: McGraw-Hill, ISBN 0-07-054235-X 

Vanjske vezeUredi