Matematické Fórum

NoTender · 29. 11. 2013 19:06

Dobrý den, mám takovýto příklad: Máme množinu všech ekvivalencí na množině o třech prvcích s uspořádáním inkluzí. Vyjádřete svazové uspořádání jako algebraicky definované svazy. Vyjádřete operace spojení a průseku. Mohl by mě někdo trošku nasměrovat ke správnému řešení? Nejsem si příliš jistý co s tím dělat. Ekvivalence na množině o 3 prvků jsem schopen vypsat. V uspořádání inkluzí a dalším si nejsem vůbec jistý. Děkuji za případnou odpověď.

Andrejka3

Ahoj,
ekvivalence na množině $A$ je binární relace.... takže jde vyjádřit jako jistá podmnožina množiny $A^2=A\times A$ . Pokud si tu ekvivalenci označíme jako $E$ , pak $E$ obsahuje všechny uspořádané dvojice prvků takové, jež jsou spolu ekvivalentní.
Vypiš pro začátek všechny ekvivalence na tříprvkové množině.

NoTender · 30. 11. 2013 13:40

↑ Andrejka3:
Ahoj, díky za odpověď. Jak říkám, to už jsem vypsal, ale jak s tím hnout dál, to netuším. :(

Andrejka3 · 30. 11. 2013 14:08

↑ NoTender:
Tak to vypiš tady, jinak Ti neporadím :(

NoTender · 30. 11. 2013 14:44

Omlouvám se :)
A = {a,b,c}
Relace ekvivalence:
1) (a,a), (b,b), (c,c)
2) (a,a), (b,b), (c,c), (a,b), (b,a)
3) (a,a), (b,b), (c,c), (a,c), (c,a)
4) (a,a), (b,b), (c,c), (b,c), (c,b)
5) (a,a), (b,b), (c,c), (a,b), (b,a), (a,c), (c,a), (b,c), (c,b)

Andrejka3

↑ NoTender:
Teď je můžeš začít porovnávat relací inkluze: $\subset$ (s dovolením mám na mysli neostrou inkluzi, ale píšu jen tento znak).
Například $1) \subset 2)$ . Samozřejmě, protože každá ekvivalence je reflexivní a $1)$ je nejmenší reflexivní relace, platí $1) \subset X$ , kde $X \in \mathrm{Eq}\{a,b,c\}$ (patří do množiny všech ekvivalencí množiny $\{a,b,c\}$ ). Můžeš najít nevjětší prvek, můžeš nakreslit Hasse diagram...

Teď potřebuji vědět, jestli znáš svaz všech podmnožin dané množiny (uspořádání dané inkluzí).
Zatím je všemu rozumět? Napadá Tě už, co odpovídá operaci $\wedge$ ?

NoTender · 30. 11. 2013 15:21

↑ Andrejka3:
Takže uspořádání inkluzí se vytvoří tak, že vpravo bude ta "největší množina" a směrem doleva budou její podmnožiny? Pořád mi ani není jasné, jak z toho zjistím největší prvek. Znamená to tedy, že tím prvkem bude celá jedna relace ekvivalence, nebo její jednotlivé členy?

Andrejka3

↑ NoTender:
Záleží na souvislostech, kdy něco nazveme množinou a kdy prvkem. V tomhle příkladu sice jednotlivé ekvivalence jsou množiny -- jisté podmnožiny $\{a,b,c\}\times \{a,b,c\}$ , ale každá ekvivalence je prvkem svazu všech ekvivalencí $\mathrm{Eq}\{a,b,c\}$ .
Zjistil jsi, že ten svaz má celkem 5 různých ekvivalencí. Ty jsou uspořádané inkluzí, což je obvyklá relace 'býti podmnožinou'.

Navrhuju použít následující označení ekvivalencí: Označme $A=\{a,b,c\}$
$I$ = 1) (a,a), (b,b), (c,c)
$I_{a,b}$ =2) (a,a), (b,b), (c,c), (a,b), (b,a)
$I_{a,c}$ =3) (a,a), (b,b), (c,c), (a,c), (c,a)
$I_{b,c}$ =4) (a,a), (b,b), (c,c), (b,c), (c,b)
$A^2=A\times A$ 5) (a,a), (b,b), (c,c), (a,b), (b,a), (a,c), (c,a), (b,c), (c,b)

Takže uspořádání inkluzí se vytvoří tak, že vpravo bude ta "největší množina" a směrem doleva budou její podmnožiny?

Skoro, lepší je psát to do Hasse diagramu, dole menší, nahoře větší. To uspořádání není lineární. Všimni si:
$I_{a,b}\subset A^2$ , ale třeba ekvivalence $I_{a,b}$ , $I_{a,c}$ jsou neporovnatelné - ani jedna není podmnožinou druhé. V Hasse diagramu budou vedle sebe (nepovede od jedné cesta nahoru nebo dolů k druhé).
edit: Hasse diagram: http://en.wikipedia.org/wiki/Hasse_diagram
edit: špatná citace

NoTender · 30. 11. 2013 15:48

↑ Andrejka3:
Kristovy rány. Děkuju moc!!! Ani nevíš jakou jsi mi udělala radost, dumal jsem nad tím takovou dobu... Jsem rád, že je na světě pořád někdo, kdo rád poradí. :) Nejradši bych tě objal :D

NoTender · 30. 11. 2013 15:50

A ještě otázka.. co je tedy algebraicky definovaný svaz?

Andrejka3 · 30. 11. 2013 15:58

↑ NoTender:
To už jsme něco vyřešili? :)
↑ NoTender:
1)Svaz je algebra se dvěma binárními operacemi, $(L,\wedge,\vee)$ , které jsou asociativní, komutativní, idempotentní a platí zákon absorpce:
idempotence: $a\wedge a =a$ , anal pro $\vee$ ,
absorpce: $a\wedge (a\vee b)=a$ , $a\vee (a\wedge b)=a$ .

2) Uspořádaná množina $(L,\leq)$ je uspořádaná svazově, právě když každá dvouprvková podmnožina má infimum a supremum v $L$ .

Existuje přirozená bijekce mezi svazy a svazově uspořádanými množinami, v podstatě oba pojmy znamenají totéž.
Přechod od usporadane mnoziny ke svazu:
$a\wedge b = \inf\{a,b\}$ , $a\vee b=\sup\{a,b\}$ .
Prechod zpet:
$a\leq b \iff a\wedge b=a$ , (coz je ekvivalentni $a\vee b=b$ .)

Na to nemáte skripta?

NoTender

↑ Andrejka3:
To co jsi napsala, to všechno vím. Jenom přesně nechápu, co s tím tedy udělat, abych to vyjádřil jako algebraicky definovaný svaz. Stačí přes ty Hasseovy diagramy, nebo je to nějákým zápisem?
Edit: A ještě jeden, snad už poslední dotaz: Vydedukoval jsem, že operace průseku a spojení budou operace průniku a sjednocení. Nicméně ve chvíli, kdy sjednotím například relace (a,a), (b,b), (c,c), (a,b), (b,a) a
(a,a), (b,b), (c,c), (a,c), (c,a) tak výsledná relace bude (a,a), (b,b), (c,c), (a,b), (b,a), (a,c), (c,a). Pokud je to skutečně svaz, mělo by sjednocením vyjít supremum, což by měla být relace (a,a), (b,b), (c,c), (a,b), (b,a), (a,c), (c,a), (b,c), (c,b). Znamená to, že tedy tyto dva prvky nemají společné supremum?

Andrejka3 · 30. 11. 2013 17:01

↑ NoTender:
Hasse diagram spíše jen pro orientaci. Nevěděla jsem, co víš.
Jde o to zjistit, co je ten průsek a spojení v nějaké hezké řeči.

operace průseku a spojení budou operace průniku a sjednocení

Opravdu, operace průseku je průnik. Průnikem dvou ekvivalencí je ekvivalence a zároveň to je nejmenší množina, která obsahuje obě ekvivalence, takže největší z dolních závor, tj. infimum, tj. průsek.

Se sjednocením to je složitější, jak sis všimnul. Sjednocení by bylo spojením ve svazu všech podmnožin množiny $A^2$ například. My ale máme chudší strukturu. Pouze ekvivalence. Když provedeme sjednocení dvou ekvivalencí, dostaneme sice opět relaci a to nejmenší relaci, která je větší než obě ekvivalence, ale není zaručeno, že je výsledkem ekvivalence. Takže naše struktura není uzavřená na operaci sjednocení.

Ekvivalence je relace, jež je reflexivní, symetrická a tranzitivní.
Které vlastnosti zachová sjednocení? Které ne? Jak to opravit? Potřebujeme se dostat k nejmenší ekvivalenci toho svazu, která obsahuje sjednocení těch dvou ekvivalencí.

První, obecná cesta je napsat to jako průnik všech ekvivalencí, které obsahují sjednocení těch dvou ekvivalencí - to je stále ošklivé. Takže chceme najít něco lepšího.

NoTender · 30. 11. 2013 17:23

↑ Andrejka3:
Sjednocení by mělo zachovávat symetrii a reflexivitu. Nicméně nemusí zachovávat tranzitivitu, jak se tak zamýšlím. Co ale pak s tím, mě bohužel nenapadá.

Andrejka3

↑ NoTender:
Tranzitivní uzávěr $T(R)$ relace $R$ se spočítá:
$T(R)=\bigcup_{n\in \mathbb{N}}R^n$ .
Je to nejmenší transitivní relace, jež obsahuje relaci $R$ . Zároveň, zachovává symetrii i reflexivitu, takže operace spojení odpovídá tranzitivnímu uzávěru sjednocení.
$E\vee F = T(E\cup F)$ .
Pochopitelně, ten předpis uzávěru je u nás jednodušší, už proto že existuje konečně mnoho relací na $\{a,b,c\}$ , takže to jde napsat jako konečné sjednocení.
Nakonec, můžeš ověřit, že pro dvě ekvivalence je
$E\vee F = T(E\cup F)=G$ , kde
$G=\{(x,y)\in A^2;\:\exists k\in \mathbb{N}\:\exists z_i\in A:\:x=z_0Ez_1Fz_2Ez_3F\ldots z_k=y\}$ .

Andrejka3

Už nemáš otázky? V definici tranzitivního uzávěru ty mocniny relací znamenají skládání relací:
$R,S$ relace na $A$ , pak
$R\circ S=\{(x,y);\:\exists z:\:xRz\:\wedge\:zSy\}$ , $R^n = R \circ R^{n-1}$ .

Matematické Fórum

#1 29. 11. 2013 19:06

Algebraicky definované svazy

#2 30. 11. 2013 10:37 — Editoval Andrejka3 (30. 11. 2013 10:37)

Re: Algebraicky definované svazy

#3 30. 11. 2013 13:40

Re: Algebraicky definované svazy

#4 30. 11. 2013 14:08

Re: Algebraicky definované svazy

#5 30. 11. 2013 14:44

Re: Algebraicky definované svazy

#6 30. 11. 2013 15:00 — Editoval Andrejka3 (30. 11. 2013 15:11)

Re: Algebraicky definované svazy

#7 30. 11. 2013 15:21

Re: Algebraicky definované svazy

#8 30. 11. 2013 15:34 — Editoval Andrejka3 (30. 11. 2013 15:45)

Re: Algebraicky definované svazy

#9 30. 11. 2013 15:48

Re: Algebraicky definované svazy

#10 30. 11. 2013 15:50

Re: Algebraicky definované svazy

#11 30. 11. 2013 15:58

Re: Algebraicky definované svazy

#12 30. 11. 2013 16:45 — Editoval NoTender (30. 11. 2013 16:50)

Re: Algebraicky definované svazy

#13 30. 11. 2013 17:01

Re: Algebraicky definované svazy

#14 30. 11. 2013 17:23

Re: Algebraicky definované svazy

#15 30. 11. 2013 18:03 — Editoval Andrejka3 (30. 11. 2013 18:04)

Re: Algebraicky definované svazy

#16 01. 12. 2013 11:08 — Editoval Andrejka3 (01. 12. 2013 11:09)

Re: Algebraicky definované svazy

Zápatí