From veky@student.math.hr Fri Jan 23 22:51:15 2004 Subject: Re: Malo o skupovima Lines: 211 Message-ID: <slrnc135cd.adk.veky@student.math.hr> References: <btku2b$9np$1@ls219.htnet.hr> In article <btku2b$9np$1@ls219.htnet.hr>, John S. Myth wrote: >Naisao sam na dosta nejasnoca citajuci onu knjigu (Pavle Papic: "Uvod u >teoriju skupova"), pa... Bilo bi cudno da nisi. ;-) >Evo pitanjaca (Veky, gopher it ;-)): Eh... da si stavio neki drugi protokol, mozda bih i prije odgovorio. p-: [:-)] >1. Koja je razlika izmedu najmanjeg i minimalnog, te najveceg i >maksimalnog elementa skupa? Dakle, ovako. (Parcijalni) uredaj je binarna relacija koja je irefleksivna i tranzitivna (alternativno, refleksivna&antisimetricna&tranzitivna , ali meni se vise svida ova gornja karakterizacija:-). Uoci da medu svojstvima nigdje nije navedeno nesto sto se zove totalnost, odnosno da opcenito (ie, za sve x,y ) vrijedi x<y V x=y V y<x . Uredaj za kojeg vrijedi jos i to zove se totalan uredaj. No opcenito, ima smisla pricati o uredaju i bez tog svojstva - npr. genericki primjer za parcijalan uredaj (cak u tom smislu da se svaki parcijalni uredaj moze svesti na njega) je relacija "biti podskup" (na partitivnom skupu univerzalnog skupa). Naravno, ima sva svojstva koja treba imati, ali cim univerzalni skup ima bar 2 elementa a i b , jasno je da su {a} i {b} neusporedivi. E sad, minimalni i najmanji element su dvije generalizacije pojma minimuma kod totalnih uredaja, uzevsi u obzir i cetvrtu mogucnost u onoj disjunkciji gore, da su elementi neusporedivi. "minimalni" je slabija varijanta, ona dopusta neusporedivost i jedino ne dopusta da netko bude manji, dok je "najmanji" jaca varijanta, i zabranjuje cak i neusporedivost. Analogno za "maksimalan" i "najveci". Ukratko:vn minimalni element: onaj od kojeg nijedan nije (strogo) manji najmanji element: onaj koji je manji ili jednak svima maksimalni element: onaj koji nije manji ni od jednog najveci element: onaj od kojeg su svi manji ili jednaki Tvrdnje (koje mozes pokusati dokazati): najmanji element je ujedno i minimalan, i to jedini takav. Stovise, najmanji element postoji ako i samo ako postoji jedinstveni minimalni element, i to je onda upravo taj (drugim rijecima, ako postoji vise minimalnih elemenata, tada najmanji element ne postoji - obrat ove tvrdnje ne vrijedi). U totalno uredenom skupu minimalan element je nuzno jedinstven, i time ujedno i najmanji. Primjeri: Gornji primjer, P(U) ureden relacijom C (podskup). Najmanji element je 0 , najveci je U . P(U)\-{0} s istom relacijom (;card U>=2 ): najveci je i dalje U , najmanjeg vise nema, ima hrpa minimalnih: za svaki x@U , {x} je minimalan. * |N (skup prirodnih brojeva), ureden (nestrogo) relacijom | (dijeli). Najveceg ni maksimalnih nema, najmanji je 1 . |N^* (=|N\-{1} ), ista relacija. Nema maksimalnih, nema najmanjeg, ali zato ima beskonacno minimalnih: svi prosti brojevi. >2. Sto je prerez, sto njegov granicni element, sto skok, a sto praznina >(u potpuno uredenom skupu)? (Ovdje terminologija nije bas standardizirana. Nadam se da ces uspjeti uspostaviti parcijalni izomorfizam ipak.:) Neka je (X,<) totalno (to je valjda ono sto Papic zove "potpuno"... ja bih pojam "potpunost uredaja" ipak sacuvao za nesto drugo - sto inace ima veze s prerezima, ali na jedan drugi nacin:) ureden skup. Prerez u X je particija od X (dakle, X=AUB , AnB=0 , A!=0 , B!=0 ), takva da je A '<'-zatvoren (dakle, x<a@A => x@A ), a B je '>'-zatvoren ( b@B & b<y => y@B ). Skok je vjerojatno prerez kod kojeg A ima najveci element, i B ima najmanji. Praznina je dualno tome: prerez kod kojeg niti A ima najveci elemnnt, niti B ima najmanji. Prerez s granicnim elementom je prerez kod kojeg A ima najmanji, illi (ekskluzivno ili) B ima najveci element (on se onda zove granicni element). Dakle, svaka lijevo-desno particija od X (takva da vrijedi A<B ) je ili skok ili praznina ili prerez s granicnim elementom. Primjeri: Skup je |N , relacija je standardni < (kao i u svim donjim primjerima). ({1,2},{3,4,....}) je skok. * Skup je skup svih najvise prebrojivih kardinalnih brojeva - dakle cine ga 0 , prirodni brojevi i alef_0 . (|N_0,{alef_0}) je prerez s granicnim elementom alef_0 . * Skup je |R . (<-oo,pi],<pi,+oo>) je prerez s granicnim elementom pi . * (Univerzalni) skup je |Q . ({x:x<0Vx^2<5},{x:0<x&5<x^2}) je praznina. >3. Sto su klasa ekvivalencije i kvocijentni skup? [lesson title="releqs i neke jako zanimljive posljedice"] Binarna relacija na nekom skupu X je ~~:X--X , odnosno relacija izmedu X i X , dakle ~~ C= XxX (podskup Kartezijevog kvadrata od X ). Relacija ekvivalencije je binarna relacija koja je simetricna i tranzitivna. Relacija ekvivalencije na X je relacija ekvivalencije koja je uz to i refleksivna na X (dakle, jednakost na X je podrelacija od ~~ ). Neka je X neki (univerzalni) skup, i ~~ releq na njemu. Za bilo koji x , klasa ekvivalencije od x s obzirom na ~~ je {y:x~~y} . Oznacava se s [x]_~~ . Kvocijentni skup je tada X/_~~ := {[x]_~~}_x , dakle skup svih klasa. On predstavlja X na kojem je apstahirana razlicitost elemenata za koje vrijedi ~~ - ono sto je na njemu = , tocno to je na X relacija ~~ . Zanimljive tvrdnje: Za bilo koju releq ~~ na X , X/_~~ je particija od X - dakle, sve klase su neprazne, medusobno disjunktne, i unija svih njih je citav X . Stovise, vrijedi i obrat: za svaku particiju B od X , postoji releq ~~ na X , takva da je X/_~~ upravo B . (mozda se isplati pogledati i http://www.math.hr/~veky/em/vjezbe/relequiv.html ) Primjeri: Skup je |Z . Relacija je ==(.3) , odnosno "biti kongruentan modulo 3 ". x i y su u toj relaciji :akko 3 dijeli x-y . To je relacija ekvivalencije, i ima 3 klase: [0]_{==(.3)}={0,3,-3,6,-6,9,-9,....}=3|Z [1]_{==(.3)}={1,4,-2,7,-5,10,-8,....}=3|Z+1 [2]_{==(.3)}={2,5,-1,8,-4,11,-7,....}=3|Z+2 Kvocijentni skup |Z/_{==(.3)} se ponekad oznacava i sa |Z/3|Z (ili cak sa |Z_3 , ali to je ipak pretjerano pojednostavljenje), i to je skup od 3 elementa na kojima se moze definirati zbrajanje i mnozenje na prirodan nacin i tako se organizirati cak u polje - prepustam tebi da raspises ako vec toliko volis polja:). * Skup je skup svih pravaca u ravnini. Relacija je || ("biti paralelan"). To je releq , i klasa ekvivalencije nekog pravca je njegov _smjer_ (dakle, skup svih pravaca paralelnih s njim). Kvocijentni skup je skup svih smjerova u ravnini. * (Sad par sokantnih;) Skup je |Nx|N - dakle, skup parova prirodnih brojeva. Relacija je ~~_+ , definirana na tim parovima sa (a,b)~~_+(c,d) :<=> a+d=b+c . To je releq, i klasa para (a,b) se zove (cjelobrojna) razlika a i b . Buduci da je |N totalno ureden, imamo 3 mogucnosti: a>b . Tad postoji jedinstveni prirodan broj n takav da je (a,b)~~_+(n',1) (gdje je n' sljedbenik od n ), i klasa od (a,b) se tada oznacava s +n (ili jednostavno n ako embedamo |N u tu strukturu). a=b . Lako se vidi da su svi parovi istih medusobno ekvivalentni, odnosno ekvivalentni (1,1) , cija se klasa oznacava s +0 (ili 0 ako embedamo i konacne ordinale tu:). a<b . Tad postoji jedinstveni n@|N takav da je (a,b)~~_+(1,n') , i klasa se u tom slucaju oznacava s -n . Kvocijentni skup zove se skup cijelih brojeva, i oznacava sa |Z . * Skup je |Zx|N - Kartezijev produkt upravo definiranog skupa sa |N . Relacija je ~~_* , ciju definiciju pogodi (hint: analogna je ~~_+ :). To je releq, i klasa para (a,b) s obzirom na tu relaciju zove se razlomak a kroz b , i oznacava a/b . Svaki par ekvivalentan je nekom (p,q) gdje su p i q relativno prosti. Kvocijentni skup se naravno zove skup racionalnih brojeva, i oznacava s |Q . * Skup je |Q^|N (remember definiciju potenciranja skupova? Ovo je dakle skup svih racionalnih nizova). Ali na njemu necemo zadati releq. ;-> Unutar njega uzmimo skup svih Cauchyjevih nizova, dakle onih (a_n)_n^|N za koje vrijedi (A_eps@|Q^+)(E_n@|N)(A_k,p@|N;>n)(|a_k-a_p|<eps) . Na njima zadajmo ~~_e ovako: (a_n)_n^|N ~~_e (b_n)_n^|N :<=> :<=>(A_eps@|Q^+)(E_n@|N)(A_k@|N;>n)(|a_k-b_k|<eps) To je releq na skupu Cauchyjevih racionalnih nizova. Klasa od (a_n)_n^|N se zove limes tog niza, i oznacava s lim_n a_n . ((Svaki takav niz je, inace, ekvivalentan jedinstvenom (Cauchyjevom) nizu decimalnih razlomaka ciji se nazivnici ponasaju kao geometrijski niz s pocetkom 1 i kvocijentom 10 , a brojnici zapisani kao stringovi cine rastuci niz u kojem se svaki sljedeci dobiva pomocu prethodnog dodavanjem jedne znamenke b_n , uz uvjet da te znamenke nisu skoro sve (dakle, sve osim konacno mnogo) jednake 9 . Ponekad se klase zapisuju kao "beskonacni stringovi" tih znamenaka.)) Kvocijentni skup se zove skup realnih brojeva, i oznacava s |R . * (Ne, nismo gotovi.;) Skup je |R[x] - dakle, skup svih polinoma s realnim koeficijentima, u jednoj varijabli koja se zove x . Relacija na njemu je ==(.(x^2+1)) , dakle kongruencija modulo x^2+1 , odnosno p i q su u relaciji ako je njihova razlika kao polinom djeljiva polinomom x^2+1 . Pokazuje se da je svaki polinom ekvivalentan nekom (jedinstvenom) najvise linearnom, dakle nekom oblika ax+b , gdje su a i b realni brojevi. Njegova klasa se zove kompleksan broj s realnim dijelom b i imaginarnim dijelom a , i oznacava s b+ai . Kvocijentni skup se zove skup kompleksnih brojeva, i oznacava s |C . [/lesson] * Zanimljivo, hm? :-) >Ako/kad to shvatim, prelazim na trece poglavlje. >'Till then I'm stalemated. ;-) Nisi. Imas jos hrpu zgodnih problema kojima se mozes baviti. ;-) >Formalizacija mi ovdje nije toliko bitna, toga imam napretek u knjizi. Znam. Namjerno sam zato \relax-ao stvar. :-) >Mozda bi bilo dobro da ukljucis koji > primjer za sve skupa. Vec mi se vrti u >glavi od samih simbola. ;-))))) ASCII je isto hrpetina simbola. Nadam se, ipak malo prijateljskijih... :-) -- Veky ... really loved a woman ...