Predmet:Re: Skupovi
Definicija
Kažemo da je skup A konacan ako postoji k iz N tako da je skup A
ekvipotentan sa skupom N
k.
Napomena
Iz navedene teorema slijedi da za svaki konacan skup A postoji jedinstveni
k iz N takav da vrijedi A ekvipotentno N
k. To nam omogucava da za svaki konacan skup A definisemo broj elemenata, u oznaci k(A), stavljajuci
k(A)=n, pri cemu vrijedi A ekvipotemtno N
n.
Teorema
Za svaki A pravi podskup N
m postoji prirodan broj k takav da vrijedi k≤ m i k(A)=k.
Dokaz.
Indukcijom po m.
Ako je m = 0 ili m = 1 tvrdnja ocito vrijedi.
Neka je m iz N takav da za svaki podskup B od N
m postoji k≤m takav da je k(B) = k.
Neka je A proizvoljan podskup od Nsub](m+1)[/sub]. Ako je A podskup Nsub]m[/sub] tvrdnja slijedi iz pretpostavke indukcije.
Posmatrajmo slucaj kada je m+1 iz A.
Tada je A \ {m + 1} podskup Nsub]m[/sub]. Iz pretpostavke indukcije slijedi da postoji k iz N takav da je k(A\{m + 1}) k. Tada je ocito k(A) = k + 1.
Korolar
Svaki podskup konacnog skupa je konacan.
Teorema
Skup X je konacan ako i samo ako postoji k iz N i sirjekcija f : N
k →X.
Dokaz
Pretpostavimo prvo da je skup X konacan. Tada iz definicije slijedi da
postoji k iz N i bijekcija f : A → N
k. Tada je f
-1 jedna tražena surjekcija.
Pretpostavimo sada da postoji k iz N i surjekcija f : N
k→X.
Tada ocitoza svaki x iz X imamo f
-1[{x}] razlicito od 0;.
Za svaki x iz X odaberimo po jedan a_x iz f
-1 [{x}].
Oznacimo A = {a
x : x iz X}.
Ocito je A podskup N
k, te je funkcija g : A → X, koja je definisana sa g(a
x) = x, bijekcija.
Tada je k(A) = k(X).
Iz A podskup N
k i i ranije dokazanog slijedi da postoji m ≤ k takav da je k(A) = m. Tada je k(X) = m, te je skup X konacan
"Ne treba se stidjeti nikakvog posla, pa čak ni onog najprljavijeg; treba se stidjeti samo besposlenog života." - Tolstoj