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

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