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 ...