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

Из Википедије, слободне енциклопедије

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

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

Пребројиве скупове можемо замислити као неки скуп чије елементе можемо поређати у низ. Дакле, пребројиве скупове можемо преуредити тако да имамо тачно један први елемент, тачно један други, тачно један трећи елемент итд. као код природних бројева {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}

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