Tranzitivita I
Úloha číslo: 3357
Dokažte, že relace \(R \subseteq X\times X\) je tranzitivní, právě když \(R\circ R\subseteq R\).
Řešení
Důkaz rozdělíme na dvě implikace.
1. Pokud \(R\) je tranzitivní, tak z definice složené relace
\(R\circ R =\{(x,z): \exists y: xRy \land yRz\}\)
vyplývá, že jakmile existuje takové vhodné \(y\), platí díky tranzitivitě \(R\) i \(xRz\), neboli
\(\{(x,z): \exists y: xRy \land yRz\} \subseteq R\)
2. Nyní předpokládejme, že platí \(R\circ R\subseteq R\).
Pokud nějaká \(x\), \(y\) a \(z\) splňují \(xRy \land yRz\), potom z definice složené relace platí \(x(R\circ R)z\) a za předpokladu \(R\circ R\subseteq R\) nyní odvodíme i kýžený vztah \(xRz\).
Formálně zapsáno:
\(\forall x,y,z: xRy \land yRz \ \Longrightarrow\ x(R\circ R)z\ \Longrightarrow\ xRz\)