Prebrojiv skup

Izvor: Wikipedia

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[uredi - уреди]

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[uredi - уреди]

Poznatiji primeri prebrojivo beskonačnih skupova:

Skup prirodnih brojeva \mathbb{N}[uredi - уреди]

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[uredi - уреди]

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[uredi - уреди]

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[uredi - уреди]

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[uredi - уреди]

  • 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 veye[uredi - уреди]