Buďte \(R\) a \(S\) tranzitivní relace na téže množině. Které z následujících relací jsou také tranzitivní?
Varianta
\(R\cup S\)
Řešení
Vezměme na \(X=\{a,b,c\}\) tranzitivní relace \(R=\{(a,b)\}\) a \(S=\{(b,c)\}\). Sjednocení \(R\cup S\) obsahuje obě dvojice, ale nikoli dvojici \((a,c)\).
Odpověď
Sjednocení tranzitivních relací nemusí být tranzitivní.
Varianta
\(R\cap S\)
Řešení
Jsou-li \((a,b),(b,c)\in R\cap S\), potom jsou tyto dvě dvojice v obou relacích. Díky tranzitivitě \(R\) i \(S\) je v obou dvou relacích i dvojice \((a,c)\).
Odpověď
Relace \(R\cap S\) je tranzitivní.
Varianta
\(R\setminus S\)
Řešení
Obsahuje-li např. \(R\) všechny dvojice na dvojprvkové množině a \(S\) jen obě reflexivní dvojice tamtéž, potom jsou obě tranzitivní, ale \(R\setminus S\) nikoli.
Odpověď
Relace \(R\setminus S\) nemusí být tranzitivní.
Varianta
\(R\mathbin{\Delta}S\)
Řešení
Obsahuje-li např. \(R\) všechny dvojice na dvojprvkové množině a \(S\) jen obě reflexivní dvojice tamtéž, potom jsou obě tranzitivní, ale \(R\mathbin{\Delta}S=R\setminus S\) nikoli.
Odpověď
Relace \(R\mathbin{\Delta}S\) nemusí být tranzitivní.
Varianta
\(R\circ S\)
Řešení
Vezměme na \(X=\{a,b,c\}\) tranzitivní relace \(R=\{(a,a),(b,c)\}\) a \(S=\{(a,b),(c,c)\}\). Složení \(R\circ S\) obsahuje obě dvojice \((a,b),(b,c)\), ale nikoli dvojici \((a,c)\).
Odpověď
Složení tranzitivních relací nemusí být tranzitivní.
Varianta
\(R^{-1}\)
Řešení
Jsou-li \((a,b),(b,c)\in R^{-1}\), potom jsou dvojice \((c,b),(b,a)\in R\). Díky tranzitivitě \(R\) máme \((c,a)\in R\) a tedy \((a,c)\in R^{-1}\).