Matematické Fórum

drabi · 07. 11. 2012 14:42

Ahoj, mám problém s úkolem. Jako vždy na přednášce neprobráno, na cvičení se to nestihlo, tak se s tím lopotím sama:(

Máme $X$ neprázdnou množinu, označme $Eq(X)$ množinu všech ekvivalencí na $X$ uspořádanou inkluzí.
Mám nakreslit Hasseův diagram pro $Eq(\{1,2,3\})$ a dokázat, že $Eq(X)$ je vždy svaz.

Tak ten rozklad je(?)
$R_1 = \{ \{1\},\{2\},\{3\} \}$
$R_2 = \{ \{1,2\},\{3\} \}$
$R_3 = \{ \{1\},\{2,3\} \}$
$R_4 = \{ \{1,3\},\{2\} \}$
$R_5 = \{ \{1,2,3\} \}$

a svaz to je pro to, že jako supremum můžeme brát celou tu množinu X a infimum jednoprvkové množiny?

Prosím poraďte, dost v tom plavu:(

kompik · 07. 11. 2012 18:43

↑ drabi:
To ze je to zvaz znamena, ze ak maz hocijaku mnozinu $\mathcal M$ ekvivalencii na $X$ , tak pre nu existuje infimum a supremum.

Co presne znamena, ze $I$ je infimum mnoziny $\mathcal M$ ? Ma to byt dolne ohranicenie, teda $(\forall R\in\mathcal M) I\subseteq R$ . Ma to byt najvacsie horne ohranicenie, teda $(\forall J\in Eq(X))[((\forall R\in\mathcal M) J \subseteq M) \Rightarrow J\subseteq R]$ .

Supremum je podobne, len treba vsade obratit inkluzie.

S infimom to pojde lahko - staci ti dokazat, ze prienik hocijakeho systemu relacii ekvivalencie je relacia ekvivalencie.

So supremom to nejde podobne - zjednotenie relacii ekvivalencie nemusi byt relacia ekvivalencie. Ale snad by mohol pomoct tranzitivny uzaver zjednotenia. (T.j. bolo by treba ukazat, ze ak vezmes nejake relacie ekvivalencie, zjednotis ich a z toho spravis tranzitivny uzaver, dostanes relaciu ekvivalencie.)

Nieco sa da najst napriklad na Planetmath.

A ked do google (alebo google books) napises: lattice "equivalence relations", tak urcite najdes kopec dalsich uzitocnych odkazov.

drabi · 08. 11. 2012 12:19

↑ kompik:
Ahoj, díky za reakci. Už mi to začíná být jasnější.
Ten Hasseův diagram už mám. Je mi jasné, co je infimum i supremum, jenže nějak nevím, jak to dokázat.
S tím infimem: Tak je jasné, že výsledná množina bude reflexivní, symetrická.. ale nevím jak ukázat, že je tranzitivní
se supremem, tak tranzitivní je jasné z toho jak je to "sjednocení" definované..
pak nutně bude i reflexivní a symetričnost mi připadá opět zřejmá.
Je to tak?

jarrro · 08. 11. 2012 12:25 — Editoval jarrro (08. 11. 2012 12:27)

ak patria nejaké dvojice do prieniku tak patria do každého prenikanca a každý prenikanec je tranzitívny teda do každého patrí "príslušná tranzitívna dvojica" teda tá "príslušná tranzitívna dvojica" patrí aj do prieniku
skôr bude viac roboty s tým tranzitívnym uzáverom

kompik · 08. 11. 2012 12:26

drabi napsal(a):
S tím infimem: Tak je jasné, že výsledná množina bude reflexivní, symetrická.. ale nevím jak ukázat, že je tranzitivní

Pomocne tvrdenie: Ak $R_i$ je tranzitivna pre kazde $i\in I$ (pricom $I$ je lubovolna neprazdna mnozina) tak aj $R=\bigcap_{i\in I} R_i$ je tranzitivna.

Nacrt dokazu:
$(x,y)\in R \land (y,z)\in R$ $\Rightarrow$ $(\forall i\in I) (x,y)\in R_i \land (y,z)\in R_i$ $\Rightarrow$ $(\forall i\in I) (x,z)\in R_i$ $\Rightarrow$ $(x,z)\in R$

Skus si to, co som tam zapisal symbolicky, prelozit do ludskej reci a detailnejsie rozmysliet preco platia tie jednotlive kroky.

drabi napsal(a):
se supremem, tak tranzitivní je jasné z toho jak je to "sjednocení" definované..
pak nutně bude i reflexivní a symetričnost mi připadá opět zřejmá.
Je to tak?

Ano, zjednotenie reflexivnych je reflexivna, zjednotenie symetrickych je symetricka, este treba zdovodnit, ze tranzitivny uzaver tieto vlastnosti tiez nepokazi.
(Suhlasim s tym, ze to je pomerne zrejme, ale ak to mas odovzdat cviciacemu ako du, tak tam asi zdovodnenie, ze ti to pripada zrejme stacit nebude, treba nejako zmysluplne zapisat, preco to plati.)

drabi · 08. 11. 2012 12:58

↑ jarrro: ↑ kompik:
díky moc

↑ kompik:
stačí tedy např. nějak podrobněji definovat to sjednocení a pak by už to mělo být zřejmé (doopravdy)

tak to sjednocení
$(x,y) \in R_i, (y,z) \in R_j$ , potom $(x,y) \in R_i \cup R_j, (y,z) \in R_i \cup R_j, (x,z) \in R_i \cup R_j$

Stačí to takto?

kompik · 08. 11. 2012 13:08

↑ drabi:
Ak spravne rozumiem tvojmu prispevku, snazis sa dokazat, ze zjednotenie relacii ekvivalencie je relacia ekvivalencie? To nie je pravda - urcite lahko vymyslis kontrapriklad, ale ak nahodou nie, tak tu je nejaky link: http://math.stackexchange.com/questions … relations.

Este raz zopakujem - moj navrh bol, ze supremum v tom zvaze by mohlo vyzerat takto: Ak mas relacie ekvivalencie $R_i, i\in I$ , tak najprv vezmes ich zjednotenie $\bigcup_{i\in I} R_i$ a z toho urobis tranzitivny uzaver.

Este dodam, ze by si to mal robit pre lubovolny pocet relacii, nie iba konecne vela - ak ste nahodou nemali v zadani, ze robite iba s konecnou mnozinou.

Pridam este tento link, ak by nahodou pomohol vyjasnit nejake veci:
Confusion about the lattice formed by an equivalence relation - MSE

jarrro · 08. 11. 2012 13:12 — Editoval jarrro (02. 12. 2012 11:28)

čo sú R ? ak sú to ľubovoľné tranzitívne relácie tak
$$x, z$\in R_i\cup R_j$ nemusí platiť
tu sú všetky tranzitívne na dvojprvkovej množine
$T_{1}=\emptyset\nl T_{2}=\{$*,\sharp$,$\sharp,*$,$*,*$\}\nl T_{3}=\{$\sharp,*$,$*,\sharp$,$\sharp,\sharp$\}\nl T_{4}=\{$*,*$,$*,\sharp$\}\nl T_{5}=\{$\sharp,\sharp$,$\sharp,*$\}\nl T_{6}=\{$*,*$,$\sharp,\sharp$\}\nl T_{7}=\{$*,\sharp$,$*,*$\}\nl T_{8}=\{$\sharp,\sharp$,$*,\sharp$\}\nl T_{9}=\{$*,*$,$*,\sharp$,$\sharp,*$,$\sharp,\sharp$\}\nl T_{10}=\{$*,*$\}\nl T_{11}=\{$*,\sharp$\}\nl T_{12}=\{$\sharp,*$\}\nl T_{13}=\{$\sharp,\sharp$\}$
ale napr.
$T_{8}\cup T_{12}$ tranzitívna nie je

kompik · 08. 11. 2012 13:20 — Editoval kompik (08. 11. 2012 13:58)

Ak ste nahodou uz mali taku vetu, ze ak ciastocne usporiadana mnozina ma lubovlne infima, tak uz musi byt zvaz; tak vlastne so supremami sa clovek nemusi trapit. Myslim si vsak, ze vobec nezaskodi zamysliet sa nad tym, ako tam vyzeraju suprema.

Tuto vec som si neuvedomil, ale robia to tak napriklad Burris, Sankappanavar: A Course in Universal Algebra v Theorem 4.5. (Ta kniha je volne pristupna online.)

drabi · 12. 11. 2012 22:47

↑ jarrro: ↑ kompik:
ahoj, díky za reakci. Myslela jsem to stejně jako vy, akorát jsem se špatně vyjádřila.
Už jsem to nějak dala dohromady, tak snad dobře. Každopádně děkuji za rady:)

Matematické Fórum

#1 07. 11. 2012 14:42

svaz

#2 07. 11. 2012 18:43

Re: svaz

#3 08. 11. 2012 12:19

Re: svaz

#4 08. 11. 2012 12:25 — Editoval jarrro (08. 11. 2012 12:27)

Re: svaz

#5 08. 11. 2012 12:26

Re: svaz

drabi napsal(a):

drabi napsal(a):

#6 08. 11. 2012 12:58

Re: svaz

#7 08. 11. 2012 13:08

Re: svaz

#8 08. 11. 2012 13:12 — Editoval jarrro (02. 12. 2012 11:28)

Re: svaz

#9 08. 11. 2012 13:20 — Editoval kompik (08. 11. 2012 13:58)

Re: svaz

#10 12. 11. 2012 22:47

Re: svaz

Zápatí