Відношення еквівалентності

Властивості відносин

Матричний спосіб завдання відносин

Задамо відношення r:» x дружить з у» на безлічі M ², де М = { a ₁, a ₂, a ₃, a ₄}— безліч персонажів. Це відношення можна представити у виді таблиці (матриці), елементи якої дорівнюють одиниці, якщо між відповідними елементами є відношення дружби, і нулеві в противному випадку.

	a 1	a 2	a 3	a 4
a 1
a 2
a 3
a 4

З цієї таблиці видно, що a ₁ дружить з a ₃, a ₂ не дружить ні з ким, крім як із самим собою, а a ₃ дружить з усіма. Такий спосіб завдання відносин називається матричним способом. У цьому випадку відношення r Î X ´ Y представляється у виді матриці A = || a_ig || c елементами a_ig, де i -номер рядка, g — номер стовпця. a_ig = 1, якщо елементи x_i і y_g знаходяться у відношенні r, і a_ig = 0 у противному випадку.

Визначення. Відношення r на безлічі X називається рефлексивним, якщо для будь-яких x Î X виконується xrx. Якщо для всіх x Î X виконується Ø xrx, то відношення називається антирефлексивним.

Приклади. Відношення рівності рефлексивно. Відношення x ³ y, x, y Î R рефлексивно, тому що x ³ x. Відношення x > y, x, y Î R антирефлексивно, тому що не здійсненно x > x.

Визначення. Відношення r на безлічі X називається симетричним, якщо для будь-яких x Î X, y Î X, з xry випливає yrx. Іншими словами, відношення симетричне, якщо всякий раз, як виконується xry, виконується і yrx.

Приклади. З того, що» x родич y», випливає, що «y родич x», — відношення симетричне. Відношення «x – сестра y», визначене на безлічі всіх людей, несиметрично: можливо, що y є братом x. Онако те ж відношення, визначене на безлічі жінок, є симетричним.

Визначення. Відношення r на безлічі X називається антисиметричним, якщо для будь-яких x, y Î X, з того, що xry і yrx, випливає x = y.

Приклади. Відношення x £ y антисиметрично: з того, що x £ y і y £ x, випливає, що x = y, тобто це той самий елемент.

Якщо для будь-яких x, y Î Х з того, що xry, випливає, що не виконується yrx, то відношення називається асиметричним.

Відносини «x предок у» і «у нащадок x» асиметричні, причому друге є зворотним до першого. Відношення строгого порядку x < y є асиметричним: якщо виконується x < y, те не виконується y < x.

Визначення. Відношення r називається транзитивним, якщо з того, що xry і yrz, випливає xrz.

Приклад. Якщо «x предок y» і «y предок z», то «x предок z», — відношення транзитивно. Відношення x < y, де x, y Î R, транзитивно: якщо x < y і y < z, те x < z. Відношення «x любить y», у загальному випадку нетранзитивно: якщо x любить y, а y любить z, те з цього не випливає, що x любить z.

Визначення. Відношення, що має властивості рефлексивности, симетричності і транзитивності, називається відношенням еквівалентності.

Дата добавления: 2014-01-07