Relacja binarna

[Darry]

Dla binarnej relacji \(\displaystyle{ R}\) w \(\displaystyle{ X}\) i \(\displaystyle{ x, y \in X}\) niech \(\displaystyle{ xSy}\) wtedy i tylko wtedy, gdy istnieje skończony ciąg \(\displaystyle{ x_{1}, x_{2}, . . . , x_{n}}\) taki, że \(\displaystyle{ x_{1} = x, x_{n} = y}\) i \(\displaystyle{ x_{i}Rx_{i+1} }\) dla każdego \(\displaystyle{ i = 1, 2, . . . , n − 1}\). Udowodnić, ze \(\displaystyle{ S}\) jest najmniejsza relacją przechodnią zawierającą \(\displaystyle{ R}\).

Myślę, że rozumiem treść, ale nie mam żadnego pomysłu jak wpaść na rozwiązanie.

[Jan Kraszewski]

Pokazujesz, że:
1. \(\displaystyle{ S}\) jest przechodnia.
2. \(\displaystyle{ R \subseteq S}\)
3. \(\displaystyle{ S}\) jest najmniejszą relacją spełniającą 1. i 2. - wystarczy wziąć dowolną relację \(\displaystyle{ T}\) spełniającą 1. i 2. i pokazać, że \(\displaystyle{ S \subseteq T.}\)

JK

[Darry]

O ile pierwsze dwa udało mi się pokazać, o tyle mam problem z wykazaniem punktu 3

[Jan Kraszewski]

A jaki masz problem?

Ustalasz dowolną parę \(\displaystyle{ \left\langle x,y\right\rangle\in S }\), czyli istnieje wspomniany ciąg \(\displaystyle{ x_{1}, x_{2}, . . . , x_{n}}\) taki, że \(\displaystyle{ x_{1} = x, x_{n} = y}\) i \(\displaystyle{ x_{i}Rx_{i+1} }\) dla każdego \(\displaystyle{ i = 1, 2, . . . , n − 1}\). Zauważ, że z Twoich założeń wynika, że \(\displaystyle{ x_{i}Tx_{i+1} }\) dla każdego \(\displaystyle{ i = 1, 2, . . . , n − 1}\), a ponieważ \(\displaystyle{ T}\) jest przechodnia, więc pozostaje prosta indukcja by pokazać, że \(\displaystyle{ \left\langle x,y\right\rangle=\left\langle x_1,x_n\right\rangle \in T.}\)

JK