relacja równoważności

[wiosna]

Proszę o pomoc. Nie rozumiem definicji sumy relacji tzn.
Jeśli \(\displaystyle{ q,v}\)oznaczają relacje równoważności to\(\displaystyle{ q v}\) jest najmniejszą relacją równoważności zawierającą zarówno \(\displaystyle{ q}\) jak i \(\displaystyle{ v}\). Proszę o jakiś konkretny przykład bo nie potrafię sobie tego wyobrazić.

[klaustrofob]

np. w zbiorze liczb całkowitych: R(a,b) a i b dają tę samą resztę z dzielenia przez 6 // r(a,b) a i b dają tę samą resztę z dzielenia przez 15. sumą relacji jest relacja: q(a,b) dają tę samą resztę z dzielenia przez 3.

dowód: oczywiście, wskazana relacja zawiera obie relacje - jeżeli para liczb daje tę samą resztę z dzielenia przez 15 i tę samą z dzielenia przez 6, to również przy dzieleniu przez 3 liczby dadzą te same reszty. jest najmniejsza: jeżeli jakaś inna relacja grupuje pary liczb o takich samych resztach z dzielenia przez 15 i takich samych resztach z dzielenia, to pary te mają takie same reszty z dzielenia przez 3, tj. opisana wyżej relacja jest zawarta w "domniemanej" mniejszej.

[Qń]

Dla jasności: suma relacji równoważności w ogólności nie jest relację równoważności (bo na ogół nie jest to relacja przechodnia).

Jeśli natomiast dla relacji \(\displaystyle{ r,p}\) oznaczymy przez \(\displaystyle{ \sigma (r \cup p)}\) najmniejszą relację równoważności zawierającą sumę \(\displaystyle{ r}\) i \(\displaystyle{ p}\), to żeby ją dobrze określić, trzeba dodać do \(\displaystyle{ r \cup p}\) wszystkie takie pary, żeby całość była relacją przechodnią.

Na przykład, dla
\(\displaystyle{ A=\{1,2,3\} \\
r=\{(1,1)(2,2),(3,3),(1,2),(2,1)\} \\
p=\{(1,1)(2,2),(3,3),(1,3),(3,1)\}}\)
(obie relacje są relacjami równoważności), mamy:
\(\displaystyle{ r \cup p = \{ (1,1)(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)\}}\)
Żeby znaleźć najmniejszą relację równoważności zawierającą ten zbiór, należy dodać do niego takie pary, żeby była to relacja przechodnia, czyli \(\displaystyle{ (3,2),(2,3)}\), zatem
\(\displaystyle{ \sigma (r \cup p) = \{ (1,1)(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2) = A^2}\)

Oczywiście przykład klaustrofoba też jest dobry.

Q.