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

[julyk]

Проверим $\rho \sigma$ на симметричность. Должно выполняться $a\rho \sigma b$ и $b\rho \sigma a$ одновременно.
1) $a\rho \sigma b$ равносильно $\exists c : a\rho c$ и $c\sigma b$. Так как $\rho$ и $\sigma$ рефлексивны, то $b\sigma c$ и $c\rho a.$ Запишем композицию: $b\sigma \rho a$. Но операция композиции некоммутативна, т.е $b\sigma \rho a \ne b\rho \sigma a$. Следовательно, $\rho\sigma$ несимметрично.

Проверим антисимметричность. Для доказательства при $a\ne b$ и $a\rho\sigma b$ не должно быть $b\rho\sigma a$. $a\rho\sigma b$ равносильно $\exists c : a\rho c$ и $c\sigma b$. Так как $\rho$ и $\sigma$ рефлексивны, то $b\sigma c$ и $c\rho a.$ Запишем композицию: $b\sigma\rho a$. Получили, что при $a\ne b$ и $a\rho\sigma b$ есть $b\sigma\rho a$. $b\rho\sigma a$ нет, значит $\rho\sigma$ антисимметрично.

-- 30.03.2014, 11:44 --

provincialka, я представляю себе отдельно отношение "брат".
$x\rho y$ и $y\rho z$, то $x\rho z$. (если $x$ брат $y$, и $y$ брат $z$, то $x$ брат $z$). Оно транзитивно. Не могу понять то же самое с "супругами". Получается, если $x$ супруг $y$, и $y$ супруг $z$, то $x$ супруг $z$. Что-то странное, на мой взгляд...Не могу это представить. И композицию тем более .

[provincialka]

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

Но операция композиции некоммутативна, т.е . $b\sigma \rho a \ne b\rho \sigma a$. Следовательно, $\rho\sigma$ несимметрично.

Как вы понимаете "некоммутативность"? Что, никогда не может быть $b\sigma \rho a = b\rho \sigma a$? Более того, для этих отношений не может существовать общих пар?
Высказывание "композиция некоммутативна" означает только, что для некоторых отношений $b\sigma \rho a \ne b\rho \sigma a$, в том смысле, что существуют пары, находящиеся в отношении $\sigma \rho$, но не находящиеся в отношении $\rho \sigma$, или наоборот. Но вдруг те пары, которые вы исследуете, как раз входят и туда, и туда?

Чтобы доказать отсутствие какого-то свойства обычно достаточно контрпримера. Я вам их и привела.

-- 30.03.2014, 12:52 --

Отношение "брат" нетранзитивно даже на множестве мужчин. Пусть А брат Б, тогда и Б брат А. Но тогда по транзитивности и А брат А. Но это неверно. Поэтому такие отношения дополняют рефлексивностью, чтобы они стали эквивалентностями.
Я так и написала: "сиблинг или сам человек", "супруг или сам человек".
Всякая эквивалентность связана с разбиением. В моем примере представлены два разбиения на "семьи": семьи, состоящие из супругов, и семьи, состоящие из братьев и сестер. Конечно, могут существовать и одиночки в том и другом смысле.

-- 30.03.2014, 12:57 --

Можете использовать другие два разбиения. Например, $\rho$ - предметы одного цвета, $\sigma$ - предметы одной формы. Что будет их композицией? В качестве носителя отношения возьмите, например, (красный круг, красный квадрат, красный треугольник, синий круг, зеленый круг)

[julyk]

Мне кажется, я поняла с супругами и братьями.
$x\rho y$ - $x-$ супруг $y$ или сам человек;
$x\sigma y$ - $x-$ брат $y$ или сам человек;
Рассмотрим композицию, по определению должно быть, если $\rho\sigma = x\rho\sigma y$ и $ y\rho\sigma z$, то $x\rho\sigma z.$ Переведем это на человеческий язык: $x-$ супруг брата $y$, $y-$ супруг брата $z$, то $x$ супруг брата $z$. На примере своих родственников я убедилась, что это не так. Т.е. отношение нетранзитивно.

А для примера с предметами необходимо добавить "или сам предмет" в каждое из отношений, верно? А то получается, как с братом.

[provincialka]

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

А для примера с предметами необходимо добавить "или сам предмет" в каждое из отношений, верно? А то получается, как с братом.

Ну, это вопрос терминологии. Считаете ли вы, что предмет одного цвета с самим собой? В данном случае определение эквивалентности идет через разбиение по свойству, так что добавка рефлексивности, по-моему, не требуется.

[julyk]

Для симметричности $\rho\sigma$ должно выполниться $x\rho\sigma y$ и $y\rho \sigma x$. Смотрим те же отношения супружества и братства. Получаем, что $x-$супруг брата $y$ и $y-$ супруг брата $x$. Выходит, несимметрично.
Антисимметричность $\rho\sigma$. Должно не выполнится при $x\ne y$ и $x\rho\sigma y$ следующее: $y\rho\sigma x$. Получаем, что $x-$супруг брата $y$ и $y-$ супруг брата $x$. Второе неверно, следовательно $\rho\sigma$ антисимметрично.
А как можно доказать в общем виде,что квадрат рефлексивного транзитивного отношения равен самому этому отношению? Чтобы уже закончить с транзитивностью для $\rho^2$, $\sigma^2$. И как работать с другими свойствами квадратов?

-- 30.03.2014, 15:15 --

Стоп, кажется, антисимметричность с этими примерами нельзя смотреть, сейчас подумаю.

[provincialka]

Про антисимметричность непонятно: вы что доказываете, есть она у композиции или нет.

[julyk]

Мне нужно рассмотреть антисимметричность композиции симметричного отношения $\rho$ и антисимметричного отношения $\sigma$. И отношение "супруги", и отношение "братья" симметричны. А мне нужно, чтобы одно было симметрично, а другое антисимметрично. И дальше уже пытаться доказать наличие или отсутствие. Вот пытаюсь подобрать такие отношения...

-- 30.03.2014, 15:39 --

Вот, нашла. Антисимметричное будет отношение "длиннее". А симметричное - "параллельно". Смотрим, должно быть при $x\ne y$ и $x\rho\sigma y$ не должно быть $y\rho\sigma.$ $x\rho\sigma y - $ $x$ длиннее параллельного $y$, $y\rho\sigma x - $ $y$ длиннее параллельного $x$ при $x\ne y$ не верно, значит ассимметрично.

-- 30.03.2014, 15:52 --

Подскажите, а я могу брать для доказательств свойств $\rho^2$ и $\sigma^2$ отношения одинаковых с ними свойств, но разные по значению? Например "супруг" и "брат" для симметричности?

[provincialka]

Что неверно? Будем применять ваши отношения к отрезкам. Композиция означает, что отрезок $a$ длиннее некоторого отрезка, параллельного отрезку $b$. Ясно, что это верно для любых двух отрезков, то есть композиция в данном случае симметрична.

-- 30.03.2014, 16:59 --

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

Подскажите, а я могу брать для доказательств свойств $\rho^2$ и $\sigma^2$ отношения одинаковых с ними свойств, но разные по значению? Например "супруг" и "брат" для симметричности?

Нет, доказывать лучше в общем виде. Вот опровергать - примером.

[julyk]

Про отрезки поняла, спасибо. А как можно начать доказывать, что квадрат рефлексивного транзитивного отношения равен самому этому отношению? И есть ли что-то подобное для симметричности и антисимметричности?

[provincialka]

Вот по определению и доказывайте. Что означает, что $a~\rho^2~b$?
Запишите это и доказывайте, что $a~\rho~b$. И наоборот.

[julyk]

Сейчас наткнулась на такой факт:
Антисимметричность отношения не исключает симметричности. Существуют бинарные отношения:
-одновременно симметричные и антисимметричные (отношение равенства);
-ни симметричные, ни антисимметричные;
-симметричные, но не антисимметричные;
-антисимметричные, но не симметричные ("меньше или равно", "больше или равно");
Т.е, если мне сказано, что$\rho-$ рефлексивно,симметрично,транзитивно, то я ничего не знаю о его антисимметричности??? Аналогично про симметричность $\sigma$. Т.е. мы ничего не можем сказать об этих свойствах. Поправьте, если я ошибаюсь.

Для квадратов сейчас посмотрю.

[provincialka]

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

Т.е, если мне сказано, что$\rho-$ рефлексивно,симметрично,транзитивно, то я ничего не знаю о его антисимметричности???

Формально - да, не знаете. Хотя отношение, одновременно симметричное и антисимметричное - очень "бедное" отношение, это только равенство, или отношения, входящие в него (т.е. когда некоторые элементы находятся в отношении с собой, но, возможно, не все).