Малюнок № 1.20. Граф відповідності.

 

2. Типи відповідностей (порожня, повна, всюди визначена у множині відправлення, сюр’єктивна, інє’ктивна, функціональна відповідність або функція, відображення, бієктивна). Обернені функції та відображення.

2. Яке співвідношення може існувати між множинами G і Х×У? – 1) G∩Х×У=Ø; 2) GÌХ×У; 3) G=Х×У. Виходячи із цих співвідношень можна виділити наступні характерні типи відповідностей:

1) порожня відповідність, при якій G∩Х×У=Ø і α= Ø;

2) повна відповідність, при якій α=Х×У і у графі якої від кожного елемента множини Х йдуть стрілки до кожного елемента множини У;

3) відповідність всюди визначена у множині відправлення Х, тобто така, у якої GÌХ×У і для якої α^-1(У)=Х. Це означає, що всі елементи множини Х мають образи у множині У. На графі такої відповідності із кожного елемента множини Х виходить стрілка до якогось елемента множини У;

4) сюр’єктивна відповідність, тобто відповідність на всю множину прибуття У, причому α(Х)=У. При такій відповідності кожен елемент множини У має прообраз у множині Х. Для графа цієї відповідності характерно те, що із кожного елемента множини Х виходить стрілка і в кожен елемент множини У входить стрілка;

5) інє’ктивна відповідність – це така відповідність αÌХ×У, у якої прообрази елементів з множини У містять не більше одного елемента з множини Х. На графі такої відповідності в елементи множини У входить не більше однієї (одна або жодної) стрілки;

6) функціональна відповідність або функція, при якій образи елементів з множини Х або порожні, або містять лише один елемент. Граф цієї відповідності характеризується тим, що з кожного елемента множини Х виходить або одна стрілка, або не виходить жодної стрілки, але в елементи множини У може входити більше, ніж одна стрілка;

7) відображення – це всюди визначена функціональна відповідність, коли кожному елементу з множини Х відповідає єдиний елемент у множині У. Такі відповідності, тобто відображення, у свою чергу, поділяють на дві групи: а) відображення множини Х в множину У, коли у множині У є елементи, які не мають прообразів в множині Х. Граф такого відображення характеризується тим, що з всіх елементів множини Х виходять стрілки, але не в кожен елемент множини У входить хоча б одна стрілка; б) відображення множини Х на множину У, коли кожен елемент з множини У має прообраз у множині Х;

8) бієктивна або взаємно однозначна відповідність, яка одночасно всюди визначена, сюр’єктивна, інє’ктивна та функціональна, тобто це ін’єктивне та сюр’єктивне відображення.

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

Означення: відповідністю, оберненою до відповідності αÌХ×У, називається така відповідність α^-1, яка є підмножиною декартового добутку множин У×Х і складається з тих і тільки тих пар (у;х), для яких (х;у)єα.

Якщо взяти функціональну відповідність і побудувати для неї обернену, то відповідь на запитання «чи буде одержана відповідність функціональною?» не завжди позитивна.

Означення: відображенням, оберненим до даного відображення f, називається таке відображення f^-1, у якого для кожного хєХ і уєУ, якщо f(х)=у, то f^-1(у)=х, тобто f^-1(f(х))=х.

У математиці доведено теорему, яка дає відповідь на запитання «які відображення мають обернені?».

Теорема: відображення fÌХ×У має обернене відображення f^-1 тоді і тільки тоді, коли відображення f – бієктивне.

Цю теорему приймемо без доведення.

Означення: відображення f називається оборотним, якщо воно має обернене відображення f^-1.

 

Бінарні відношення між елементами однієї множини, способи їхнього задання та їх властивості: рефлексивність, антирефлексивність, симетричність, асиметричність, антисиметричність, транзитивність, антитранзитивність.

3. Хоча поняття відповідності та відношення досить близькі, але вони мають суттєві відмінності. Не зупиняючись на цих відмінностях, які не є предметом нашого розгляду, приймемо наступне означення.

Означення: якщо у відповідності f множина відправлення Х співпадає з множиною прибуття У, то таку відповідність будемо називати відношенням між елементами множини Х.

Означення: бінарним відношенням, визначеним у множині Х, називається кожна підмножина декартового квадрату Х×Х=Х².

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

Означення: відношення α, визначене у множині Х, називається рефлексивним, якщо кожний елемент множини Х перебуває у відношенні α сам з собою, тобто аαа.

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

Означення: відношення α, визначене у множині Х, називається антирефлексивним, якщо не кожен елемент множини Х перебуває у відношенні α сам з собою, тобто аαа.

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

Означення: відношення α, визначене у множині Х, називається симетричним, якщо для будь-яких а,вєХ із того, що аαв→вαа.

Символічно наведене означення можна записати так: ( а,вєХ)(аαв→вαа). Якщо відношення α симетричне, то говорять, що елементи множини Х мають властивість симетричності. Прикладами симетричних відношень є відношення дорівнює на множині фігур, перпендикулярності на множині прямих тощо.

Означення: відношення α, визначене у множині Х, називається асиметричним, якщо для будь-яких а,вєХ із того, що аαв→вαа.

Символічно наведене означення можна записати так: ( а,вєХ)(аαв→вαа). Якщо відношення α асиметричне, то говорять, що елементи множини Х мають властивість асиметричності.

Означення: відношення α, визначене у множині Х, називається антисиметричним, якщо для будь-яких а,вєХ із того, що (аαв^вαа)→(а=в).

Символічно наведене означення можна записати так:

( а,вєХ)(аαв^вαа)→(а=в). Якщо відношення α антисиметричне, то говорять, що елементи множини Х мають властивість антисиметричності.

Означення: відношення α, визначене у множині Х, називається транзитивним, якщо для будь-яких а,в,сєХ із того, що (аαв^вαс)→(аαс).

Символічно наведене означення можна записати так:

( а,в,сєХ)(аαв^вαс)→(аαс). Якщо відношення α транзитивне, то говорять, що елементи множини Х мають властивість транзитивності. Прикладами транзитивних відношень можуть бути: відношення подільності на множині чисел, відношення менше на множині кутів тощо.

Означення: відношення α, визначене у множині Х, називається антитранзитивним, якщо для будь-яких а,в,сєХ із того, що (аαв^вαс)→(аαс).

Символічно наведене означення можна записати так: ( а,в,сєХ)(аαв^вαс)→(аαс). Якщо відношення α антитранзитивне, то говорять, що елементи множини Х мають властивість антитранзитивності.

Означення: відношення α, визначене у множині Х називається зв’язним, якщо для будь-яких аαв і а≠в випливає, що аαв або вαа.

Прикладом таких відношень є відношення більше, менше на множині чисел.