8.1. Бінарне відношення з a в b

Означення 1. Бінарним відношенням з A в B називається підмножина R ( A B упорядкованих пар ( x, y): x називають першою координатою, y – другою координатою; термін “упорядкована” треба розуміти як (x, y) ( (y, x).

Множину перших координат x бінарного відношення називають областю визначення (Dom R ( A ), множина других координат y областю значень або образом (Im R ( B).

Приклади.

Нехай A = { 1, 2, 3 }, B = { 2, 3, 4 }. Тоді,

A B = { (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4) }

Підмножина R₁ = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)} визначає бінарне відношення.

Dom R₁ = { 1, 2, 3 }, Im R₁ = { 2, 3, 4 }.

Означення 2. Якщо Dom R = А , Im R = В, то бінарне відношення називають відношенням А на В.

Якраз таке відношення ми маємо в попередньому прикладі. Якщо помітити ще одну визначну властивість пар в цьому ж прикладі “ x менше y ”, R₁ можна представити як

R₁ = {(x,y): ((x,y) (A B ) ( (x < y)}

Підмножина R₂ = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 4)} визначає друге бінарне відношення, але цього разу

Dom R₂ = { 1, 2}, Im R₂ = { 2, 3, 4 }.

Означення 2. Якщо Im R = В, то бінарне відношення називають відношенням з А на В.

Визначна властивість пар цього відношення є “y ділиться на x ” або “x є множником y” . Позначимо це “y I x “. Тоді можемо представити R₂ як

R₂ = {(x,y): ((x,y) (A B ) ( (y | x)}

Підмножина R₃ = {(1,2), (2,4)} визначає відношення “ x є половина y ” з

Dom R₃ = { 1, 2 }, Im R₃ = { 2, 4 }

і може бути представлено як

R₃ = {(x,y): ((x,y) (A B ) ( (y = 2x)}.

Нехай U множина всіх слів української мови і Е множина перекладів цих слів на англійську мову. В цьому випадку зручніше представити бінарне відношення з U в E як

xRy, (x, y) ( U E,

тому що для перерахування всіх його пар знадобилась би ціла книга, якою і є українсько-англійський словник. Сама літера R означає, що y є англійським еквівалентом українського x. В комп’ютерній логіці це відношення написали б як

dict(X_S , Y_S),

де X_S , Y_S є списки елементів, відповідно Dom R і Im R. Але

dict(x, y)

є не що інше, як бінарний предикат. Значить, існує відповідність між бінарними відношеннями і бінарними предикатами – це просто різні підходи, різні бачення одного й того ж об’єкту. (dict від англійського dictionary – словник).

Відношення

R = {(x,y): ((x,y) (A B ) ( P(x, y)}

разом з бінарним предикатом P(x, y) задає множину існування цього предикату A B. Очевидно, що пара (a, b) ( R тоді і тільки тоді коли P(a, b) є істинним. Другими словами, (a, b) ( R тоді і тільки тоді коли (a, b) належить до множини істинності предикату P(x, y). В цих термінах будь яке рівняння з двома невідомими, наприклад

2x + 3y – 5 = 0

можемо трактувати і як бінарний предикат, і як бінарне відношення на множині дійсних чисел. Підставляючи пару (3, 4) одержимо хибну пропозицію 2 3 + 3 4 – 5 = 0. З другого боку,

(1, 1) ( {(x,y): (x,y) (R R ( 2x + 3y – 5 = 0 }

Рівняння з одним невідомим, наприклад

x² – 3x + 2 = 0

також можна трактувати як унарний предикат. З цим рівнянням пов’язана множина істинності предикату {1, 2} – його корені, але ця пара вже не є елементом бінарного відношення.

Нехай A = {Large, Middle, Small} множина предикатів розміру і B = {a, b, c, d, e, f} множина імен вживаних в Bolanda. Множина

{Large(a), Middle(b), Small(c), Large(d), Small(a)}

є одним з можливих бінарних відношень в A B. Зверніть увагу, кожний елемент цього бінарного відношення є пропозиція.