2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Транзитивное отношение, найти ошибку
Сообщение04.05.2010, 17:31 


04/05/10
4
Наткнулся в книжке Д. Кука и Г. Бейза <<Компьютерная математика>> на задачу 2 в упражнении 2.3:
Следующее утверждение ошибочно. Симметричное и транзитивное отношение на $S$ является также рефлексивным, так как $aRb$ и $bRa$ влекут $aRa$. Внимательно изучив определения найти ошибку.
Изучил определение, которое приводится в книжке: Пусть $\rho$ -- отношение на множестве $A$. Тогда:
а) $\rho$ рефлексивно, если $x \rho x$ для любого $x \in A$;
б) $\rho$ симметрично, если $x \rho y$ влечет $y \rho x$;
в) $\rho$ транзитивно, если $x \rho y$ и $y \rho z$ влечет $x \rho z$.
Где же ошибка? Ведь ничто не мешает положить в пункте в) $z=x$.
В книжке Grimaldi R. "Discrete and combinatorial mathematics: an applied introduction" эта же задача в приводится в главе 7 (под номером 13, и вместо $S$ там множество $A$). В качестве ответа приводится фраза: There may exist an element $a \in A $
such that for all $b \in B $ neither $(a, b)$ nor $(b, a) \in R$. Возможно существует элемент $a \in A $ такой, что для любого $b \in B $ ни $(a, b)$ ни $(b, a)$ не принадлежат $R$.
Что за множество $B $ и где же противоречие?

 Профиль  
                  
 
 Re: Транзитивное отношение.
Сообщение04.05.2010, 18:11 


02/07/08
322
Если положить в пункте в) $z = x$, то получится утверждение: если $xRy$ и $yRx$, то $xRx$. Однако нет гарантии того, что существует хотя бы один элемент $y$, состоящий в отношении $R$ с $x$.
Примеров много: например, возьмём множество с отношением эквивалентности и добавим к нему элемент, не изменяя отношение. Тогда на новом множестве отношения эквивалентности нет, а пункты б) и в) остаются верными.

 Профиль  
                  
 
 Re: Транзитивное отношение.
Сообщение05.05.2010, 01:24 


04/05/10
4
Cave в сообщении #315558 писал(а):
. Однако нет гарантии того, что существует хотя бы один элемент $y$, состоящий в отношении $R$ с $x$.


Пусть $(x, y) \in R$. Из свойства симметричности следует $(y, x) \in R$. Так как $(x, y), (y, x) \in R$, то из свойства транзитивности следует $(x, x) \in R$. Теперь разобрался, что рефлексивность из этого не следует. Но тогда получается, что для всех $(x, y) \in R$ должно выполняться $(x, x) \in R$.

 Профиль  
                  
 
 Re: Транзитивное отношение.
Сообщение05.05.2010, 01:53 
Заслуженный участник
Аватара пользователя


06/10/08
6422
MikhailN в сообщении #315721 писал(а):
Пусть $(x, y) \in R$.
Вот именно. А если такого $y$ нет - то и заключение $(x,x)\in R$ может быть неверным.

 Профиль  
                  
 
 Re: Транзитивное отношение.
Сообщение05.05.2010, 02:51 


04/05/10
4
Вроде бы теперь разобрался. Последний вопрос на тему:
Если A = \{ 1, 2, 3, 4 \}, то будет ли транзитивным и симметричным отношение R = \{ (1{,}2), (2{,}1), (1{,}3), (3{,}1), (2{,}3), (3{,}2) \}? Из определения, приведенного выше, получается, что нет.
А R_1 = \{ (1{,}2), (2{,}1), (1{,}3), (3{,}1), (2{,}3), (3{,}2), (1{,}1), (2{,}2), (3{,}3) \} -- транзитивно и симметрично, но не рефлексивно.

 Профиль  
                  
 
 Re: Транзитивное отношение.
Сообщение05.05.2010, 09:34 


04/05/10
4
Прогнал предыдущие примеры через GHCi. Все верно: $R$ -- симметрично, но не транзитивно и не рефлексивно; $R_1$ -- транзитивно и симметрично, но не рефлексивно. Благодарю всех, кто ответил.

 Профиль  
                  
 
 Re: Транзитивное отношение.
Сообщение05.05.2010, 10:07 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Cave в сообщении #315558 писал(а):
Примеров много...

Например, пустое отношение на непустом множестве :-)

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

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



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

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


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

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