дискретная-математика - Транзитивность отношений

Обозначения смотрятся несколько странно, но если я правильно понял вопрос, то он заключается в следующем. Даны два транзитивных бинарных отношения на множестве $%A$%. Верно ли, что их композиция тоже транзитивна?

Ответ отрицателен. Построим контрпример для случая, когда $%A=\{1;2;3\}$%. В качестве первого отношения рассмотрим отношение эквивалентности $%\sim$% на $%A$%, для которого разбиение на классы эквивалентности таково: $%\{\{1;2\};\{3\}\}$%. Проще говоря, элементы $%1$% и $%2$% полагаются эквивалентными, а элемент $%3$% им не эквивалентен (относительно $%\sim$%).

В качестве второго отношения рассмотрим также отношение эквивалентности, обозначаемое $%\approx$%, для которого разбиение на классы имеет вид $%\{\{1\};\{2;3\}\}$%. Здесь элементы $%2$% и $%3$% эквиваленты друг другу, а элемент $%1$% им не эквивалентен (относительно $%\approx$%).

Оба отношения $%\sim$% и $%\approx$%, очевидно, транзитивны. Рассмотрим теперь их композицию $%\sim\circ\approx$% и покажем, что она не транзитивна. Обозначим эту композицию буквой $%\rho$%. Утверждается, что $%3\rho2$%, $%2\rho1$%, но при этом неверно, что $%3\rho1$%. Если это проверить, что нетранзитивность $%\rho$% будет установлена.

Ясно, что $%3\sim3\approx2$%, откуда следует $%3\rho2$%. Очевидно также, что $%2\sim1\approx1$%, поэтому $%2\rho1$%. Предположим теперь, что $%3\rho1$%. По определению композиции, это означает существование такого $%x\in A$%, что $%3\sim x$% и $%x\approx1$%. Первому условию удовлетворяет только $%x=3$%, так как $%3$% эквивалентен лишь самому себе относительно $%\sim$%. Второе условие при $%x=3$% не выполнено, так как $%3$% и $%1$% находятся в разных классах эквивалентности отношения $%\approx$%.