Tranzitivita II
Úloha číslo: 3358
Dokažte, že pro každou relaci \(R \subseteq X\times X\) platí, že relace \(T\), definovaná předpisem \(T=\bigcup\limits_{i=1}^\infty R^i\), je tranzitivní.
Nápověda
Co lze vyvodit ze vztahu \(xTy\)?
Řešení
Předpokládejme \(xTy \land yTz\).
Všimneme si, že
\(xTy \ \Longrightarrow\ (x,y)\in \bigcup\limits_{i=1}^\infty R^i \ \Longrightarrow\ \exists i: (x,y)\in R^i\).
neboť, náleží-li prvek (i nekonečnému) sjednocení, musí náležet alespoň jedné z množin.
Podobně \(yTz \ \Longrightarrow\ \exists j: (y,z)\in R^j\).
Ze skládání relací ovšem plyne, že
\(xR^iy \land yR^jz \ \Longrightarrow\ xR^{i+j}z \ \Longrightarrow\ xTz\),
což už dokazuje tranzitivitu \(T\).