Реферат на тему:

Відношення. Властивості відношень

Підмножина R декартового степеня Mn деякої множини M називається
n-місним або n-арним відношенням на множині M. Кажуть, що елементи
a1,a2,…,an(M знаходяться у відношенні R, якщо (a1,a2,…,an)(R.

При n=1 відношення R(M називають одномісним або унарним. Таке відношення
часто називають також ознакою або характеристичною властивістю елементів
множини M. Кажуть, що елемент a( M має ознаку R, якщо a(R і R(M.
Наприклад, ознаки «непарність» і «кратність 7» виділяють із множини N
натуральних чисел унарні відношення R( = {2k-1 | k(N } і
R(( = {7k | k(N }, відповідно.

Найбільш популярними в математиці є двомісні або бінарні відношення, на
вивченні властивостей яких ми зупинимось детальніше. Далі скрізь під
словом «відношення» розумітимемо бінарне відношення. Якщо елементи a,b(M
знаходяться у відношенні R (тобто (a,b)(R), то це часто записують у
вигляді aRb. Зауважимо, що бінарні відношення іноді розглядають, як
окремий випадок відповідностей, а саме — як відповідності між однаковими
множинами.

Приклад 1.13. Наведемо приклади бінарних відношень на різних множинах.

1. Відношення на множині N натуральних чисел:

R1 — відношення «менше або дорівнює», тоді 4R19, 5R15, 1R1m для
будь-якого m(N ;

R2 — відношення «ділиться на», тоді 4R23, 49R27, mR21 для будь-якого m(N
;

R3 — відношення «є взаємно простими», тоді 15R38, 366R3121, 1001R3612;

R4 — відношення «складаються з однакових цифр», тоді 127R4721, 230R 4
302, 3231R 43213311.

2. Відношення на множині точок координатної площини R2:

), (0,0)R 5 (0,0) ;

R6 — відношення «симетричні відносно осі ординат», тоді (1,7)R6(-1,7) і
взагалі (a,b)R6(-a,b) для будь-яких a,b(R ;

R7 — відношення «менше або дорівнює». Вважаємо, що (a,b)R7(c,d), якщо a
( c і b ( d. Зокрема, (1,7)R7(20,14), (-12,4)R7(0,17).

3. Відношення на множині студентів даного вузу:

R8 — відношення «є однокурсником»,

R9 — відношення «є молодшим за віком від».

Для задання відношень можна користуватись тими ж способами, що і при
заданні множин. Наприклад, якщо множина M скінченна, то довільне
відношення R на M можна задати списком пар елементів, які знаходяться у
відношенні R.

Зручним способом задання бінарного відношення R на скінченній множині M
= {a1,a2,…,an} є задання за допомогою так званої матриці бінарного
відношення. Це квадратна матриця C порядку n, в якій елемент cij, що
стоїть на перетині i-го рядка і j-го стовпчика, визначається так

( 1, якщо aiRaj,

cij = (

( 0, в противному разі.

Приклад 1.14. Для скінченної множини M = {2,7,36,63,180} матриці
наведених вище відношень R1, R2, R3 мають такий вигляд

Рис.1.5.

Відношення можна задавати також за допомогою графіків і діаграм. Графік
відношення означається й будується так само, як і графік відповідності.
Поняття діаграми (або графа) відношення також можна означити аналогічно
до відповідності. Однак частіше діаграма (або граф) відношення R на
скінченній множині M={a1,a2,…,an} означається таким чином. Поставимо у
взаємно однозначну відповідність елементам множини M деякі точки
площини. З точки ai до точки aj проводимо напрямлену лінію (стрілку) у
вигляді відрізка або кривої тоді і тільки тоді, коли aiRaj. Зокрема,
якщо aiRai, то відповідна стрілка, що веде з ai в ai, називається
петлею.

Оскільки відношення на M є підмножинами множини M 2, то для них означeні
всі відомі теоретико-множинні операції. Наприклад, перетином відношень
«більше або дорівнює» і «менше або дорівнює» є відношення «дорівнює»,
об’єднанням відношень «менше» і «більше» є відношення «не дорівнює»,
доповненням відношення «ділиться на» є відношення «не ділиться на» тощо.

Аналогічно відповідностям для відношень можна означити поняття
оберненого відношення і композиції відношень.

Відношення R-1 називається оберненим до відношення R, якщо bR-1a тоді і
тільки тоді, коли aRb. Очевидно, що (R-1)-1=R. Наприклад, для відношення
«більше або дорівнює» оберненим є відношення «менше або дорівнює», для
відношення «ділиться на» — відношення «є дільником».

Композицією відношень R1 і R2 на множині M (позначається R1(R2 )
називається відношення R на M таке, що aRb тоді і тільки тоді, коли
існує елемент c(M, для якого виконується aR1c і cR2b. Наприклад,
композицією відношень R1 — «є сином» і R2 — «є братом» на множині
чоловіків є відношення R1(R2 — «є небожем».

Наведемо список важливих властивостей, за якими класифікують відношення.

Нехай R — деяке відношення на множині M.

а). Відношення R називається рефлексивним, якщо для всіх a(M має місце
aRa.

Очевидно, що відношення R1,R2,R4,R5,R7 — рефлексивні.

б). Відношення R називається антирефлексивним (іррефлексивним), якщо для
жодного a(M не виконується aRa.

Відношення «більше», «менше», «є сином» антирефлексивні. В той же час,
відношення R6 не є ні рефлексивним, ні антирефлексивним.

Всі елементи головної діагоналі матриці C для рефлексивного відношення
на скінченній множині M дорівнюють 1, а для антирефлексивного відношення
дорівнюють 0.

в). Відношення R називається симетричним, якщо для всіх a,b(M таких, що
aRb маємо bRa.

г). Відношення R називається антисиметричним, якщо для всіх a,b(M таких,
що aRb і bRa маємо a = b.

Наприклад, відношення R3,R4,R5,R6,R8 — симетричні, а відношення R1,R2,R7
— антисиметричні.

Неважко переконатись, що відношення R симетричне тоді і тільки тоді,
коли R=R-1.

д). Відношення R називається транзитивним, якщо зі співвідношень aRb і
bRc випливає aRc.

Наприклад, відношення R1,R2,R4,R5,R7,R8,R9 — транзитивні, а відношення
R3,R6 — не транзитивні.

Неважко переконатись, що відношення R транзитивне тоді і тільки тоді,
коли R(R(R.

Зауважимо, якщо відношення R має будь-яку з перерахованих вище
властивостей, то обернене відношення R-1 також має ту саму властивість.
Таким чином, операція обернення зберігає всі п’ять властивостей
відношень.

Для довільного відношення R означимо нову операцію. Відношення R*
називається транзитивним замиканням відношення R на M, якщо aR*b, a,b(M,
тоді і тільки тоді, коли у множині M існує послідовність елементів
a1,a2,…,an така, що a1 = a, an = b і a1Ra2, a2Ra3,…,an-1Ran.

Наприклад, нехай M — це множина точок на площині і aRb, a,b(M, якщо
точки a і b з’єднані відрізком. Тоді cR*d, c,d(M, якщо існує ламана
лінія, яка з’єднує точки c і d.

Можна довести, що відношення R транзитивне тоді і тільки тоді, коли
R*=R.

Деякі відношення займають особливе місце в математиці. Розглянемо ці
відношення окремо.

Похожие записи