Predmet:Re: Skupovi
Konacni i beskonacni skupovi
U svim ovim razmatranjama predpostavljamo da su poznate osobine sklase { 0, 1, 2, ...} tj skupa prirodnih brojeva N.
Za svaki k iz N \ {0} sa N
k oznacavamo skup {1, . . . , k}, a N
0 je prazan skup.
Teorema
Neka je k iz N proizvoljan. Ako je f : N
k → Nsub]k[/sub] injekcija tada je f i sirjekcija.
Dokaz.
Neka je k iz N proizvoljan. Dokažimo da ako je f : N
k →N
k injekcija tada je f i surjekcija.
Indukcijom po k dokazujemo da je svaka injekcija f : N
k
→ N
k ujedno i sirjekcija.
Za k = 0 tvrdnja je trivijalno isitinita.
Ako je k = 1 tada je ocito funkcija f : {1} → {1} sirjekcija.
Za k iz N \ {0} prirodan broj koji ima osobinu da je svaka injekcija g : N
k → N
k i sirjekcija.
Neka je f : N
(k+1)→N
(k+1) proizvoljna injekcija. Tada je restrikcija f|
Nk : N
k→N
(k+1)
takodjer injekcija.
Sada razlikujemo dva slucaja:
a) f(k + 1) = k + 1
To znaci da je slika restrikcije f|
Nk sadržana u skupu N
k.
Time imamo da je funkcija f|
Nk: N
k →N
k injekcija.
Iz pretpostavke indukcije slijedi daje ta funkcija sirjekcija. Ocigledno je je funkcija f sirjekcija.
b) f(k + 1) = i
0 iz N
k
Primijetimo prvo da postoji j
0 iz N
k takav da je f(j
0 = k + 1 (Pretpostavimo da takav j
0 iz N
k ne postoji. Tada je f|
Nk: N
k →N
k dobro definisana, te je injekcija.
Iz pretpostavke indukcije slijedi da je ta restrikcija i sirjekcija.
Tada postoji neki i
1 iz N
k takav da je f(i
1) = i
1.
Time imamo f(k + 1) = f(i
1, te k + 1 razlicito od i
1, što je kontradikcija s pretpostavkom da je funkcija f : N
(k+1)→N
(k+1) injekcija).
Definisimo funkciju f : N
k → N
k ovako:
F(x) ={f(x) ako je xrazlicito od j
0 i i
0 ako je x= j
0}
Ocito je funkcija F : N
k→ N
k injekcija.
Iz pretpostavke indukcije slijedi da je ta funkcija i sirjekcija. Sada je lako vidjeti da iz toga slijedi da je i funkcija f sirjekcija (Neka je y iz N
(k+1)proizvoljan.
Razlikujemo tri slucaja.
1. Ako je y iz N
k \ {i
0} tada iz sirjektivnosti funkcoje F i njene definicije slijedi da postoji x iz N
k takav da je f(x) = y.
2. Ako je y = i
0 tada imamo f(k + 1) = i
0.
3. Ako je y = k + 1 tada imamo f(j
0) = k + 1 ).
"Ne treba se stidjeti nikakvog posla, pa čak ni onog najprljavijeg; treba se stidjeti samo besposlenog života." - Tolstoj