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₀ 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₀ iz N_k

Primijetimo prvo da postoji j₀ iz N_k takav da je f(j₀ = k + 1 (Pretpostavimo da takav j₀ 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₁ iz N_k takav da je f(i₁) = i₁.
Time imamo f(k + 1) = f(i₁, te k + 1 razlicito od i₁, š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₀ i i₀ ako je x= j₀}
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₀} 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₀ tada imamo f(k + 1) = i₀.
3. Ako je y = k + 1 tada imamo f(j₀) = k + 1 ).

---