Помогите доказать транзитивность

[@rchimed]

Помогите доказать, что если отношение транзитивно, то его симметричная и асимметричная части тоже транзитивны (т.е. $\rho\circ\rho\subseteq\rho \Rightarrow \rho^s\circ\rho^s\subseteq\rho^s$ и $\rho^a\circ\rho^a\subseteq\rho^a$, где $\rho^s=\{(x,y)\in\rho|(y,x)\in\rho\}$ и $\rho^a=\{(x,y)\in\rho|(y,x)\notin\rho\}$). Наверняка не должно быть очень сложно, но никак не соображу...

[eugensk]

Несложно, как только выпишете, что означает $\rho\circ\rho\subseteq\rho $, что означает, например, $\rho^s\circ\rho^s\subseteq\rho^s$.

Дано: $\rho\circ\rho\subseteq\rho $, т.е. для любых $x,y,z$ если $(x,y)\in \rho$ и $(y,z)\in \rho$, то (смотрим определения композиции и включения)... и так далее.

[@rchimed]

Для симметричной части доказательство действительно несложное.
Нужно показать, что для произвольных $x,y,z$ из $(x,z)\in\rho^s$ и $(z,y)\in\rho^s$ следует $(x,y)\in\rho^s$. Действительно,

$$(x,z)\in\rho^s~\&~(z,y)\in\rho^s \Rightarrow (x,z)\in\rho~\&~(z,x)\in\rho~\&~(z,y)\in\rho~\&~(y,z)\in\rho~\text{(по опр. сим. части)} \Rightarrow$$ $$\Rightarrow [(x,z)\in\rho~\&~(z,y)\in\rho]~\&~[(y,z)\in\rho~\&~(z,x)\in\rho] \Rightarrow (x,y)\in\rho~\&~(y,x)\in\rho~\text{(по транзитивности}~\rho) \Rightarrow$$ $$\Rightarrow (x,y)\in\rho^s~\text{(снова по определению симм. части)}.$$

Для асимметричной части доказательство буксует.

[eugensk]

Да точно так же, пусть $(x,z)\in\rho^a$ и $(z,y)\in\rho^a$,
выписываем всё что это даёт:

$(x,z)\in\rho$
$(z,x)\notin\rho$
$(z,y)\in\rho$
$(y,z)\notin\rho$.


Возможно ли, что $(y,x)\in\rho$ ?

[@rchimed]

Спасибо за наводку, $(y,x)\in\rho$ невозможно.
Докажем от противного, пусть $(y,x)\in\rho$. Из $(x,z)\in\rho$ и $(z,y)\in\rho$ по транзитивности $\rho$ следует $(x,y)\in\rho$, а вместе с нашим допущением это дает $(x,y)\in\rho^s$ и $(y,x)\in\rho^s$.
Идем дальше.
$(y,x)\in\rho^s~\&~(x,z)\in\rho^a \Rightarrow (y,z)\in\rho$, что противоречит $(y,z)\notin\rho$.
$(z,y)\in\rho^a~\&~(y,x)\in\rho^s \Rightarrow (z,x)\in\rho$, что противоречит $(z,x)\notin\rho$.
Итак, $(y,x)\in\rho$ невозможно.
Таким образом, $(x,y)\in\rho$ и $(y,x)\notin\rho$, откуда $(x,y)\in\rho^a$. ч.т.д.

А можно ли проще/короче?

-- 12.10.2021, 16:55 --

Заметил, что доказательство невозможности $(y,x)\in\rho$ можно сократить.
Итак, от противного, пусть $(y,x)\in\rho$. Тогда
$(y,x)\in\rho~\&~(x,z)\in\rho^a \Rightarrow (y,z)\in\rho$, что противоречит $(y,z)\notin\rho$.
$(z,y)\in\rho^a~\&~(y,x)\in\rho \Rightarrow (z,x)\in\rho$, что противоречит $(z,x)\notin\rho$.
Значит, $(y,x)\in\rho$ невозможно, т.е. $(x,y)\in\rho$ и $(y,x)\notin\rho$, откуда $(x,y)\in\rho^a$. ч.т.д.
Спасибо!

[eugensk]

Ну да, только убрать лишние ${}^a$, видно остались от copy-paste.

[@rchimed]

Точно, можно убрать. Не подумал об этом. С ними тоже все проходит, все правильно, но без них лаконичнее.

[beroal]

@rchimed, раз у вас бесточечное определение транзитивности, можно и всё остальное написать бесточечно. $\rho^s = \rho \cap \rho^{-1}$.

$$\rho^s\circ\rho^s = (\rho \cap \rho^{-1}) \circ (\rho \cap \rho^{-1}) \subseteq (\rho\circ\rho) \cap (\rho\circ\rho^{-1}) \cap (\rho^{-1}\circ\rho) \cap (\rho^{-1}\circ\rho^{-1}) \subseteq (\rho\circ\rho) \cap (\rho^{-1}\circ\rho^{-1}) \subseteq \rho\cap\rho^{-1} = \rho^s.$$

[@rchimed]

beroal, простите, некоторое время не заходил, не видел вашего ответа. Спасибо. Но вот это место мне не очень понятно:
$(\rho\circ\rho) \cap (\rho\circ\rho^{-1}) \cap (\rho^{-1}\circ\rho) \cap (\rho^{-1}\circ\rho^{-1}) \subseteq (\rho\circ\rho) \cap (\rho^{-1}\circ\rho^{-1}).$

[bot]

$A\cap B\subseteq A$