|
Отношение S={(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)} на A={1,2,3,4,5} является транзитивным? задан 28 Сен '14 12:51 
termit |
|
Отношение наз. транзитивным, если для любых $%(x,y); (y,z)$%, принадлежащих отношению, пара $%(x,z)$% также принадлежит этому отношению. Т.е. происходит "склеивание" второго элемента первой пары и первого элемента второй пары, а остаются первый элемент первой пары и второй элемент второй пары. Например, $%(2,3) i (3,4)$% должна быть пара $%(2,4)$% - она есть. Проверяем далее: $%(2,3),(3,5)$%, пара $%(2,5)$% - есть. Далее: $%(2,4),(4,5)$%, пара $%(2,5)$% - есть. Далее есть пара $%(2,5)$%, но с $%5$% ничего не начинается, следовательно, и проверять ничего не нужно. Идем далее: $%(3,4),(4,5)$%, пара $%(3,5)$% - есть; $%(3,5)$%, с $%5$% ничего не начинается, проверять ничего не нужно. Аналогично и с парой $%(4,5)$%. Отношение есть транзитивным. отвечен 28 Сен '14 13:02 
Lyudmyla Спасибо. Я правильно нашел $%S*S={(2,4),(2,5),(3,5),(4,5)}$%?
(28 Сен '14 13:24)
termit
@termit: пара $%(4,5)$% у Вас здесь лишняя, она в $%S$% ни с чем дальнейшим не стыкуется. Транзитивность отношения $%S$% здесь просто выводится из того факта, что $%S$% есть отношение "меньше" на подмножестве $%{2,3,4,5}$%, а про это отношение мы знаем, что оно транзитивно, из свойств неравенств.
(28 Сен '14 15:57)
falcao
Я думал если композиция отношения с самим собой совпадает с отношением, то отношения является транзитивным.
(28 Сен '14 17:49)
termit
Для транзитивности отношения необходимым и достаточным является включение $%S\circ S\subseteq S$%. Равенство при этом может и не иметь места, как в указанном примере.
(28 Сен '14 19:02)
falcao
|
