Отношения на множестве.

[julyk]

Пусть на некотором множестве $\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}$.
Но, увы, без доказательств(. А мне нужно как-то это объяснить. Наверное, либо доказать, либо привести контрпример. Я пока не понимаю, как это сделать. Подскажите, пожалуйста.

[SpBTimes]

Так а вы понимаете, что значит квадрат в этих обозначениях?

[julyk]

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

[SpBTimes]

А что, $\rho$ - не бинарное?

[provincialka]

julyk в сообщении #839904 писал(а):

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

Две части предложения никак не связаны между собой и с вопросом. Вообще-то в 5 классе говорят, что $2^2=2\cdot2$. А для отношений $\rho^2=\rho\rho$, только пропущенный знак действия - не умножение, а .. Что?

[julyk]

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

[provincialka]

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

[julyk]

Да, верно, спасибо). Под "произведением" я понимаю композицию бинарных отношений. Т.е. пусть $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. Большое спасибо за тему, я изучаю).

[provincialka]

julyk в сообщении #839935 писал(а):

$AR_{1}R_{2}C$ существует тогда и только тогда, когда $AR_{1}B$ и $BR_{2}C$ для B из B.

Хм.. $B$ из чего?
В этой фразе слово "существует" не на том месте.

julyk в сообщении #839935 писал(а):

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

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

[SpBTimes]

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

[julyk]

Я и начала искать теорию, но, видимо, запуталась в определениях. Композиция бинарных отношений $\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$. Но в то, что доказательства остальных свойств столь же тривиальны,мне как-то не очень верится.

[provincialka]

(Оффтоп)

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

[julyk]

Рассмотрим транзитивность для $\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.$

[julyk]

Антисимметричность для $\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$ антисимметричность не выполняется.

[provincialka]

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$ - "супруг сиблинга" - нетранзитивное отношение. Подумайте, почему. Кстати, оно же подойдет для проверки симметричности.