roza 14.09.2010 19:04
Predmet:Skupovi

Teorija skupova daje mogucnost baratanja sa beskonacnosti. Ona razlikuje razlicite beskonacnosti. Postoji beskonacno mnogo beskonacnosti razlicitih velicina. To je pokazao otac teorije skupova GEORG CANTOR.

Skup je osnovni pojam i zato ga ne definisemo.
Skup je kolekcija objekta koji zajedno cine cjelinu.

Na ovako nedefinisanom i nejasnom pojmu Kantor je izgradio teoriju skupova. Kao i svaka druga teorija i teorija skupva mora se zasnivati na sistemu alsioma. Kantor se nije srrogo vezivao za sistem aksioma. Analizom njegovog rada vidi se da se skoro svi toremi vezuju za 3 aksioma.

Aksiom: EKSTENZIONALNOSTI
Dva skupa su jednaka Ako imaju iste elemente.

Aksiom: KOMPREHENIZIJE
Za unaprijed datu osobinu f(x) postoji skup ciji su elementi bas oni objekti koji imaju tu osobinu tj [x; f(x)] je skup

Aksiom IZBORA
Za svaki neprazni skup postoji bar jedna funkcija ciji su argumentineprazni podskupovi datog skupa a slike su argumenti tog skupa.

Razvojem teorije o skupovima pojavili su se paradoksi. Paradoks nije isto kao i kontradikcija. Paradoks je tvrdnja ciji je dokaz logicki neupitan, ali je intuitivno sama tvrdnja upitna.

Russellov paradoks

R=[x: xje skup i xnije element iz x]

Dokazimo da R nije skup. Predpostavimo da je R skup. Mozemo postaviti pitanje da li je R element skupa R.
Predpostavimo da je R element skupa R. Onda ispunjava uslov koji ispunjavaju njegovi elementi tj x nije element skupa x odnosno R nije element skupa R. Ovim smo iz pretpostavke R je element skupa R dobili R nije element skupa R.
(dobili smo kontradikciju). Zakljucujemo da R ispunjava uslov R nije element skupa R. Tada R ispunjava definicijski uslov za skup R tj R je jedan element skupa R (kontradikcija).
Znaci predpostavka R je skup dovodi do kontradikcije, tj R nije skup.
Sta ovo znaci?
Russell je prvi dao primjer klase objekata koja nije skup. Ukazao je da Cantorov princip komprihinizije ne mozemo primjenjivati pri izgradnji skupova. Ne postoje kriteriji za izgradnju skupova.

Mozemo postaviti da li su sljedeci primjeri skupovi.
[x: postoji bijekcija izmedju skupa x i N] ( nije skup)
[ x: x je diferencijalna realna funkcija na skupu N] ( jeste skup)
[x: x je skup takav da za VyVz(y iz z iz x => y iz x] ( nije skup)
[x: postoji binarna operacija o takva da je (x,o) grupa] ( nije skup)

Ako je f neka osobina tada je (x, f/x)) klasa. Klase mogu biti ili ne biti skupovi. Klase koje nisu skupovi su prave klase. Klasa iz Russellovog paradoksa je prava klasa. Klasa x je skup ako postoji klasa y takva da je x element iz y.
Skupove treba graditi po nivoima. Njihovu izgradnju omogucava aksiomatski pristup. Ovakvi skupovi treba da cine temelj matematike. Npr da se u njima mogu definisati prirodne brojeve.

Prije izgradnje teorije skupova predpostavimo da postoji skup koji nema ni jedan element. Ovaj skup je PRAZAN skup.
Cesto se predpostavlja da neki skup ne moze biti element nekog skupa. Primjer je partitivni skup. Njegovi elementi su podskupovi datog skupa. U teoriji skupova elementi skupova su skupovi.

roza 15.09.2010 18:12
Predmet:Re: Skupovi

Kumulativna hijerarhija

Kada zelimo napisati aksiome koji ce opisivati prirodne brojeve mi imamo dobro izgradjen, ili bar tako mislimo, pojam prirodnog broja. Slicno je i sa drugim pojmovima.

Evo nekoliko struktura i pripadnih aksiomatizacija:

Teorija brojeva- Peanova aritmetika
Intuicija polja R- aksiome za R
Teorije raznih grupa- aksiome teorije grupe
Teorija vektorskog prostora – aksiomi vektorskog prostora

Prilikom aksiomatizacije pojma skupa imamo problem. Sta ustvari znaci skup?
Koju strukturu zelimo opisati aksiomima?

Aksiomima treba da opisemo sljedecu strukturu:
[0 oznaka za prazan skup]

­V0= 0
V1= [0]=P(V0)
V2= [0, [0]]=P(V1)
.
.
.
V(a+1)=P(V(a))
Vb =UVa [a<b]

Gdje je a proizvoljan ordinalni broj, a b ordinalni broj koji nema neposrednog predhodnika. Tada klasu.

V=UVa (a € O_n) [On klasa svih ordinalnih brojeva] nazivamo kumulativna hijerarhija.

Osnovni zahtjevi skupova su:

1. Svaka podklasa skupa je skup. Odnosno za svaki skup A i svojstvo f postoji skup svih x €A sa svojstvom f(x).
2. Skupovi su zatvoreni na osnovne operacije unija, presjek, paritivni skup.
3. Skupovi su zatvoreni na slike funkcija. Odnosno ako je je f funkcija i A skup, tada je {f(x): x € A } takodjer skup.
4. Ako je klasa X element skupa Y, tada je X skup.

roza 15.09.2010 18:19
Predmet:Re: Skupovi

Neke aksiome Zermelo-Fraenkelove teorije (teorija ZF)

Aksiom ekstenzionalnosti

Ako su x i y skupovi takvi da je x podskup od y i y podskup od x onda je x=y.

Ovaj aksiom koristimo kod dokazivanja skupovnih identiteta.

Primjer

{1, 2, 3}= {3, 1, 2}
{1, 2, 2, 3, 1}={1, 2, 3}

Aksiom praznog skupa

Postoji skup koji ne sadrzi niti jedan element.

Aksiom partitivnog skupa

Ako je x skup onda je klasa svih njegovih podskupova skup. Oznacava se sa P(x)

Aksiom para

Za svaka dva skupa x, y postoji skup ciji su x i y jedini elementi. Oznacavamo ga sa (x, y)

Aksiom unije

Za svaki skup je klasa elemenata svih njegovih elemenata ponovo skup

Neka je dat skup A={0, {a, b, c},{d}} onda je skup {a, b, c} takodjer skup.

Ako su x i y skupovi onda postoji par {x, y}. Tada je U{x,y} takodjer skup.oznacava se sa xUy.

Definicija

Ako su x, y skupovi onda skup {{x},{x, y } nazivamo uredjeni par i ozmacavamo sa s(x, y)

Ovu definiciju dao je Kuratowski 1921 godine. N Wiener 1914 godine uredjeni par je definisao kao
{ {{x},0}, {{y}}}

roza 15.09.2010 19:09
Predmet:Re: Skupovi

Propozicija
Ako vrijedi {x1, y1}={x2, y2 tada je x1=x2 & y1=y2
Dokaz

Po pretpostavci je

{{x1}, {x1, y1}}= {{x2}, {x2, y2}}

Iz aksiome ekstenzionalnosti slijedi da su moguca dva slucaja

1.
[{x1}={x2} => x1 = x2]& [{x1, y1}={x2, y2}=> x1=x2 & 1=y2]=> y1=y2

2.
{x1}={x2,y2}=> x1=x2 $ x1=y2=>x1=x2=y2
i iz
{x1,y1}={x2,y2}=>{x1,y1}= {x2}=>x1=y2=x2,
odnosno
x1= x2= y1= y2

roza 17.09.2010 19:16
Predmet:Re: Skupovi

Definicija

Za svako n iz N, n ≥ 2 definisemo uredjenu n- torku ovako:

{{ x1}, { x1, x2}}
{{ x1,..., xn}, { x(n+1)}}

kako bismo mogli govoriti o Kartazijevom proizvodu funkcija, zatim o relacijama i funkcijama navodimo semu aksima separacije

Sema aksioma separacije

Ako je x skup i F neka osobina tada je klasa svih z iz x takodjer skup.

(F je proizvoljna formula teorije ZF sa jednom slobodnom varijablom. Formula je konacan niz znakova koji mogu biti varijable, zagrade, logicki veznici, kvantifikatori...)

Propozicija

Neka su x i y skupovi tada je klasa {(x´,y´): x´ iz x i y´ iz y} takodjer skup. Nazivamo ga KARTEZIJEV proizvod skupova x i y i oznacavamo ga sa x x y.

Dokaz
Iz aksioma unije i i para slijedi da postoji skup xUy. Iz aksioma partitivnog skupa slijedi da postoji skup P(P(xUy)). Sada iz semi aksima separacije slijedi da je klasa
{z: z element iz P(P(xUy))}& (postoji u iz x)(postoji v iz y)(z=(u,v)) skup, tj (x x y) je skup.

Na analogan nacin moze se dokazati da propozicija vrijedi za n skupova.

Definicija

Za proizvoljni skup x sa ∩x oznacavamo klasu {z: da za svaki y iz x vrijedi y iz y} te je nazivamo PRESJEK skupa x. Ako su x i y skupovi tada x∩y oznacavamo sa ∩x.
Analogno ako je n iz N i ako su x1,..., xn skupovi tada sa x1∩x2∩...∩xn oznacavamo presjek ∩{x1,... xn}

Propozicija

Ako je x skup tada je presjek ∩x takodjer skup.

Definicija
Za proizvoljne skupove x i y sa x bez y (x\y) oznacavamo klasu {z: z iz x & z nije iz y} te je nazivamo RAZLIKA skupova x i y. Neka je U neki skup te je x pravi podskup od U tada sa xc oznacavamo klasu U(\ x)i nazivamo KOMPLEMENT skupa x u odnosu na U.

Propoticija
Za sve skupovi x i y razlika skupova x i y je skup. Ako je U skup i ako je x pravi podskup od U onda je i kompliment xc takodjer skup.

roza 17.09.2010 19:49
Predmet:Re: Skupovi

Definicija

BINARNA relacija R na skupovima x i y je proizvoljni podskup Kartezijevog proizvoda x x y. Ako su x_1, ... x_n skupovi onda je n- mjesna relacija proizvoljan podskup Kartezijevog proizvoda x1 x... x xn

Definicija

Neka su X i Y proizvoljni skupovi i neka je f pravi podskup od XxY ima svojstvo da za svako x iz X postoji jedinstven y iz Y tako da vrijedi (x,y) iz f. Tada binarnu relaciju f nazivamo FUNKCIJA i oznacavamo sa f:X→Y. Skup X nazivamo domena, a Y kodomena funkcije. Ako je f:X→Y te je (x,y) element od f onda umjesto y pisemo f(x,y).

Skup svih funkcija iz skupa X u skup Y oznacavamo sa x(Y). Funkcije mozemo zadavati na razne nacine formulom, grafikom, tabelom...

Ako je X neki skup onda funkciju id x:X→X zadanu sa idx(x) =x nazivamo IDENTITET.
Ako je A pravi podskup od X onda funkciju i:A→X nazivamo INKLUZIJA.
Ako je f:X→Y neka funkcija te A pravi podskup od Y, te C pravi podskup od Y tada skup f[A]={f(x):x iz A} nazivamo SLIKA podskupa A, odnosno skup f(-1)[C]={x iz X:f(x) iz C} nazivamo praslika skupa C. Slika funkcije f:X→Y je tada f[X]. Obicno sliku funkcije oznacavamo sa R(ng) (f). Graf funkcije f:X→Y je skup {(x, f(x)):x iz X} [ iz navedenog slijedi da je funkcija jednaka svom grafiku]
Kazemo da su funkcije f:X→Y i g:U→V JEDNAKE ( pisemo f=g) ako vrijedi X=U i Y=V te za svaki x iz X vrijedi f(x)=g(x).

Propozicija

Neka je f:X→Y neka funkcija i A, B pravi podskupovi od X onda vrijedi:
f[AUB]=f[A]Uf[B] i
f[A∩B]=f[A] ∩f[B]

Propozicija

Neka je f:X→Y neka funkcija i C, D pravi podskupovi od X onda vrijedi:
F(-1) [CUD]=f(-1) [c]Uf(-1)[D] i
F(-1)[C∩D]=f(-1)[C] ∩f(-1 [D].

Neka su f:X→y i g:U→V takve da je R_(ng)(f) pravi podskup od U, tada funkciju sa domenom X i kodomenom V koja svakom x iz X pridruzuje g(f(x)) nazivamo kompozicija funkcija f i g i oznacavamo sa gof. Lako se provjerava da je ovo asocijativna kompozicija.
Neka je f:X→Y neka funkcija tr A pravi podskup od X. Funkciju g:A→Y, koja je definisanu sa g(x)=f(x) RESTRIKCIJA funkcije f, te je oznacavamo sa f|A. Kazemo f je PROSIRENJE f| A.

Za funkciju f:X→Y kazemo da je INJEKCIJA ako za svako x1, x2 iz X ,takve da je x1≠ x2, vrijedi f(x1) ≠ f(x[sub_2[/sub]).
Za funkciju f:X→Y kazemo da je SIRJEKCIJA ako za svako y iz Y postoji x iz X tako da vrijedi y=f(x).
Kazemo da je funkcija BIJEKCIJA ako je injekcija i sirjekcija.

Neka je f:X→Y neka funkcija.
Kazemo da je funkcija g:Y→X INVERZNA funkcija od f ako vrijedi fog=id_y i gof=idx. Ako za neku funkciju f postoji inverzna funkcija ona je jedinstvena. Inverznu funkciju funkcije f oznacavamo sa f(-1).

roza 17.09.2010 19:52
Predmet:Re: Skupovi

Definicija

Za svaki skup X svaki podskup F od P(x) nazivamo FAMILIJA skupova. Ako su X i I neki skupovi tada svaku funkciju f:I→P(x) nazivamo INDEKSIRANA FAMILIJA skupova. Obicno umjesto f(i) pisemo Xi pa indelsiranu familiju skupova oznacavamo sa (Xi : i iz I).

Definicija

Neka je (Xi: i iz I) proizvoljna familija skupova. Kartezijev proizvod skupova u oznaci ∏Xi (i iz I) definisemo kao klasu
{f| f:I→UXi (i iz I) vrijedi f(i) iz Xi}

roza 19.09.2010 10:26
Predmet:Re: Skupovi

Ekvipotentni skupovi

Nije pretjerano reci da citavu matematiku prozima ideja beskonacnosti. Sjetimo se beskonacnih skupova kao sto su: skupovi brojeva: prirodnih, cijelih, racionalnih, realnih i kompleksnih. U geometriji se govori o skupu svih tacaka ravni, skupu svih duzi, skupu svih pravi, ...

Jedna od osnovnih Cantorovih ideja o jednakobrojnim skupovima je nevjerojatno jednostavna:

Za dva skupa A i B kazemo da su JEDNAKOBROJNA ili EKVIPOTENTNA ako postoji bijekcija f:A → B

[napomenimo da matematicari; od starogrckih matematricara sve do Cantora, nisu uocili postojanje raznih beskonacnosti.]
Primjer skup realnih brojeva ima vise elemenata od skupa prirodnih brojeva. Odnosno ne postoji bijekcija izmedju R i N.
No, skup N je ekvipotentan sa skupom svih parnih prirodnih brojeva, te sa skupom cijelih, a i skupom svih racionalnih brojeva.

Definicija

Za skupove A i b kazemo da su ekvipotentni ako postoji bar jedna bijekcija f:A→B. Oznacavamo sa A ekvipotentno B

a) {2, 7, 9 } ekvipotentno sa {153, 1001,2006 }
b) { 1, 2, 3 } ekvipotentno sa {-1, -2, -3 }

c) neka je data jedna bijekcija f: Z→ N sa:

f(x)={ (-2x za x<0 U (o za x=0) i (2x-1 za x>0 }

roza 19.09.2010 10:27
Predmet:Re: Skupovi

Hilbertov hotel.

Zamislimo da negdje daleko u Svemiru postoji hotel s beskonacno mnogo soba. Sobe su numerisane brojevima 1, 2, 3, . . . No, zamislimo da su sve sobe zauzete gostima, i dolazi jos jedan putnik koji zeli sobu. sto ce portir napraviti s njim?
Jednostavno, zamolit ce:
gosta iz sobe 1 da se premjesti u sobu 2,
gost iz sobe 2 u sobu 3, itd.
Novopridoslog gosta ce tada smjestiti u sobu broj 1.
(Nemojte si postavljati pitanje koliko ce to premjestanje trajati!)
Pokusajte sami odgovoriti sto ce portir napraviti kada stigne 1000 novih gostiju,
a sve sobe hotela su pune.
Razmotrimo jos jedan problem s kojim bi se mogao susresti portir hotela s beskonacno mnogo soba, i cije su sve sobe su pune.

Zamislimo da u Svemiru postoji jos jedan hotel s beskonacno mnogo soba cije su sve sobe popunjene gostima. Jednog dana glavna komisija za gradjevinarstvo u svemirskim prostorima otkrila je da taj drugi hotel koji nema gradjevinsku dozvolu. Istog trena taj drugi hotel je morao biti zatvoren i svi gosti (beskonacno mnogo njih!) stali su pred vrata prvog hotela (cije su sve sobe pune).
No, portir se brzo snasao.
Gosta iz sobe 1 svojeg hotela premjestio je u sobu 2, gosta iz sobe 2 u sobu 4, gosta iz sobe 3 u sobu 6, itd. Tako je ispraznio sve sobe s neparnim brojevima, te je u njih smjestio goste iz zatvorenog hotela.
Sada kada se vec tako dobro snalazimo s hotelima s beskonacno mnogo soba razmotrimo jos jedan problem koji bi portiru mogao zadati mnogo glavobolja.

Zamislimo da u Svemiru postoji beskonacno mnogo hotela s beskonacno mnogo soba, i sve su sobe popunjene gostima. Svemirska gradjevinska komisija iz raznih je razloga zatvorila sve hotele osim jednog. Tada su svi gosti (po beskonacno mnogo njih iz svakog od beskonacno mnogo hotela) dosli pred vrata tog jednog hotela koji je jos imao dozvolu za rad.
Snalazljivi portir sada nije znao rjesenje ove na prvi pogled bezizlazne situacije.
Trebao je pomoc matematicara. Moze li se uopce ova ogromna grupa novopridoslih gostiju smjestiti u (puni!) hotel? Mozete li pomoci portiru?

roza 19.09.2010 10:38
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 Nk oznacavamo skup {1, . . . , k}, a N0 je prazan skup.

Teorema

Neka je k iz N proizvoljan. Ako je f : Nk → Nsub]k[/sub] injekcija tada je f i sirjekcija.

Dokaz.

Neka je k iz N proizvoljan. Dokažimo da ako je f : Nk →Nk injekcija tada je f i surjekcija.

Indukcijom po k dokazujemo da je svaka injekcija f : Nk
→ Nk 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 : Nk → Nk i sirjekcija.

Neka je f : N(k+1)→N(k+1) proizvoljna injekcija. Tada je restrikcija f|Nk : Nk→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 Nk.
Time imamo da je funkcija f|Nk: Nk →Nk injekcija.
Iz pretpostavke indukcije slijedi daje ta funkcija sirjekcija. Ocigledno je je funkcija f sirjekcija.

b) f(k + 1) = i0 iz Nk

Primijetimo prvo da postoji j0 iz Nk takav da je f(j0 = k + 1 (Pretpostavimo da takav j0 iz Nk ne postoji. Tada je f|Nk: Nk →Nk dobro definisana, te je injekcija.
Iz pretpostavke indukcije slijedi da je ta restrikcija i sirjekcija.
Tada postoji neki i1 iz Nk takav da je f(i1) = i1.
Time imamo f(k + 1) = f(i1, te k + 1 razlicito od i1, što je kontradikcija s pretpostavkom da je funkcija f : N(k+1)→N(k+1) injekcija).

Definisimo funkciju f : Nk → Nk ovako:

F(x) ={f(x) ako je xrazlicito od j0 i i0 ako je x= j0}
Ocito je funkcija F : Nk→ Nk 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 Nk \ {i0} tada iz sirjektivnosti funkcoje F i njene definicije slijedi da postoji x iz Nk takav da je f(x) = y.
2. Ako je y = i0 tada imamo f(k + 1) = i0.
3. Ako je y = k + 1 tada imamo f(j0) = k + 1 ).