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 podrazumjevaju 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 poredati 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 primjetiti, pošto i beskonačni skupovi mogu biti prebrojivi, da ne zahtjevamo 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 primjer, skup svih racionalnih brojeva, premda beskonačan, je prebrojiv.

Formalna definicija[uredi | uredi izvor]

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 S, ili sa S  na  ). Kada znamo da je skup konačan, ili beskonačno prebrojiv, kažemo da je on najviše prebrojiv skup.

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

Primjeri

Najpoznatiji primjeri prebrojivo beskonačnih skupova:

Skup prirodnih brojeva

Da bi skup bio prebrojiv, mora biti ekvipotentan sam sebi, a kako je ekvipotencija refleksivna relacija sliedi da je ~

Skup parnih brojeva

Definišimo funkciju , koja skup svih prirodnih brojeva preslikava 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 cijelih brojeva

U ovom slučaju možemo koristiti definiciju koja se koristi bijekcijom. Dakle, svaki element skupa mora se 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 slijedi da je prebrojiv skup.

Ovo pridruživanje možemo opisati i funkcijom:

Skup racionalnih brojeva

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

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

Community content is available under CC-BY-SA unless otherwise noted.