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
1213
деревня Инет-Кельманда
Несложно, как только выпишете, что означает $\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
1213
деревня Инет-Кельманда
Да точно так же, пусть $(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
1213
деревня Инет-Кельманда
Ну да, только убрать лишние ${}^a$, видно остались от copy-paste.

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


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

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


17/04/11
656
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
5731
Новосибирск
$A\cap B\subseteq A$

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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