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 definicija

Neki skup $S\,$ je prebrojiv ako je ekvipotentan sa skupom $\mathbb {N}$, odnosno ako postoji bijekcija $f:\mathbb {N} \mapsto S$.

(Pošto se radi o bijekciji, sve jedno je da li je bijekcija sa $\mathbb {N}$ na $S\,$, ili sa $S\,$ na $\mathbb {N}$).

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

Primeri

Poznatiji primeri prebrojivo beskonačnih skupova:

Skup prirodnih brojeva $\mathbb {N}$

Da bi skup $\mathbb {N}$ bio prebrojiv, mora biti ekvipotentan sam sebi, a kako je ekvipotencije refleksivna relacija sledi da je $\mathbb {N}$ ~ $\mathbb {N}$.

Skup svih parnih brojeva

Definišimo funkciju $f(n)=2n$, 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 $\mathbb {Z}$

U ovom slučaju možemo koristiti definiciju koja se koristi bijekcijom. Dakle, svaki element skupa $\mathbb {Z}$ se mora preslikati na jedan i samo jedan element skupa $\mathbb {N}$.

Ovo možemo posmatrati tako da svaki broj iz $\mathbb {Z}$ 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 $\mathbb {Z}$ i $\mathbb {N}$, pa prema definiciji sledi da je $\mathbb {Z}$ prebrojiv skup.

Ovo pridruživanje možemo opisati i funkcijom:

$f(n)={\begin{cases}-(n-1)/2&\exists k\in \mathbb {N} _{0}:n=2k+1\\n/2&\exists k\in \mathbb {N} _{0}:n=2k+2\end{cases}}$

Skup racionalnih brojeva $\mathbb {Q}$

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,...}.

${\begin{matrix}(0,0)&\rightarrow &(0,1)&&(0,2)&\rightarrow &(0,3)&\\&\swarrow &&\nearrow &&\swarrow &&\\(1,0)&&(1,1)&&(1,2)&&\ddots &\\\downarrow &\nearrow &&\swarrow &&&&\\(2,0)&&(2,1)&&\ddots &&&\\&\swarrow &&&&&&\\(3,0)&&\ddots &&&&&\\\downarrow &&&&&&&\\\vdots &&&&&&&\end{matrix}}$

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.

Literatura

• 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 veze

• Weisstein, Eric W., "Countable Set", MathWorld.