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

Из пројекта Википедија

Предложено је да се овај чланак или један његов део споји са чланком Пребројиво бесконачан скуп. (Разговор)

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

Пребројиви скупови се могу дефинисати на два различита начина. Под пребројивим скуповима можемо подразумевати или само бесконачне пребројиве скупове, или бесконачне пребројиве и коначне скупове. Дакле, две дефиниције се разликују само по томе, да ли сматрамо коначне скупове пребројивим. Прва дефиниција је на неки начин подскуп друге дефиниције. Коначни скупови (по другој дефиницији) су увек пребројиви (ако желимо да будемо прецизни, можемо нагласити да говоримо о бесконачном пребројивом скупу).

Под пребројивим скуповима најчешће се подразумевају и коначни скупови.

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

Изненађујући резултати у вези пребројивих скупова:

Рационални бројеви су пребројиви.
Постоје скупови који су непребројиви, тј. постоје скупови који

имају више од бесконачно пребројиво много елемената.

Садржај

1 Бесконачни пребројиви скуиви

[уреди] Бесконачни пребројиви скуиви

За неки скуп кажемо да је бецконачно пребројив, ако је бесконачан и има исто толико елемената као скуп природних бројева.

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

За неки скуп $S$ кажемо да је (бесконачно) пребројив ако је бесконачан и постоси функција $f:\mathbb{N}\mapsto S$ са скупа $\mathbb N$ (природниха бројева) на скуп $S$ . (Пошто се ради о бијекцији, све једно је да ли је бијекција са $\mathbb N$ на $S$ , или са $S$ на $\mathbb N$ ).

[уреди] Примери

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

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

Примери за непребројиве скупове су: скуп реалних бројева, интервал реалних бројева од 0 до 1 или подскуп свих скупова природних бројева.

[уреди] Рационални бројеви су пребројиви

По формалној дефоиницији се одмах види, да су природни бројеви пребројиви (са бијективном идентичном функцијом).

Цели бројеви се бијекивно могу пресликати на природне тако да сваком природном броју придружимо одговарајући елемент низа {0, 1, -1, 2, -2, 3, -3, ...}. Ово придруживање можемо описати функцијом

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

За сад би смо могли рећи да су препројиви они скупови, чије елементе можемо поставити по једној (бесконачној) линији, а да буде простора између њих, па би по тој логици могли рећи да рационални бројеви, пошто су свуда густи, непребројиви као реални бројеви, али то није тако!

Пребројивост рационалних бројева можемо приказати на следећој слици:

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