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, svejedno 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 ekvipotencija 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 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 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, treba 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

• Apostol, Tom M. (1969). Multi-Variable Calculus and Linear Algebra with Applications. Calculus. 2 (2nd izd.). New York: John Wiley + Sons. ISBN 978-0-471-00007-5. 
• Avelsgaard, Carol (1990). Foundations for Advanced Mathematics. Scott, Foresman and Company. ISBN 978-0-673-38152-1. 
• Cantor, Georg (1878), „Ein Beitrag zur Mannigfaltigkeitslehre”, Journal für die Reine und Angewandte Mathematik, 84: 242—248 
• Ferreirós, José (2007). Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought (2nd revised izd.). Birkhäuser. ISBN 978-3-7643-8349-7. 
• Fletcher, Peter; Patty, C. Wayne (1988). Foundations of Higher Mathematics. Boston: PWS-KENT Publishing Company. ISBN 978-0-87150-164-6. 
• Halmos, Paul R. (1960). Naive Set Theory. D. Van Nostrand Company, Inc.  Reprinted by Springer-Verlag. . New York. 1974. ISBN 978-0-387-90092-6.  (Springer-Verlag edition). . Reprinted by Martino Fine Books. 2011. ISBN 978-1-61427-131-4.  (Paperback edition).
• Kamke, E. (1960), Theory of Sets, New York: Dover 
• Lang, Serge (1993). Real and Functional Analysis. Berlin, New York: Springer-Verlag. ISBN 978-0-387-94001-4. 
• Rudin, Walter (1976). Principles of Mathematical Analysis. New York: McGraw-Hill. ISBN 978-0-07-054235-8. 

Spoljašnje veze

• Weisstein, Eric W. „Countable Set”. MathWorld.