Специальные бинарные отношения

[HeartOfTheHeath]

Помогите, пожалуйста, решить.
1) Объединение `R_1 uu R_2` антисимметричных отношений `R_1` и `R_2` на А антисимметрично тогда и только тогда, когда `R_1 nn R_2^(-1) subseteq i_A`
т.е. `R_1 uu R_2` антисим. `<=> R_1 nn R_2^(-1) subseteq i_A`

решение

`R_1 nn R_2^(-1) notsubseteq i_A => EE {((x; y) in (R_1 nn R_2^(-1))),(x!=y):} => {((x; y) in R_1),((x; y) in R_2^(-1)),(x!=y):} => {((x; y) in R_1),((y; x) in R_2),(x!=y):}=> {((x; y) in (R_1 uu R_2)),((y; x) in (R_1 uu R_2)),(x!=y):} =>` противоречит `R_1 uu R_2` антисимметрично.
Но совсем нет идей, как доказывать в обратную сторону.

2)Доказать, что пересечение любой системы эквивалентностей на множестве А есть эквивалентность на А.
3)Доказать, что произведение `R_1 circ R_2` двух эквивалентностей `R_1` и `R_2` тогда и только тогда является эквивалентностью, когда `R_1 circ R_2 = R_2 circ R_1`

решение

`R_1` и` R_2` - эквивалентности `=>` они рефлексивны, симметричны, транзитивны `{((x;x) in R),((x;y) in R => (y;x) in R),((x;y) in R \ & \ (y;z) in R => (x;z) in R) :}`
`R_1` и `R_2` - рефлексивны `=> R_1 circ R_2` - рефлексивно в любом случае (доказано ранее у меня в тетради)
`R_1` и `R_2` - симметричны `=> R_1 circ R_2` - симметрично `<=> R_1 circ R_2 = R_2 circ R_1` (подзадача, которая у меня была ранее), но в доказательстве не уверена, поэтому, если можете, проверьте и его.
Док-во:
` R_1 circ R_2` - симметрично `=> R_1 circ R_2 = ( R_1 circ R_2)^(-1) = R_2^(-1) circ R_1^(-1) = R_2 circ R_1` (т.к. `R_1` и `R_2` - симметричны);
`R_1 circ R_2 = R_2 circ R_1` и `R_1` и `R_2` - симметричны
`R_2 circ R_1 = R_2^(-1) circ R_1^(-1) = (R_1 circ R_2)^(-1) => R_1 circ R_2 = (R_1 circ R_2)^(-1) => R_1 circ R_2` - симметрично.
чтд.
`R_1` и `R_2` - транзитивны `=>` ??? не знаю, как доказывать транзитивность...

@темы: Бинарные отношения, Дискретная математика

Comments

[All_ex]

LuidaFoxy, поправьте, пожалуйста набор формул... а то какая-то белиберда отображается в режиме скрипта... (где-то лишние скобки... где-то русские буквы оставили внутри формул...)

[HeartOfTheHeath]

All_ex, странно... У меня всё отображается правильно (специально перепроверила).
Вот скрин:

[HeartOfTheHeath]

All_ex, возможно... Или в браузере дело. Может мне тогда скрин под катом под самой записью вывесить (для расшифровки)?

[All_ex]

Просто запись `(x,y)` воспринимает как строку массива (матрицы)... лучше в таких записях использовать точку с запятой...
Я подправил Вам формулы... вроде теперь всё нормально...

И русские символы внутри формул не отображаются...

[HeartOfTheHeath]

All_ex, спасибо. Следующий раз буду иметь в виду.

[Дилетант]

С первой задачей как-то так:

Пусть `R_1 uu R_2` — антисимметрично.
Тогда для любых `(x,y) | x!=y` имеем:

`(x, y) in (R_1 uu R_2) => (y,x) notin (R_1 uu R_2) => (y, x) notin R_1 ^^ (y,x) notin R_2`

Отсюда сразу следует, что `AA x!=y`     `(y, x) notin R_1 nn R_2^(-1)`
То есть `R_1 nn R_2^(-1) subseteq i_A`

[Дилетант]

Во второй задаче нужно просто проверить выполнение свойств эквивалентности внутри полученного пересечения.

[HeartOfTheHeath]

Дилетант, спасибо большое!