2. előadás tételei
Kompozíció inverzének disztributivitása
\[
(R\circ S)^{-1} = S^{-1} \circ R^{-1}
\]
Adott S és R reláció, bizonyítsuk be, hogy a komponáltjuk inverze a sorrend felcserélésével felbontható
Bizonyítás
\[\begin{array}{ccl}
(z,x)\in (R\circ S)^{-1} &\quad& \\
\Updownarrow &\leftarrow& \text{1. Inverz definíciója}\\
(x,z) \in R\circ S \\
\Updownarrow &\leftarrow& \text{2. Kompozíció definíciója}\\
\exists y:(x,y) \in S\quad\land\quad(y,z) \in R \\
\Updownarrow &\leftarrow& \text{3. Inverz definíciója}\\
\exists y:(y,x)\in S^{-1}\quad\land\quad(z,y) \in R^{-1} \\
\Updownarrow &\leftarrow& \text{4. Kompozíció definíciója}\\
(z,x) \in S^{-1} \circ R^{-1} \\
\end{array}\]
Magyarázat
- Lényegében, az inverz definíciója arra vezet, hogy ha \((a,b)\) páros benne van egy \(S\) relációban, akkor az \(S^{-1}\)-ben a \((b,a)\)-nak kell benne lennie.
- A kompozíció definíciója miatt ha a komponált tagokat külön vesszük, akkor kell, hogy közöttük legyen egy köztes elem (a példában \(y\)).
- Illetve vegyük észre, hogy a kompozíció jobb asszociatív, a sorrend "felcserélődik", tehát a leg jobboldali kell, hogy először visszatérjen értékkel, olyan, mint \(R(S(x))\)
- Az inverz definíciója újból jó volt arra, hogy a sorrendet elemenként megcseréljük, és így visszajön az inverz
- A kompozíció definíciója meg arra jó, hogy a megcserélt köztes elem miatt újra összeragasszuk a két függvényt, csak lássuk, ahogy a sorrend megfordult
- Ta-da 🧨