Пребројив скуп

У математици, пребројив скуп је скуп чија је кардиналност (тј. број елемената) једнака кардиналности неког подскупа скупа природних бројева. Овај термин је увео Георг Кантор; потиче из чињенице да за бројање користимо природне бројеве. Скуп који није пребројив, називамо непребројив скуп.

Под пребројивим скуповима најчешће се подразумевају и коначни скупови, па зато када желимо да нагласимо да је скуп бесконачан и пребројив, називамо га пребројиво бесконачан скуп.^[1]

Пребројиве скупове можемо замислити као неки скуп чије елементе можемо поређати у низ. Дакле, пребројиве скупове можемо преуредити тако да имамо тачно један први елемент, тачно један други, тачно један трећи елемент итд. као код природних бројева {1,2,3,...}. Важно је приметити, пошто и бесконачни скупови могу бити пребројиви, да не захтевамо да се може одредити (коначан) број елемената, само треба да сваком броју можемо рећи који је он у низу елемената тог скупа. Тако, на пример, скуп свих рационалних бројева, премда бесконачан, је пребројив.

Формална дефиниција

Неки скуп $S\,$ је пребројив ако је еквипотентан са скупом $\mathbb {N}$ , односно ако постоји бијекција $f:\mathbb {N} \mapsto S$ .

(Пошто се ради о бијекцији, свеједно је да ли је бијекција са $\mathbb {N}$ на $S\,$ , или са $S\,$ на $\mathbb {N}$ ).

Када знамо да је скуп коначан, или бесконачно пребројив, кажемо да је он највише пребројив скуп.

Примери

Познатији примери пребројиво бесконачних скупова:

Скуп природних бројева $\mathbb {N}$

Да би скуп $\mathbb {N}$ био пребројив, мора бити еквипотентан сам себи, а како је еквипотенција рефлексивна релација следи да је $\mathbb {N}$ ~ $\mathbb {N}$ .

Скуп свих парних бројева

Дефинишимо функцију $f(n)=2n$ , која пресликава скуп свих природних бројева пресликава у скуп парних бројева. Ова функција је бијекција, па то повлачи и пребројивост парних бројева.

Обратимо пажњу да ово према дефиницији еквипотентних скупова значи да је скуп природних бројева еквипотентан скупу парних бројева, односно да су они „једнаки“. Ова особина бесконачног скупа је искоришћена за његово дефинисање.

Скуп целих бројева $\mathbb {Z}$

У овом случају можемо користити дефиницију која се користи бијекцијом. Дакле, сваки елемент скупа $\mathbb {Z}$ се мора пресликати на један и само један елемент скупа $\mathbb {N}$ .

Ово можемо посматрати тако да сваки број из $\mathbb {Z}$ има своју слику на скупу природних бројева. Тако можемо дефинисати функцију која:

0 пресликава на 1
1 пресликава на 2
-1 пресликава на 3
2 пресликава на 4
-2 пресликава на 5

. . .

n пресликава на 2n
-n пресликава на 2n+1...

Овако дефинисана функција је бијекција између скупова $\mathbb {Z}$ и $\mathbb {N}$ , па према дефиницији следи да је $\mathbb {Z}$ пребројив скуп.

Ово придруживање можемо описати и функцијом:

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

Скуп рационалних бројева $\mathbb {Q}$

Као и код претходног примера, треба да нађемо бијекцију која ће рационалне бројеве „слагати у низ“, односно додељивати им слике, или места, из скупа {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}}

Ако пратимо стрелице, можемо закључити да сваком рационалном броју можемо доделити његово место у низу, односно можемо дефинисати бијекцију на горе описан начин, па следи да су рационални бројеви пребројиви.

Референце

^ Rudin 1976, Chapter 2

Литература

Apostol, Tom M. (1969). Multi-Variable Calculus and Linear Algebra with Applications. Calculus. 2 (2nd изд.). 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 изд.). 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.

Спољашње везе

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

[Rudin-1] Rudin 1976, Chapter 2

[1]