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

1. Доказать, что если отношения r₁ и r₂ рефлексивны, то рефлексивны и отношения:

r₁ È r₂, r₁ Ç r₂, r₁^-1, r₁ · r₂.

2. Доказать, что если r₁ и r₂ иррефлексивны, то иррефлексивны и отношения

r₁ È r₂, r₁ Ç r₂, r₁^-1. Показать, что композиция r₁ · r₂ иррефлексивных отношений может не быть иррефлексивной.

3. Доказать, что если r₁ и r₂ симметричны, то симметричны и отношения

r₁ È r₂, r₁ Ç r₂, r₁^-1, r₁ · r₁^-1.

4. Доказать, что композиция r₁ · r₂ симметричных отношений симметрична тогда и только тогда, когда r₁ · r₂ = r₂ · r₁.

5. Доказать, что

5.1. если отношения r₁ и r₂ антисимметричны, то антисимметричны также r₁ Ç r₂ и r₁^-1;

5.2. объединение r₁ È r₂ антисимметричных отношений антисимметрично тогда и только тогда, когда r₁ Ç r₂^-1 Í i_A.

6. Построить бинарное отношение

6.1. рефлексивное, симметричное, не транзитивное;

6.2. рефлексивное, антисимметричное, не транзитивное;

6.3. рефлексивное, транзитивное, не симметричное;

6.4. антисимметричное, транзитивное, не рефлексивное;

6.5. симметричное, транзитивное, не рефлексивное.

7. Доказать, что если r есть транзитивное и симметричное отношение на А

и dom r È rng r=А, то r есть эквивалентность на А.

8. Доказать, что любое отношение на А, симметричное и антисимметричное одновременно, является транзитивным.

9. Доказать, что отношение r на множестве А является одновременно

эквивалентностью и частичным порядком в том и только в том случае, когда r=i_A.

10. Пусть rÍА². Доказать, что r есть эквивалентность Û (r · r^-1) È i_A = r

ª r - эквивалентность Þ r^-1 = r, r · r= r, i_A Í r. Следовательно, (r · r^-1) È i_A Í r. Обратно,

r · r^-1 симметрично для любого r. Поэтому r также симметрично и r · r= r · r^-1 Í r. Следовательно, r симметрично, транзитивно и рефлексивно, т.е. r - эквивалентность. §

11. Доказать, что объединение r₁ È r₂ эквивалентностей r₁ и r₂ является эквивалентностью тогда и только тогда, когда r₁ È r₂ = r₁ · r₂.

ª Пусть r₁ È r₂ - эквивалентность. Тогда r₁ · r₂ Í( r₁ È r₂) ·(r₁ È r₂) Í r₁ È r₂, r₁ È r₂=

(r₁ ·i_A) È (i_A · r₂) Í r₁ · r₂. Обратно, пусть r₁ È r₂ = r₁ · r₂ . Тогда r₂ · r₁= r₂^-1 · r₁^-1. Тогда

r₂ · r₁ = r₂^-1 · r₁^-1 = (r₁ · r₂)^-1 = =(r₁ È r₂)^-1= r₁ È r_2. (r₁ Èr₂) · (r₁ È r₂)=

(r₁ · r₁) È(r₂ ·r₁) È(r₁ · r₂) È (r₂ · r₂) Í r₁ È r₂, т.е. r₁ Èr₂ транзитивно. Симметричность и рефлексивность r₁ È r₂ очевидны. §

12. Доказать, что композиция двух эквивалентностей r₁ · r₂ является эквивалентностью тогда и только тогда, когда r₁ · r₂=r₂ ·r₁.