Отношение S={(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)} на A={1,2,3,4,5} является транзитивным?

задан 28 Сен '14 12:51

изменен 28 Сен '14 17:31

10|600 символов нужно символов осталось
0

Отношение наз. транзитивным, если для любых $%(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

изменен 28 Сен '14 17:13

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Спасибо. Я правильно нашел $%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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×663

задан
28 Сен '14 12:51

показан
474 раза

обновлен
28 Сен '14 19:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru