Композиция бинарных отношений

[masterflomaster]

Посмотрите пожалуйста и скажите правильно ли я сделал задачу?

Пусть $\rho$ и $\sigma$ являются бинарными отношениями на множестве $A$. Верно ли, что а) если $\rho$ и $\sigma$ рефлексивны, то и $\rho\sigma$ рефлексивно; б) если $\rho$ и $\sigma$ симметричны, то и $\rho\sigma$ симметрично; в) если $\rho$ и $\sigma$ антисимметричны, то и $\rho\sigma$ антисимметрично; г) если $\rho$ и $\sigma$ транзитивны, то и $\rho\sigma$ транзитивно.

Решение. Вначале вспомним немного теории. По умолчанию, все малые латинские буквы являются элементами из $A$. Бинарным отношением на множестве $A$ является любое подмножество $R$ множества $A \times A$. Бинарные отношения могут обладать следующими свойствами: симметричность (если $aRb$, то $bRa$), антисимметричность (если $aRb$ и $bRa$, то $a=b$), рефлексивность ($aRa$), транзитивность (если $aRb$ и $bRc$, то $aRc$). Теперь запишем определение произведения бинарных отношений: произведением бинарных отношений $\alpha$ и $\beta$ на множестве $A$ называется бинарное отношение на $A$, которое обозначается через $\alpha\beta$ и определяется следующим образом: $(x,y) \varepsilon \alpha\beta$ тогда и только тогда, когда найдется элемент $z \varepsilon A$ такой, что $x \alpha z$ и $z \beta y$. Теперь приступим к самому доказательству:

а) При $\forall a$ выполняется $a\rho a$ и $a\sigma a$. По определению $a\rho\sigma a \Leftrightarrow \exists c: a\rho c$ и $c\sigma a$. При $c=a$ получаем $a\rho a$ и $a\sigma a$. Следовательно, для $\rho\sigma$ свойство рефлексивности выполняется.

б) При $\forall a, b, m, k$ если $a\rho b$ и $m\sigma k$, то $b\rho a$ и $k\sigma m$. По определению $a\rho\sigma m \Leftrightarrow \exists c: a\rho c$ и $c\sigma m$. При $c=b=k$ получаем $a\rho b$ и $k\sigma m$, которые равны $b\rho a$ и $m\sigma k$ соответственно по свойствам симметричности $\rho$ и $\sigma$. Следовательно, для $\rho\sigma$ свойство симметричности выполняется.

в) При $\forall a, b$ если $a\rho b$ и $b\rho a$, а также $a\sigma b$ и $b\sigma a$, то $a=b$.
По определению $a\rho\sigma b \Leftrightarrow \exists c: a\rho c$ и $c\sigma b$. Также $b\rho\sigma a \Leftrightarrow \exists c: b\rho c$ и $c\sigma a$. При $c=a$ одновременно получаем $a\rho a$, $b\rho a$, $a\sigma a$, $a\sigma b$. Такое возможно лишь при $a=b$. Следовательно, для $\rho\sigma$ свойство антисимметричности выполняется.

г) При $\forall a, b, c$ если $b\rho a$ и $b\rho c$, а также $a\sigma c$ и $c\sigma b$, то $b \rho c$ и $a\sigma b$. По определению $a\rho\sigma b \Leftrightarrow \exists f: a\rho f$ и $f\sigma b$. Также $b\rho\sigma c \Leftrightarrow \exists m: b\rho m$ и $m\sigma a$. При $m=a$ и $f=c$ получаем $a\rho c$, $c\sigma b$, $b\rho a$, $a\sigma c$. Значит пара $b\rho a$ и $a\rho c$ по свойству транзитивности $\rho$ приобретает вид $b\rho c$, а пара $a\sigma c$ и $c\sigma b$ по свойству транзитивности $\sigma$ меняется на $a\sigma b$. Следовательно, для $\rho\sigma$ свойство транзитивности выполняется.

[iifat]

а) доказано, хотя можно, имхо, и сократить. б) в) — нет. г) — каша какая-то, по-моему.
Зря вы столько буков вводите, имхо. Понятно, что потом пишете, кто кому равен, но следить тяжко.

[masterflomaster]

Хорошо, а можете подсказать, в каком направлении двигаться в пунктах б) в) и г). Может нужно знать какие-то свойства?

[iifat]

Да нет, вроде. б) и в), вполне возможно, не верны, попробуйте поискать контрпример. В г) стоит, имхо, попробовать сменить направление. Запишите транзитивность композиции (с минимумом букв!), распишите на элементарные отношения, поглядите, что получится. Вполне возможно, что и тоже неверно.

[masterflomaster]

Я не совсем понял, что вы имели ввиду.
В первом сообщении, Вы сказали, что б) и в) неправильны, а во втором, что они уже вполне возможно неверны (так точно неверно или наверно неверно?). А последнее предложение я вообще не понял по-поводу пункта в):"Вполне возможно, что и тоже не верно". Ну да ладно, что просили исправить, я вроде бы понял. Посмотрите пожалуйста, и скажите, что не так.

б) $a\rho\sigma b$ т.е. $\exists c: a\rho c, c\sigma b$. Т.к. $\rho$ и $\sigma$ симметричны, то $a\rho c, c\sigma b$ преобразуем в $b\sigma c, c\rho a$, следовательно имеем $b\sigma\rho a$. Поскольку по свойству $\rho\sigma \neq \sigma\rho$, то свойство симметричности у $\rho\sigma$ не выполняется.

в) из пункта б) $a\rho\sigma b$ и $b\rho\sigma a$ не могут существовать одновременно, то и условие антисимметричности не выполняется.

г) я так и не понял в чем каша? Разложил произведения композиций $a\rho\sigma b$ и $b\rho\sigma c$ на простые элементы с новыми переменными (всё как в определении). Введенные новые переменные f и m заменил на уже имеющиеся известные a и c (как в пункте а)), затем пользуясь свойством транзитивности $rho$ и $sigma$ из $b\rho a$ и $a\rho c$ получили $b\rho c$, а из $a\sigma c$ и $c\sigma b$ получили $a\sigma b$. А из полученных $a\sigma b$ и $b\rho c$ по определению произведения композиции получили $a\sigma\rho c$, что и хотели. Если этот пункт неверный, то укажите пожалуйста логическую или вычислительную ошибку.

[AV_77]

masterflomaster в сообщении #839668 писал(а):

Если этот пункт неверный, то укажите пожалуйста логическую или вычислительную ошибку.

masterflomaster в сообщении #839585 писал(а):

По определению $a\rho\sigma b \Leftrightarrow \exists f: a\rho f$ и $f\sigma b$. Также $b\rho\sigma c \Leftrightarrow \exists m: b\rho m$ и $m\sigma a$. При $m=a$ и $f=c$ получаем $a\rho c$, $c\sigma b$, $b\rho a$, $a\sigma c$.

Почему вы берете $m = a$ и $f = c$? Как у вас (правильно) написано, существует некоторое $f$, что $a \rho f$ и $f\sigma b$, но это не означает, что вместо $f$ можно подставить что угодно. Аналогично и с $m$.

[masterflomaster]

AV_77, я понял Вашу мысль, но посмотрите 10-ую страницу, определение: http://kadm.imkn.urfu.ru/files/alggeom02.pdf
Я нашел такое z, которое имеет известное нам конкретное значение 1-ом случае а, во 2-ом случае с.
При разложении транзитивности композиции на элементарные отношения, как предложил iifat, я ничего необычного не увидел.
В этой задаче в г) наверно нужно пойти другим путем, но я его не вижу)

Ах да, правильно ли я исправил пункты б) и в)?

[AV_77]

masterflomaster в сообщении #839688 писал(а):

Я нашел такое z, которое имеет известное нам конкретное значение 1-ом случае а, во 2-ом случае с.

В каком месте вы это $z$ нашли?
1) $a \rho \sigma b$, то есть существует такое $f$, что $a \rho f$ и $f\sigma $b.
2) $b \rho \sigma c$, то есть существует такое $m$, что $b \rho m$ и $m\sigma c$.
И что вы дальше делаете?

[masterflomaster]

Хорошо, попробую так.

AV_77, Вы говорите, что я не имею право сделать замену m=a, f=c (притом мы знаем, что а и с существуют из условий $a\rho\sigma b$, $b\rho\sigma c$). Почему тогда в пункте а) я сделал то же самое, хотя iifat сказал, что пункт а) решен верно.

По-поводу, что делаю дальше.
Имеем: $a\rho f, f\sigma b, b\rho m, m\sigma c$(Вы сами это написали, продублировав меня). Делаем замену m=a, f=c. Получаем $a\rho c, c\sigma b, b\rho a, a\sigma c$. То что с сигмой: $a\sigma c, c\sigma b$. Сигма по условию обладает транзитивностью, значит $a\sigma c, c\sigma b$ равносильно $a\sigma b$. Аналогично с ро из $b\rho a, a\rho c$ получаем $b\rho c$. В итоге имеем $a\sigma b$ и $b\rho c$, что является произведением, т.е: $a\sigma\rho c \Leftrightarrow \exists b: a\sigma b$ и $b\rho c$.
Мы получили $a\sigma\rho c$, которое хотели.
Если эта точка зрения воооообще неверная, то напишите что лучше сделать с пунктом г)?

А пункт б) и в) я исправил верно? (Моё 3-ье сообщение в этой теме)

[AV_77]

masterflomaster в сообщении #839705 писал(а):

AV_77, Вы говорите, что я не имею право сделать замену m=a, f=c (притом мы знаем, что а и с существуют из условий $a\rho\sigma b$, $b\rho\sigma c$). Почему тогда в пункте а) я сделал то же самое, хотя iifat сказал, что пункт а) решен верно.

Условия разные. В случае рефлексивности можно, а для транзитивности нельзя.

masterflomaster в сообщении #839705 писал(а):

Делаем замену m=a, f=c

Почему вы делаете эту замену? $m$ и $f$, вообще говоря, выбираются некоторым вполне определенным способом и взять вместо них что-то другое нельзя.

Как пример рассмотрите следующие отношения, заданные, для удобства, матрицами (единица на пересечении $i$-го столбца и $j$-й строки означает, что пара $(i, j)$ входит в отношение)

$$ \rho = \begin{array}{c|cccc} & a & b & c & d \\ \hline a & 1 & 1 & 0 & 0 \\ b & 1 & 1 & 0 & 0 \\ c & 0 & 0 & 1 & 1 \\ d & 0 & 0 & 1 & 1 \end{array}, \quad \sigma = \begin{array}{c|cccc} & a & b & c & d \\ \hline a & 1 & 0 & 0 & 0 \\ b & 0 & 1 & 1 & 0 \\ c & 0 & 1 & 1 & 0 \\ d & 0 & 0 & 0 & 1 \end{array} $$

[masterflomaster]

Я сделал такую замену $m$ и $f$ потому что получился хороший ответ) По-поводу того, что $m$ и $f$ выбираются некоторым вполне определенным способом я не знал, руководствовался лишь определением произведения отношений. Про этот определенный способ, если можете, просветите пожалуйста или просто киньте ссылку на материал)

По-поводу матрицы. Её значения Вы написали просто для примера или чем-то руководствовались? Не понял откуда взяли значения матрицы.

У меня есть еще один вариант решения пункта г). Но я в нём еще больше не уверен. Может этот ход мысли лучше? Скажите, каким лучше путем пойти?

Но для начала:
Свойство 3: пусть $\alpha$ - бинарное отношение на множестве $A$. Обратным к $\alpha$ называется бинарное отношение на множестве $A$, обозначаемое через $\alpha^{-1}$ и определяемое правилом: $x\alpha^{-1}y$ тогда и только тогда, когда $y \alpha x$. Свойство 5: если отношение $\alpha$ транзитивно, то и обратное отношение $\alpha^{-1}$ тоже транзитивно.

Предположим, что бинарное отношение $\rho\sigma$ транзитивно, т.е. существуют такие $a\rho\sigma b$ и $b\rho\sigma c$, что $a\rho\sigma c$. По свойству 5 транзитивность должна выполняться и для $(\rho\sigma)^{-1}$, т.е. еще существуют такие $a(\rho\sigma)^{-1} b$ и $b(\rho\sigma)^{-1} c$, что $a(\rho\sigma)^{-1} c$. Проверим это. Используем определение об умножении бинарных отношений и свойство 3: $a(\rho\sigma)^{-1} b \Rightarrow a\sigma^{-1}\rho^{-1} b \Rightarrow a\sigma^{-1}f, f\rho^{-1} b\Rightarrow f\sigma a, b\rho f$; $b(\rho\sigma)^{-1} c \Rightarrow b\sigma^{-1}\rho{-1} c \Rightarrow b\sigma^{-1}m, m\rho^{-1} c \Rightarrow m\sigma b, c\rho m$; $a(\rho\sigma)^{-1} c \Rightarrow a\sigma^{-1}\rho^{-1} c \Rightarrow a\sigma^{-1}n, n\rho^{-1} c \Rightarrow n\sigma a, c\rho n$. Теперь для итоговых 6 соотношений попробуем построить диаграмму:



Из диаграммы видим, что свойство транзитивности для $(\rho\sigma)^{-1}$ выполняется, следовательно $\rho\sigma$ тоже обладает свойством транзитивности.



А пункт б) и в) я исправил верно? (Моё 3-ье сообщение в этой теме)

[AV_77]

masterflomaster в сообщении #839716 писал(а):

Я сделал такую замену $m$ и $f$ потому что получился хороший ответ) По-поводу того, что $m$ и $f$ выбираются некоторым вполне определенным способом я не знал, руководствовался лишь определением произведения отношений. Про этот определенный способ, если можете, просветите пожалуйста или просто киньте ссылку на материал)

Вы же писали, что $f$ выбирается из условия $a \rho f$ и $f\sigma b$. Но существование такого $f$ не означает, что $a \rho c $ и $c \sigma b$. Вместо $f$ взять $c$ нельзя.

masterflomaster в сообщении #839716 писал(а):

У меня есть еще один вариант решения пункта г).

Не надо придумывать доказательств, разберитесь с моим примером. Там заданы два транзитивных отношений $\rho$ и $\sigma$. Проверьте, является ли $\rho\sigma$ транзитивным.

[masterflomaster]

Я не очень разобрался с матрицами. Транзитивные отношения для $\rho$ и $\sigma$ верно задал?

$$ \rho = \left \begin{array}{c|ccc} & a & b & c \\ \hline a & 0 & 1 & 1 \\ b & 1 & 0 & 1 \\ c & 1 & 1 & 0 \\ \end{array} \right $$

$$ \sigma = \left \begin{array}{c|ccc} & a & b & c \\ \hline a & 0 & 1 & 1 \\ b & 1 & 0 & 1 \\ c & 1 & 1 & 0 \\ \end{array} \right $$

[AV_77]

masterflomaster в сообщении #839751 писал(а):

Я не очень разобрался с матрицами. Транзитивные отношения для $\rho$ и $\sigma$ верно задал?

Зачем вы их написали? Я же вам привел два отношения, с ними разберитесь. Если на пересечении строки, помеченной буквой $i$, и столбца, помеченного буквой $j$, стоит 1, то пара $(i, j)$ входит в отношение. Если там стоит $0$ - то соответствующая пара не входит в отношение. Найдите для приведенных отношений их произведение и проверьте, является ли это произведение транзитивным.

[provincialka]

Не поняла, при чем тут Теория чисел?
К п. г). Я предпочитаю содержательные примеры. Пусть отношение $\rho$ означает "предок по женской линии", т.е. $a\rho b$ означает, что $a$ - мама $b$, или бабушка по материнской линии и т.д. Это отношение транзитивно. Аналогично $\sigma$ - "предок по мужской линии". Тогда $\rho\circ\sigma$ так сказать, женско-мужской предок. Например, мама отца, или дедушки по мужской линии. Или мама мамы отца. То есть берется несколько поколений мужчин-предков и несколько поколений женщин-предков старшего из них. Подумайте, будет ли $\rho\circ\sigma$ транзитивно?

-- 23.03.2014, 02:16 --

masterflomaster в сообщении #839668 писал(а):

Поскольку по свойству $\rho\sigma \neq \sigma\rho$, то свойство симметричности у $\rho\sigma$ не выполняется.

Это неравенство что, всегда выполняется? Выражайтесь аккуратней.

Вот хороший источник примеров -- композиций отношений:

Цитата:

СВЕКОР – отец мужа.
СВЕКРОВЬ – мать мужа.
ТЕСТЬ – отец жены.
ТЕЩА – мать жены.
ЗЯТЬ: 1) муж дочери; 2) муж сестры.
СНОХА – жена сына по отношению к его отцу, реже – по отношению к его матери.
НЕВЕСТКА: 1) жена брата; 2) жена сына по отношению к его матери, реже – по отношению к его отцу; 3) жена одного брата по отношению к жене другого брата.
ШУРИН – брат жены.
ДЕВЕРЬ – брат мужа.
ЗОЛОВКА – сестра мужа.
СВОЯЧЕНИЦА – сестра жены.
СВОЯК – муж сестры жены.
СВАТ – отец жены сына или мужа дочери.
СВАТЬЯ – мать жены сына или мужа дочери.

Можете подобрать отсюда контрпримеры. Например, симметричными являются отношения "сиблинг" (т.е. брат или сестра) и супруг/супруга. Возьмите их композицию!