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\).

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze