8.8. Антисиметричні відношення

Означення 7. Відношення R називається антисиметричним, якщо aRb і bRa одночасно виконуються лише у випадку a = b.

Приклади.

1. Нехай R бінарне відношення у множині натуральних чисел визначене як x I y (x ділиться на y). Це відношення є антисиметричне, тому що

a ділиться на b і b ділиться на a імпліка a = b.

Нехай V = {1, 2, 3, 4} і R = {(1,3), (4, 2), (2, 4), (4, 4)}. Тоді R не є антисиметричним, тому що (4, 2) ( R і (2, 4) ( R . Зверніть увагу, що R також не є симетричним.

3. Відношення “включення” визначене на множині множин є антисиметричним, тому що

A ( B e B ( A implica A = B

8.9. Транзитивні відношення

Означенняo 8. Відношення R у множині A називається транзитивним, якщо (aRb ( bRc) ( aRc.

Приклади

1. Нехай A множина всіх людей, а відношення R визначена предикатом “x любить y”. Якщо a любить b і b любить c, звідси аж ніяк не слідує, що a любить c. Отже, R не є транзитивним.

2. Нехай відношення R relacao визначене у множині дійсних чисел предикатом “x < y”. R є транзитивним, тому що transitiva, porque

(a < b ( b < c) ( a < c.

3. Нехай W {a, b, c} e R = { (a, b), (c, b), (b, a), (a, c)}. R не є транзитивним, тому що

(c, b) ( R, (b, a) ( R, але (c, a) ( R.

4. . Відношення “включення” визначене на множині множин є транзитивним, тому що

(A ( B ( B ( C) ( A ( C.

Вправи на закріплення

1. R = {(1, 1), (1, 3), (2, 2), (3, 1), (4, 4)} в W = {1, 2, 3, 4}. Чи є R рефлексивним?

2. Нехай E = {1, 2, 3}. Розгляньте наступні відношення в E:

R1 = {(1, 2), (3, 2), (2, 2), (2, 3)}; R3 = {(1, 1), (2, 2), (2, 3), (3, 2), (3, 3)}; R5 = E E;

R2 = {(1, 2), (2, 3), (1, 3)}; R4 = {(1, 2)} R6 = (.

Які з цих відношень рефлексивні ? симетричні? антисиметричні? транзитивні?

3. R_i ( N N, i = 1, 2, 3, 4.

R1 = {(x, y ) : x ( y }; R3 = {(x, y ) : x + y = 10 };

R2 = {(x, y ) : x ділиться на y }; R4 = {(x, y ) : x і y взаємно прості числа };

Які з цих відношень рефлексивні ? симетричні? антисиметричні? транзитивні?

4. Довести: Нехай R₁ , R₂ симетричні відношення в A , тоді:

a) R₁ ( R₂ є симетричне відношення в A; b) R₁ ( R₂ є симетричне відношення в A.

5. Нехай R₁ , R₂ відношення в A. Довести, що наступні пропозиції хибні:

a) Якщо R₁ і R₂ антисиметричні, то R₁ ( R₂ також антисиметричне.

b) Якщо R₁ і R₂ транзитивні , тo R₁ ( R₂ також транзитивно.

6. Нехай L є множина векторів на площині. R ={(x, y):x, y ( L і “x колінеарний y “}. Чи є відношення R :

a) рефлексивне;

b) симетричне;

c) антисиметричне;

d) транзитивне.

7. Нехай L є множина векторів на площині. R ={(x, y):x, y ( L і “x ортогональний y “}. Чи є відношення R :

a) рефлексивне;

b) симетричне;

c) антисиметричне;

d) транзитивне.

8.10. Рефлексивне закриття

Означення 9. Нехай R є бінарне відношення в A. Відношення S в A називається рефлексивним закриттям R якщо S має наступні властивості:

a) R ( S;

b) S рефлексивне;

c) Для будь якого T в A, якщо R ( T і T рефлексивне, то S ( T.

Зміст властивостей a), b) зрозумілий, а що стосується властивості c), то вона забезпечує мінімальність S з усіх можливих відношень, що задовольняють a), b).

Приклад.

A = {1, 2, 3 }, R = { (1, 1), (1, 3), (2, 3), (3, 1)}, тоді рефлексивне закриття R

S = { (1, 1), (1, 3), (2, 3), (3, 1), (2, 2), (3, 3)}.

Наступна теорема гарантує існування рефлексивного закриття для будь якого бінарного відношення в A.

Teorema 1. Нехай R є бінарне відношення в A. Тоді, S = R ( I_A є рефлексивне закриття R.

Доведення. R ( R ( I_A = S;

Якщо a ( A, то (a, a) ( I_A ( R ( I_A = S ( S є рефлексивне);

Нехай T ( A A, R ( T і T є рефлексивне. Так як I_A ( T , R ( I_A = S ( T.