2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Отношения на множестве.
Сообщение23.03.2014, 11:23 


15/09/13
85
Пусть на некотором множестве $\Omega$ отношение $\rho$ является отношением эквивалентности, а $\sigma$ - отношением линейного порядка. Какими из свойств: рефлексивностью, транзитивностью, симметричностью,. антисимметричностью - обладают в отношения ${\sigma}^2$, ${\rho}^2$, ${\sigma}^2$,$\rho\sigma$?

Отношение эквивалентности $\rho$ - отношение рефлексивное, симметричное и транзитивное.
Отношение линейного порядка $\sigma$ - отношение рефлексивное, антисимметричное, транзитивное и для всех $x,y$ из $\Omega$ либо $x\cdot\sigma\cdot y$, либо $y\cdot\sigma\cdot x$ .

Я нашла несколько лемм и теорем вроде:
- если $\alpha$ и $\beta$ рефлексивны, то рефлексивны и их пересечение, объединение, произведение и ${\alpha}^{-1}$.
- если $\alpha$ и $\beta$ транзитивны, то транзитивны их пересечение и ${\alpha}^{-1}$.
Но, увы, без доказательств(. А мне нужно как-то это объяснить. Наверное, либо доказать, либо привести контрпример. Я пока не понимаю, как это сделать. Подскажите, пожалуйста.

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение23.03.2014, 11:26 
Заслуженный участник
Аватара пользователя


18/12/10
1600
spb
Так а вы понимаете, что значит квадрат в этих обозначениях?

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение23.03.2014, 11:36 


15/09/13
85
Предположу, что отношения степени 2, т.е. бинарные отношения.

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение23.03.2014, 12:19 
Заслуженный участник
Аватара пользователя


18/12/10
1600
spb
А что, $\rho$ - не бинарное?

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение23.03.2014, 12:38 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
julyk в сообщении #839904 писал(а):
Предположу, что отношения степени 2, т.е. бинарные отношения.
Две части предложения никак не связаны между собой и с вопросом. Вообще-то в 5 классе говорят, что $2^2=2\cdot2$. А для отношений $\rho^2=\rho\rho$, только пропущенный знак действия - не умножение, а .. Что?

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение23.03.2014, 12:46 


15/09/13
85
Бинарное, наверное, степень 2 значит, что это произведение бинарных отношений.

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение23.03.2014, 12:48 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
Что такое "произведение отношений", что вы под этим понимаете? Посмотрите также тему «Композиция бинарных отношений»

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение23.03.2014, 13:04 


15/09/13
85
Да, верно, спасибо). Под "произведением" я понимаю композицию бинарных отношений. Т.е. пусть $R_{1}\subseteq A \times B$ , $R_{2}\subseteq B \times C$, то $R_{1}\cdot R_{2} \subseteq A \times C:$ $AR_{1}R_{2}C$ существует тогда и только тогда, когда $AR_{1}B$ и $BR_{2}C$ для B из B.

Если рассматривать $\rho^{2},$ получается, что произведение будет определено на $\Omega \times \Omega$.

P.S. Большое спасибо за тему, я изучаю).

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение23.03.2014, 13:10 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
julyk в сообщении #839935 писал(а):
$AR_{1}R_{2}C$ существует тогда и только тогда, когда $AR_{1}B$ и $BR_{2}C$ для B из B.

Хм.. $B$ из чего?
В этой фразе слово "существует" не на том месте.
julyk в сообщении #839935 писал(а):
Если рассматривать $\rho^{2},$ получается, что произведение будет определено на $\Omega \times \Omega$.

Опять "произведение"? Композиция отношений определена на том же носителе $\Omega$.

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение23.03.2014, 18:04 
Заслуженный участник
Аватара пользователя


18/12/10
1600
spb
В общем, сначала нужно обратиться к теории и посмотреть, а что же за зверь перед вами. Иначе как доказывать-то?

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение24.03.2014, 11:01 


15/09/13
85
Я и начала искать теорию, но, видимо, запуталась в определениях. Композиция бинарных отношений $\rho$ и $\sigma$ есть бинарное отношение $\rho\sigma$ такое, что $(x,y)\in\rho\sigma$ тогда и только тогда, когда существует $z\in\Omega$ такой, что $(x,z)\in\Omega$, $(z,y)\in\Omega$.

$\rho^{2}$ - бинарное отношение. Следовательно, может быть симметричным, антисимметричным, рефлексивным и транзитивным. Как теперь доказывать?

-- 24.03.2014, 11:17 --

Рассмотрим рефлексивность для $\rho^{2}$, $\sigma^{2}$, $\rho\sigma$.
Для $\rho\sigma$:
$\forall a\in\Omega$ выполняется $a\rho a$, $a\sigma a$. $a\rho\sigma$ существует титт, когда $\exists c: a\rho c$ и $c \sigma a$. При $c=a$ $a\rho a$ и $a\sigma a$. Рефлексивность выполняется. В случае $\rho^2$ и $\sigma^2$ выполняется тоже. Очевидно из определения. Вот как-то так. Надеюсь, похоже на доказательство.

-- 24.03.2014, 11:30 --

Еще мне интуитивно кажется, что $\rho^2$ сохраняет свойства $\rho$, а $\sigma^2$ сохраняет свойства $\sigma$. Но в то, что доказательства остальных свойств столь же тривиальны,мне как-то не очень верится.

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение24.03.2014, 15:52 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань

(Оффтоп)

Нехорошо подсказывать, но квадрат рефлексивного транзитивного отношения равен самому этому отношению. Например, пусть $\eta =\le\circ\le$. Имеем $a \eta b$ титт, когда для некоторого $c$ выполняется $a\le c\le b$. Ясно, что $a\le b$ и наоборот, в качестве $c$ можно взять $a$ или $b$. Но это надо доказать в общем случае.
Для композиции разных отношений это уже не верно (то есть свойства, вообще говоря, не выполняются)

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение30.03.2014, 09:50 


15/09/13
85
Рассмотрим транзитивность для $\rho \sigma$:
для доказательства нужно показать, что из $a\rho \sigma b$ и $b\rho \sigma c$ получается $a\rho\sigma c.$ По определению $a\rho \sigma b$ равносильно тому, что $\exists f:a\rho f$ и $f\sigma b$ , $b\rho \sigma c$ равносильно $\exists f:b\rho f, f\sigma c$. Используя транзитивность $\rho$, $\sigma$, из $a\rho f$, $f\sigma c$, $b\rho f$, $f\sigma b$, получаем $a\rho\sigma c$ и $b\rho \sigma b$. Кроме искомого $a\rho\sigma c$ получили еще $b\rho\sigma b$, значит свойство транзитивности для $\rho\sigma$ не выполнено.

-- 30.03.2014, 10:38 --

Симметричность для $\rho^2$:
Для доказательства нужно показать, что одновременно существуют $a\rho \rho b$ и $b\rho \rho a$. По определению $a\rho\rho b$ равносильно $\exists c: a\rho c$ и $c\rho b.$ Используя свойство симметричности, получим $b\rho c$, $c\rho a$. По определению композиции это $b\rho \ rho a$. В данном случае, т.к. рассматривается случай с одним и тем же бинарным отношением, $a\rho \rho b = b\rho \rho a.$

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение30.03.2014, 10:57 


15/09/13
85
Антисимметричность для $\sigma^2$, где $\sigma$ - антисимметричное.
Чтобы $a\sigma \sigma b$ было антисимметричным, нужно, чтобы при $a\neb$ существовало $a\sigma \sigma b$, но не существовало $b\sigma \sigma a$. Рассмотрим $a\sigma \sigma b$. Это равносильно $\exists c: a\sigma c, c\sigma b;$ Так как отношение $\sigma$ рефлексивно, получим $b\sigma c$, $c\sigma a.$ Композиция этих отношений - $b\sigma \sigma a.$ Получили, что при $a\neb$ существует и $a\sigma \sigma b$, и $b\sigma \sigma a$. Значит для $\sigma^2$ антисимметричность не выполняется.

 Профиль  
                  
 
 Re: Отношения на множестве.
Сообщение30.03.2014, 11:22 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
julyk в сообщении #842999 писал(а):
По определению $a\rho \sigma b$ равносильно тому, что $\exists f:a\rho f$ и $f\sigma b$ , $b\rho \sigma c$ равносильно $\exists f:b\rho f, f\sigma c$.

Неверно. Здесь могут быть разные $f$. Я приводила в другой теме пример, композицию отношений "предок по женской линии" и "предок по мужской". Каждое из них транзитивно, но композиция - нет.

Или возьмите в качестве примера эквивалентности. Пусть $\rho$ - "супруг или сам человек", $\sigma$ - "сиблинг (брат или сестра) или сам человек". Тогда $\rho\circ\sigma$ - "супруг сиблинга" - нетранзитивное отношение. Подумайте, почему. Кстати, оно же подойдет для проверки симметричности.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.

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



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

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


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

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