2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Помогите доказать транзитивность
Сообщение11.10.2021, 10:46 


17/02/20
9
Помогите доказать, что если отношение транзитивно, то его симметричная и асимметричная части тоже транзитивны (т.е. $\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\}$). Наверняка не должно быть очень сложно, но никак не соображу...

 Профиль  
                  
 
 Re: Помогите доказать транзитивность
Сообщение11.10.2021, 14:39 
Аватара пользователя


14/12/17
1370
деревня Инет-Кельманда
Несложно, как только выпишете, что означает $\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$, то (смотрим определения композиции и включения)... и так далее.

 Профиль  
                  
 
 Re: Помогите доказать транзитивность
Сообщение12.10.2021, 12:46 


17/02/20
9
Для симметричной части доказательство действительно несложное.
Нужно показать, что для произвольных $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{(снова по определению симм. части)}.$$
Для асимметричной части доказательство буксует.

 Профиль  
                  
 
 Re: Помогите доказать транзитивность
Сообщение12.10.2021, 13:31 
Аватара пользователя


14/12/17
1370
деревня Инет-Кельманда
Да точно так же, пусть $(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$ ?

 Профиль  
                  
 
 Re: Помогите доказать транзитивность
Сообщение12.10.2021, 15:42 


17/02/20
9
Спасибо за наводку, $(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$. ч.т.д.
Спасибо!

 Профиль  
                  
 
 Re: Помогите доказать транзитивность
Сообщение12.10.2021, 16:31 
Аватара пользователя


14/12/17
1370
деревня Инет-Кельманда
Ну да, только убрать лишние ${}^a$, видно остались от copy-paste.

 Профиль  
                  
 
 Re: Помогите доказать транзитивность
Сообщение12.10.2021, 19:52 


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

 Профиль  
                  
 
 Re: Помогите доказать транзитивность
Сообщение23.10.2021, 14:11 
Аватара пользователя


17/04/11
658
Ukraine
@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.$$

 Профиль  
                  
 
 Re: Помогите доказать транзитивность
Сообщение15.11.2021, 15:33 


17/02/20
9
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}).$

 Профиль  
                  
 
 Re: Помогите доказать транзитивность
Сообщение15.11.2021, 16:00 
Заслуженный участник
Аватара пользователя


21/12/05
5784
Новосибирск
$A\cap B\subseteq A$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Aritaborian


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group