Дискретная математика: композиция эквивалентностей

[Nogin Anton]

Доброго времени суток! :)

Вот такая задача:

Нужно доказать, что композиция $R_1 \circ R_2$ эквивалентностей $R_1$ и $R_2$ тогда и только тогда являются эквивалентностью, когда $R_1 \circ R_2 = R_2 \circ R_1$.

Полагаю, что одним из вариантов доказательства является метод "от противного"... ведь у операции композиции есть свойство: $A\circ B \not = B\circ A$

[arseniiv]

Нету у неё такого свойства. Она просто не обязана быть коммутативной, но может и быть.

[Nogin Anton]

Хм.. подскажите пожалуйста с чего начать))

[cyb12]

У меня получилось решить, покрутив определение и свойства, правда как-то муторно. Наверное, можно проще.
Но вот допустим, пусть $R_2\circ R_1 = R_1 \circ R_2,$ тогда нужно проверить рефлексивность (очевидно выполняется), симметричность (тоже нетрудно видеть, если использовать это равенство), транзитивность. С транзитивностью можно аккуратно всё расписать по определению, воспользоваться тем, что $R_i$ -- отношения эквивалентности и записать нужные отношения. Также я использовал, что из $a ((R_1\circ R_2) \circ R_2) b$ следует $a (R_1\circ R_2)b.$ Напишите, что у вас получается.

[Nogin Anton]

У меня получается вот как..

Для соотношения $R_1 \circ R_2 = R_2 \circ R_1$ должно выполняться два свойства:

1) Симметричность: $x\phi y = y \phi x$
2) Транзитивность: $x\phi y$ & $y\phi z \to x\phi z$

И наверное, в таком случает, композиция эквивалентностей будет эквивалентностью.
Как-то не получается..

[beroal]

Тут удобнее доказывать без элементов (множества). Доказываем полезные свойства операций над отношениями: композиция отношений монотонна и так далее. Формулируем определение отношения эквивалентности без элементов:
рефлексивное R := $id\subseteq R$
транзитивное R := $R\circ R\subseteq R$
симметричное R := $R\subseteq R^{op}$

Вот как выглядят доказательства:
если рефлексивные $R_1, R_2$
$id = id\circ id \subseteq R_1\circ R_2$
то рефлексивное $R_1\circ R_2$

если симметричные $R_1, R_2$ и $R_1, R_2$ коммутируют
$R_1\circ R_2 = R_2\circ R_1 \subseteq R_2^{op}\circ R_1^{op} = (R_1\circ R_2)^{op}$
то симметричное $R_1\circ R_2$

и так далее. Потом можно перевести доказательства без элементов в доказательства через элементы, если было требование доказывать именно через элементы.