Відношення

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Поняття функції

Функція - це функціональне (тобто однозначне) відображення.

Якщо визначати функцію як відображення, тоді виходить що це є функція від одного аргументу, оскільки кожне відображення (відповідність) є відображенням однієї множини в іншу.

Коли функція від кількох аргументів:

f(x₁, x₂, ..., x_n)=y,

кожен x_i визначений в своїй області X_i

відповідно й кожне значення функції y визначено в своїй області Y

Ці області можуть бути рівними, або не рівними одне одному.

Тоді ми пропонуємо визначати функцію від багатьох змінних ($x_1 \in X_1 \dots, x_n \in X_n$) як функцію від одного аргументу, область визначення якого є прямим декартовим добутком множин:

$X_1 \times \dots \times X_n$.

Записують: $f: X_1 \times \dots \times X_n \to Y$ - визначення "типу функції".

Для функції такого типу ми вказали:

• кількість аргументів (n)
• область визначення функції
• область значень функції

Наприклад функція f(x) = log₂x визначається як $f: R^{+} \to R$

Cуперпозиція функцій - підстановка одних функцій у аргумент інших.

h(x₁, x₂, ..., x_n)=g(f₁, ..., f_n). Кількість аргументів зліва і справа має бути однаковою, наприклад така суперпозиція:

h(x₁, x₂, x₃, x₄)=g(f₁(x₃), f₂(x₁x₂, f₃(x₄))

Способи задання функцій'

• задання функції формулою (аналітичне задання)

Формула - деяка суперпозиція, що використовує обмежений набір функцій.

• задання деякою властивістю її значень
• задання таблицею (якщо задана на скінченних множинах), будь яка таблиця має бути доповненою правилами інтерполяції (вирахувати значення функції в точці, між двома заданими точками).
• задання процедурою (породжуючою). Програма.

Відношення

Відношення

Нехай задано деякий прямий добуток множин: $R \subseteq A_1 \times A_2 \times \dots A_n$

R - позначення відношення

n-місним (n-арним відношенням) називається підмножина прямого добутку n-множин.

Коли $R \subseteq A^2$ добуток на двох множинах $R \subseteq A_1 \times A_2$ (і ці множини рівні). Таке відношення називається бінарним.

Приклади бінарних відношень: "=", "≠", "<", ">", "≤", "≥"

Коли 3<5, тоді визначають (3, 5) належить відношенню R_"<", натомість пара (5, 3) не належить цьому відношенню.

Інший запис: a<b записують як aRb - "a перебуває у відношенні R_< з b"

$R \subseteq A_1 \times A_2$ - позначення як відповідності, так і бінарного відношеня. У випадку відповідності "кожному елементу з A₁ відповідає елемент з A₂"

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

Рефлексивність

Відношення називається рефлексивним, якщо відношення $R \subseteq A_1 \times A_2$ (визначене на множині A):

• Рефлексивність - кожен елемент із R перебуває у відношенні "сам з собою":

$(a, a) \in R$

прикладом такого відношення є відношення рівності (=), кожен елемент рівний самому собі.

• Нерефлексивним є відношення нерівності "≠".

Антирефлексивність

• Антирефлексивним є відношення, коли жодне a не перебуває у відношенні "сам з собою":

$(a, a) \notin R$

• Антирефлексивним є відношення "бути батьком", оскільки жоден з нас не є "батьком самому собі".

Симетричність

• Симетричним називається відношення R, якщо з того що a R b (a перебуває у відношенні з b) випливає, що b R a (і b перебуває у відношенні з a):

$a R b \to b R a$

• Симетричною є рівність на числах. Також, на множині формул, відношення рівності (еквівалентності) арифметичних формул одне одній сформульовано так: "Дві формули еквівалентні (рівносильні), якщо вони представляють одну й ту саму функцію, тобто при будь-якій підстановці значень аргументів формул (ліву та праву) ми зліва і справа отримуємо одне й те саме число".

Антисиметричність

• Антисиметричним є відношення R є антисиметричним, якщо: $a R b \land b R a \to a = b$

Тобто перестановка є можливою є тільки у випадку рівності.

• Антисиметричним є відношення "менше": <. Коли a < b, ніколи не буде правильним так, що b<a. Але, якщо взяти відношення ≤, тоді єдиним можливим випадком (a=b) одночасно: a ≤ b та b ≤.

Транзитивність

• Транзитивним є відношення R, якщо: $a R b \land b R c \to a R c$

Передача відношення відбувається і по довшим ланцюгам.

• Транзитивним є відношення "менше": <. Коли a < b, b < c, тоді a < c.

Транзитивне доповнення

Транзитивне замикання

Якщо відношення R не є транзитивним, то доповнення його до транзитивного є транзитивним замиканням.

• $\tilde{R}$ - транзитивне замикання.

$R \subseteq A \times B$ - множина пар, над якими задано теоретико-множинні операція (об'єднання, доповнення, перетин,...)

Коли ми говоримо, що транзитивне замикання - це доповнення R до транзитивного, то ми додаємо ще деякі пари, щоби відношення стало транзитивним.

• Наприклад, відношення "бути батьком": aRb - a є батьком b не є транзитивним:

якщо a є батьком b, а b є батьком с, то a не є батьком с.

Транзитивним замиканням цього відношення є "бути предком по чоловічій лінії.

якщо a є предком b, а b є предкомс, то a є предком с." Тобто додано до R всі ті пари, щоби воно стало $\tilde{R}$

• Ще приклад:

відношення "бути сусідом не є транзитивним", але його транзитивне замикання - "сидіти за одним столом".

Зворотнє відношення

• Деяке відношення R (a R b), для нього Зворотнім відношенням є відношення a R^-1 b, якщо:
• b R a

або

• $(a,b) \in R \Leftrightarrow (b,a) \in R^{-1}$

або

• $R^{-1}= \{ (a,b) | (b,a) \in R \}$
• Приклад: для відношення "бути батьком", оберненим є "бути сином". Для відношення "бути предком" є зворотнім відношення "бути нащадком".

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

Бінарне відношення називається відношенням еквівалентності, ящо воно:

• рефлексивне
• симетричне
• транзитивне

Приклад - еквівалентність формул: "2 Формули еквівалентні, якщо представляють одну й ту саму функцію".

Дійсно, взявши якусь формулу, через ланцюжки еквівалентних перетворень (розкриття дужок, приведення подібних членів,...): F₁ =_{перетворення} F₂ =_{перетворення} F_n. В цьому випадку:

• рефлексивність - формула рівна сама собі;
• симетричність - всі перетворення можна проводити в двох напрямах (вперед і назад) та в будь-якому порядку;
• транзитивність - при як завгодно довгих ланцюгах формули ми зберігаємо еквівалентність до початкового виду формули.

Клас еквівалентності

Завдяки цим трьом властивостям (рефлексивності, симетричності, транзитивності), будь-яке відношення еквівалентності розбиває множину, на якому воно задано на класи, що не перетинаються. Ці підмножини, що не перетинаються, називаються класами еквівалентності.

Якщо ми маємо множину A, на якій це відношення задано, тоді ми отримаємо розбиття множин, що не перетинаються.

Ці класи мають таку властивість:

• всі елементи одного класу між собою є еквівалентними, та всі елементи з різних класів не є еквівалентними між собою.

• симетричність - відношення всередині класу, справедливе в обидва боки:

• транзитивність - відношення всередині класу, коли ми маємо взаємозв'язок першого з другим, а другий елемент зв'язаний з третім, тоді виходить що перший зв'язаний через другий з третім елементом.

АЛЕ, якщо узяти елементи з різних класів, тоді якби хоч один елемент був би пов'язаний із елементом з сусіднього класу, він тоді по транзитивності був би пов'язаний із усіма елементами класу. І тоді ці два класи потрібно було би об'єднати в один.

Класи еквівалентності - це такі "максимальні" множини, що будь-які два елементи всередині них є еквівалентними. Тобто нічого нового до класу додати не можна.

Повертаючись до прикладу еквівалентності формул, тоді класом еквівалентності буде клас всіх таких формул, що представляють одну й ту саму функцію.

Потужність класів та елементів у них. Наприклад, нескінченна множина може бути розбитою скінченну кількість класів еквівалентності.

Приклад:

ми можемо на множині натуральних чисел задати відношення: "два числа перебувають у цьому відношенні, якщо вони мають одну й ту саму остачу при діленні на три". Тоді множина

натуральних чисел буде розбита на такі 3 класи:

• 0, 3, 6, 9, ... - клас, де остача від ділення на 3 дорівнює нулю
• 1, 4, 7, 10 ... - клас, де остача від ділення на 3 дорівнює одиниці
• 2, 5, 8, 11, ... - клас, де остача від ділення на 3 дорівнює двом

Тоді, по-перше, ці три класи не перетинаються, і кожен елемент якогось класу є еквівалентним (в розумінні залишку від ділення) до елементів цього ж класу.

Відношення порядку

Відношенням строгого порядку називається відношення, яке:

• антирефлексивне
• антисиметричне
• транзитивне

Типовий приклад - відношення "строго менше" <

Або "строге включення" на множинах $\subset$

Відношення нестрогого порядку

Відношенням нестрогого порядку називається відношення, яке:

• рефлексивне
• антисиметричне
• транзитивне

Типовий приклад - відношення "нестрого менше" ≤

Або "нестроге включення" на множинах $\subseteq$

Відношення лінійного порядку

Відношенням лінійного порядку називається відношення порядку R, якщо для будь-якої пари (a, b) елементів це відношення виконується в якийсь бік:

• або a R b
• або b R a

Тобто: будь-які два елементи порівнювані між собою

Типовий приклад - відношення "менше" < на множині натуральних чисел

Відношення часткового порядку

Відношенням часткового порядку називається відношення порядку R, але яке не є відношенням лінійного порядку:

Приклад - множина числових векторів:

• (4, 3)
• (2, 5)

Джерела

• http://www.intuit.ru/department/ds/discretemath/3/