Размещено на http://www.allbest.ru/

Зміст

• 1. Відношення між елементами множини
• 2. Операції над графіками і відношеннями
• 3. Властивості відношень
• 4. Відношення еквівалетності
• 5. Відношення порядку


1. Відношення між елементами множини

В кожній математичній теорії розглядаються якісь множини об'єктів, між якими встановлено певні відношення. При аксіоматичній побудові теорії з цих об'єктів і відношень виділяється деяка частина як основні поняття і основні відношення, які в даній теорії приймаються без означення. При цьому саме поняття «відношення (співвідношення) між елементами множини» досі сприймалось нами як первинне, неозначуване поняття.

Однак виявляється, що поняттю «відношення між елементами множини» можна дати чітке означення, спираючись на основне поняття «множина» та єдине основне відношення «a є елемент множини M». Таке означення не тільки зменшує кількість понять, які ми повинні приймати як первинні, але й дає змогу глибше зрозуміти зміст самого поняття відношення, зробити це абстрактне поняття об'єктом математичного дослідження.

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

Приклади. 1. Якщо L - множина людей, то для елементів x L, y L можна розглядати відношення «x є батько y».

2. Для елементів x R, y R можна розглядати відношення «x<y (x менше y)».

3. Якщо T - множина трикутників, то для елементів x є T, y є T можна розглядати відношення « x подібний до y».

Аналізуючи наведені приклади, слід звернути увагу на таке:

а) розглядуване бінарне відношення має місце не для довільної пари елементів з даної множини, а лише для деяких пар;

б) якщо елемент x перебуває у даному відношенні до елемента y, то y, взагалі кажучи не перебуває у цьому відношенні до елемента x (таким є відношення у прикладах 1 і 2). Це означає, що відношення слід розглядати не просто для пар {x, y}, а для упорядкованих пар , <x, y> елементів множини;

в) кожне конкретне відношення між елементами даної множини цілком характеризується сукупністю упорядкованих пар елементів цієї множини, для яких це відношення має місце. Так, відношення «є батько» буде повністю задане, якщо для множини L буде складено список усіх пар<x, y> таких, що x є батько y ; саме такі списки складають в органах ЗАГС.

Щоб задати певне відношення між елементами множини M потрібно крім самої множини M вказати множину всіх упорядкованих пар таких елементів, для яких це відношення має місце, тобто вказати деякий г р а ф і к. Оскільки сукупність усіх упорядкованих пар елементів множини M утворює множину

,

то цей графік є підмножина множини .

Тепер ми підготовлені до такого означення.

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

(1)

Множина M називається множиною задання відношення , множина -- графіком цього відношення. Замість виразу «M - множина задання відношення » вживають також вирази «відношення задано на множині M «або» відношення задано між елементами множини».

Якщо <x, y> P кажуть, що x знаходиться у відношенні до y і пишуть x або . Коли задано відношення (1), то про будь-які два елементи x, y з множини M можна сказати, чи перебуває один з них у відношенні до іншого, чи ні, тобто встановити істинність чи хибність висловленняx .

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

Нехай

, .

Для рівності цих відношень необхідно і достатньо, щоб для будь-яких

мала місце рівносильність

(2)

Справді, якщо то , і тому

,

тобто виконується (2). Навпаки з (2) випливає, що для будь-якої пари

тобто, і тому

Приклади. 4. Нехай L -- множина членів сім?ї, що складається з батька (елемент a), матері (b) та трьох їхніх дітей(c, d, e). Відношення «є батьком» задане на множині

і визначається графіком

бо (a є батьком c, d та e), а для будь-яких інших упорядкованих пар елементів з відношення L не має місця.

На рисунку 1. схематично зображено точки множини площини, ортогональної проекції яких на осі координат збігаються з зображенням на осях відповідних проекцій (компонент) пар. Точки графіка P виділено при цьому особливим позначенням «*».

5. Якщо x, y-- довільні дійсні числа, то відношення задається

де R -- множина усіх дійсних чисел, а графік T складається з усіх пар, для яких. Це означає, що висловлення рівносильне висловленню .

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

У наведених прикладах, виходячи з відомих нам відношень, ми будували для них формальні означення, тобто множину задання і графік.

Розглянемо тепер приклади, в яких відношення задається формально, згідно з означенням (1).

Приклади. 6. Розглянемо відношення , де

.



На рис. 13 зображено множину і виділено її підмножину P(позначенням «*») -- графік відношення .

Цієї інформації досить для повної характеристики та вивчення властивостей відношення. Справді, про будь-які два елементи множини M, задані у певному порядку, можемо сказати, чи перебувають вони у відношенні , чи ні. Так,

і т. д., але висловлення

-- хибні (бо

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

(бо ).

Уважний читач помітить, що в розглянутому прикладі відношення можна означити і так: тоді і тільки тоді, коли

,

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

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

7. Нехай, де T складається з усіх пар з однаковими компонентами і з усіх пар з протилежними компонентами, тобто з усіх пар виду (x- довільне число).

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

Легко зрозуміти, що

,

тобто відношення між числами x і y полягає в рівності абсолютних величин цих чисел.

8. Нехай A - довільна непорожня множина, а - множина усіх пар виду, де . Очевидно, . Відношення

між елементами множини A є ніщо інше як відношення рівносильності елементів множини. Адже

, але, за означенням

.

Отже

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

Графік відношення називають діагоналлю множини ; геометрично від зображується діагоналлю «квадрата» , яка лежить на бісектрисі I--III координатних кутів (якщо вважати, що елементи множин A зображені відповідними точками координатних осей).

В тому випадку, коли P є невласна підмножина (див.п. 4.1), відношення також називають невласним. Якщо , відповідне невласне відношення називають п о в н и м; якщо ж, відношення називають п о р о ж н і м. Якщо - повне відношення на множині M, то для будь-яких істинне висловлення ; якщо - порожнє відношення, то для будь-яких двох елементів , висловлення хибне .

Розглядаючи наведені приклади 4 - 7, можна помітити, що не в усіх випадках в означенні відношення, заданого на множині M, справді фігурують усі елементи множини M. Так у прикладі 4 елемент b («мати» y «сім?ї» L) не був компонентою (першою чи другою) жодної з пар, що належали графіку P. Розглядаючи замість L множину , ми по суті не змінили б нічого в означенні даного відношення. Надалі вважатимемо як правило, що таких «зайвих» для розглядуваного відношення елементів в множині M немає. Щоб сформулювати цю думку точніше, введемо поняття п о л я II в і д н о ш е н н я , розуміючи під цим множину

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

Аналогічно до бінарного відношення можна означити тернарне відношення.



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

2. Операції над графіками і відношеннями

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

Зауважимо перш за все, що над графіками, як і над будь-якими множинами, можна виконувати операції об?єднання, перетину, віднімання, утворення симетричної різниці тощо.

Розглянемо ще дві операції, специфічні для графіків у тому розумінні, що при їх означенні і здійсненні істотно виконується те, що елементами графіка є саме упорядковані пари.

Перша з цих операцій унарна і називається інверсією.

Означення 1. Інверсією називається операція, яка довільному графіку ставить у відповідність графік , який визначається за таким правилом:

ь

Графік, що є результатом інверсії графіка, називається також інверсією графіка , і позначається .

Отже, щоб утворити графік , слід у кожній упорядкованій парі з графіка поміняти місцями компоненти; сукупність упорядкованих пар, що утвориться, і є .

З означення випливає, що



тобто область означення , а область значень , а область значень графіка дорівнює області означення графіка .

Далі зрозуміло, що

,

тобто повторне застосування операції інверсії графіка приводить знову до графіка .

Приклади. 1. У прикладі 2, п. 5.1 ми розглядали графіки (рис. 9) і (рис. 10). На рис. 16 зображено графіки та відповідно.

Які слід було чекати,

2. У прикладі 5 (п. 5.2), ми розглядали графік

,

де -- усі можливі упорядковані пари дійсних чисел такі, що . Очевидно, це сукупність усіх пар , для яких , тобто сукупність усіх точок площини, які лежать нижче бісектриси I - III координатних кутів (рис. 7).

3. Для графіка (діагональ множини -- див. приклад 8) маємо

,

тобто інверсія не змінює цього графіка.

Геометричне зображення інверсії графіка легко утворити за допомогою перетворення симетрії координатної площини відносно бісектриси I - III координатних кутів. Справді , при цьому перетворенні вісь абсцис і вісь ординат міняються місцями, і довільна точка площини переходить у точку .

Друга із згаданих операцій над графіками бінарна і має назву композиції (або множення) графіків.

Означення 2. Композицією графіків називається операція, яка довільним двом графікам та , заданим у певному порядку, ставить у відповідність графік Г, який визначається за таким правилом: тоді і тільки тоді, коли існує таке , при якому справджується

Такий графік називають композицією графіка і графіка і позначають .

Приклади. 4. Нехай

Побудуємо графік . Перш за все зрозуміло, що пара може належати лише тоді, коли, тобто, в даному прикладі. Але згадана умова лише необхідна для того, щоб і дає нам тільки, так би мовити, «кандидатів» у пари графіка . Кожна така «пара-кандидат» потребує перевірки за означенням композиції.

Так, пара справді належить , бо існує такий елемент , що . Пара, бо існує такий елемент , що. А бо не існує такого , що . Міркуючи аналогічно, знаходимо:

У випадку графіка TP необхідна умова того, щоб

.

Перевірка показує, що

5. Нехай та -- графіки, причому

. Тоді .

Справді, не існує жодного такого, що

та (бо таке ), а тому й жодної пари .

6. Нехай є сукупність усіх пар дійсних чисел, для яких (див. приклад 5, п. 5.2). покажемо, що .

Справді, якщо

.

Але тоді знайдеться дійсне число , таке, що

(наприклад, ).

Це означає, що

і, отже .

Навпаки, якщо

, то існує таке , що

, або , звідки , що рівносильно .

При умові, що однакові елементи зображуються на різних координатних осях однаковими точками (тобто такими, що лежать від початку координат на однаковій відстані і по той самий бік), можна іноді дістати геометричне зображення графіка з геометричних зображень графіків за допомогою простої послідовності дій. Проілюструємо це для випадку графіків з прикладу 4. на рис. 18 точки графіка P позначено , точки графіка T. Для довільної точки графіка (наприклад, точки ) виконуємо такі дії: а) проводимо до перетину з бісектрисою I - III координатних кутів у точці ; очевидно,

;

б)проводимо пряму через точку паралельно і визначаємо на ній всі точки, які належать графіку , якщо вони існують (в даному разі -- це точки ); в) проводимо через точку пряму , паралельну, проектуємо ортогонально на неї точки, знайдені в операції б) (в даному разі -- точки M і N ); точки, які ми дістанемо(), належать графіку (позначаємо їх «»). Перевіримо це, наприклад, для точки . Якщо

.

Оскільки, ,то .



У нашому випадку точка не дає нових точок графіка , а точка дає третю точку .

Як видно з прикладу 4, операція композиції графіків у загальному випадку некомутативна. Можна, однак, показати, що вона має властивість асоціативності.

Означення 3. Оберненим до відношення називають відношення

.

З означення 3 випливає, що для довільних .

Означення 4. Доповненням відношення називають відношення

.

З означення 4 випливає, що

для довільних . Адже

.

Операції утворення оберненого відношення до відношення і доповнення відношення є унарні операції, які називають відповідно інверсією та доповненням відношення .



Приклад 7. Нехай

є відношення «менше» для дійсних чисел (приклад 5, п. 5.2), тобто є сукупність усіх пар дійсних чисел, для яких . Тоді складається з усіх пар , для яких

, або (див. приклад 2), - з усіх пар , для яких, або .

Геометричним зображенням обох графіків є частина площини, заштрихована на рис.7, з тією різницею, що точки бісектриси I--III координатних кутів належать , але не належать .

Відношення можна назвати «більше», бо

, а відношення - «не менше» ,

бо .

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

Означення 5. Нехай дано відношення

та .



Відношення

(11)

; (12)

; (13)

; (14)

називають відповідно об?єднанням, різницею, перетином і композицією відношень та ; такі ж назви мають операції, результатом яких є ці відношення (наприклад, операцію утворення відношення називають композицією відношення і відношення ).

Зміст складних відношень (11) -- (13) стає зрозумілим з таких рівносильностей, які мають місце для довільних .

(15)

(16)

(17)

Перевіримо, наприклад, (16):

Відношення означає, що . Це в свою чергу означає, що існує таке , при якому

(тобто ) і (тобто ).

Отже, для довільних :

. (18)

Приклади. 8. Подібно до прикладу 4. п. 5.2, розглянемо «сім?ю» з дещо зміненим складом: батько, його брат, його дочка, його сини. Крім відношення «бути батьком» з графіком

,

розглянемо відношення «бути братом», графік якого очевидно, є

.

Відношення означає «бути батьком або бути братом» і має своїм графіком множину . Відношення означає «бути батьком і бути братом»; воно порожнє

,

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

(бути батьком означає -- бути батьком і не бути братом).

Найбільш цікаво розглянути композицію . Її зміст зрозумілий з того, що тоді і тільки тоді, коли існує в сім?ї такий , що ( брат ) і ( батько ); іншими словами відношення означає «бути дядьком».

Побудуємо графік цього відношення. На рис. 19 точки графіка T позначено, точки графіка P, точки графіка .

9. Нехай відношення «менше» на множині -- обернене до нього відношення «більше» (див. Приклад 7)

.

Оскільки це виконується для довільних дійсних чисел .

Рекомендуємо читачеві дістати ті самі результати, виконуючи дії над графіками .

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

бінарний відношення множина графік

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

Означення 1. Відношення називається рефлексивним, якщо для будь-якого має місце .

Оскільки

,

а сукупність усіх пар виду є діагональ множини (див. приклад 8, п. 5.2), то необхідною і достатньою умовою рефлексивності відношення є така властивість його графіка :

(1)

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

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

(2)

Висловлення (2), як і будь-яка імплікація, носить умовний характер. Воно не означає, що кожна пара елементів з перебуває у цьому відношенні, але якщо , то обов?язково .

Оскільки у (2) -- довільні елементи з , то, міняючи їх місцями, дістанемо

, (3)

а з (2) і (3) та означення оберненого відношення (п. 5.3) випливає, що

,

тобто Отже, іншим означенням симетричності відношення є те, що воно збігається з оберненим відношенням .

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

Означення 3. Відношення називається транзитивним, якщо для будь-яких справедливе твердження

(4)

Але за означенням композиції відношень для будь-яких

В силу (4) це означає істинність висловлення

Отже графік транзитивного відношення має властивість

(5)

Навпаки, якщо графік відношення має властивість (5), то це відношення транзитивне. Справді, для будь-яких

(за означенням композиції) і (за умовою (5));

звідси , тобто транзитивне.

Приклади. 1. Відношення рівності елементів

(приклад 8, п. 5.2)

є рефлексивним, симетричним і транзитивним .



2. Відношення «менше» для дійсних чисел

(приклад 5 п. 5.2) не є рефлексивним , не є симетричним , але воно транзитивне, .

3. Нехай

(звичайно ) і .

Відношення не рефлексивне, але транзитивне, бо .

При відсутності властивості рефлексивності чи симетричності іноді доцільно означити деякі вужчі властивості відношення .

Означення 4. Відношення називається антирефлексивним, якщо для будь-якого має місце .

Оскільки

,

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

Зауважимо, що антирефлексивне відношення не є рефлексивним, але не рефлексивне відношення не завжди є антирефлексивним. Так, відношення на множині

з графіком



не є рефлексивним, бо

.

Але воно не є антирефлексивним, бо

.

Означення 5. Відношення називається антисиметричним, якщо справджується умова

(6)

Умова (6) рівносильна умові

.

Зауважимо, що ця умова виконується, зокрема коли

.

Як і у випадку рефлексивності, антисиметричне відношення не є симетричним, але існують не симетричні відношення, які не мають властивості антисиметричності. Так, щойно наведене відношення

з множиною задання

і графіком

не є симетричним і не є антисиметричним .

Нарешті, розглянемо ще одну властивість відношення , яка полягає в тому, що для будь-яких нерівних між собою одне з відношень має місце обов?язково.

Означення 6. Відношення називається досконалим, якщо для будь-яких при умові справедливе твердження

(7)

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

aбо

aбо

Рівносильність усіх наведених форм означення очевидна.

Приклади 4. Відношення «менше» для дійсних чисел

антирефлексивне, антисиметричне, транзитивне і досконале, бо



.

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

6. Відношення «бути братом» (приклад 8, п. 5.3) антирефлексивне, не симетричне і не антисиметричне, транзитивне (в «сім?ї» ) і не досконале.

У наступних пунктах розглянемо два важливих класи відношень -- так звані відношення еквівалетності і відношення порядку.

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

Введемо таке означення:

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

Приклади. 1. Відношення рівності

(приклад 1, п. 6.1) є еквівалентність.

2. Відношення рівності множин (п. 4.1) є еквівалентність.

3. Відношення подібності у множині всіх трикутників є еквівалентність.

4. Відношення , наведене у прикладі 6, п. 5.2

є відношенням еквівалентності. Узагальнюючи цей приклад, можна твердити, що відношення , задане на множині всіх цілих чисел рівносильністю



,

де -- фіксоване ціле число, відмінне від нуля, є еквівалентність. Числа , які знаходяться у відношенні , називають конгурентними за модулем .

5. Рівносильність висловлень відношення еквівалентності на множині всіх висловлень.

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

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

Дамо спочатку таке означення.

Означення 2. Розбиттям непорожньої множин називається сукупність непорожніх підмножин множини таких, що:

1. Для будь-яких

2. Об?єднання усіх множин дорівнює множині



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

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

8. Сукупність усіх різних одиничних підмножин даної множини є розбиттям множини M.

Підмножини , з яких утворено розбиття множини , називають к л асами розбиття. З властивості 2 випливає, що кожний елемент входить хоч один клас розбиття , а з властивості 1 -- що тільки в один клас розбиття.

Теорема 1. Якщо -- відношення еквівалентності на множині , то можна утворити розбиття множини на класи так, щоб для будь-яких , які належать до одного класу, справджувалось, а для будь-яких, які належать до різних класів, справджувалось .

Доведення. Позначимо через множину всіх елементів таких, що . Очевидно, що

, бо (рефлексивність еквівалентності).

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

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

Нехай такий спільний елемент: тобто та за означенням множин . Далі,

за симетричністю еквівалентності. Отже, використовуючи транзитивність еквівалентності, дістаємо або .

Якщо тепер -- довільний елемент з , то ; оскільки , то за транзитивністю дістанемо , тобто і тому . Аналогічно, якщо , маємо і в силу дістаємо , звідки . В результаті дістаємо , що й треба було довести. Далі легко зрозуміти, що

(8)

Справді

,

тобто .

Але кожне -- підмножина , тому й

.

Цим (8) доведено.

Нехай тепер є сукупність усіх попарно різних множин . Покажемо, що розбиття множини . З доведеного вище випливає, що. Залишається показати, що .з (8) зрозуміло, що об'єднання множин для всіх дорівнює. Оскільки множину ми утворили з усіх попарно різних , то в не ввійшли такі , які збігаються з деякими . Тому відкидання таких не приводить до втрати жодного елемента з об'єднання:



Отже -- розбиття множини . Переконаємось, що це розбиття задовольняє умови теореми.

Нехай -- довільні елементи з . Якщо вони належать тому самому класу то , звідки (ураховуючи симетричність і транзитивність відношення ).

Якщо ж і класи різні (отже,), то. Справді, припустивши супротивне, дістаємо з, та, що; але це означає, що і тому, що суперечить доведеному раніше

.

Цим теорему доведено.

Розбиття множини , яке має властивості, зазначені в теоремі 1, називаємо розбиттям, спряженим з відношенням .

Покажемо, що для будь-якого відношення рівносильності на множині існує єдине спряжене розбиття множини .

Теорема 2. Якщо -- відношення рівносильності на множині та -- спряжені з розбиття множини , то.

Доведення. Нехай -- довільний клас і . Оскільки -- розбиття , то знайдеться клас такий, що. Якщо довільний елемент з , то , звідки випливає за властивістю спряженого розбиття, що тобто . Цілком аналогічно показують , що, і тому . Отже, кожний клас є одним з класів розбиття , тобто . В силу повної рівноправності розбиттів та маємо також , тобто , що й треба було довести.

Отже, за даним відношенням еквівалентності на множині можна єдиним способом побудувати спряжене з ним розбиття цієї множини; позначатимемо це розбиття . Виявляється, що й навпаки, за будь-яким розбиттям множини можна побудувати таке відношення еквівалентності на множині , щоб дане розбиття було спряженим з цим відношенням. Точніше, має місце така теорема.

Теорема 3. Якщо -- будь-яке розбиття множини , то існує таке відношення еквівалентності на множині , що.

Доведення. Означимо відношення на множині за допомогою такої умови. Для довільних

Таке означення коректне, бо кожний елемент належить одному і тільки одному класу розбиття . Якби міг належати двом різним класам і входило лише в одним з них, то означення (9) не мало б смислу.

Покажемо, що відношення -- еквівалентність.

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



і, але тоді й ; отже, -- симетричне відношення. Нарешті, нехай та -- довільні елементи з , і відомо, що та . Це означає, що існує клас розбиття такий, що

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

Отже, має властивості рефлексивності, симетричності і транзитивності, тобто є відношенням еквівалентності.

Залишається показати, що , тобто що для будь-яких

,

які належать одному і тому ж класу розбиття , а для будь-яких

з різних класів . Але це безпосередньо випливає з означення(9) відношення . Теорему доведено.

Відношення , існування якого доведено у теоремі 3, природно назвати спряженим з розбиттям і позначити . З теореми випливає що .

Легко зрозуміти, що визначається розбиттям однозначно. Якби це було не так, то існували б різні відношення еквівалентності та на множині такі, що

.



Але це неможливо, бо коли, то існує пара елементів

така, що , але .

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

Підіб?ємо підсумки попереднього викладу. Як бачимо, задання еквівалентності на множині рівносильне заданню деякого розбиття цієї множини. Інакше кажучи, встановити відношення еквівалентності між елементами якоїсь множини -- це означає розбити цю множину на класи елементів, які вважаються еквівалентними між собою.

Ця обставина визначає специфічну будову графіка відношення еквівалентності, а саме: якщо є відношення еквівалентності, а -- розбиття множини M спряжене з , то

(10)

Справді,

.

Але та належать класу розбиття тоді і тільки тоді, коли

.

Тому

.



Ця рівносильність і означає правильність рівності (10).

Отже, графік будь-якого відношення еквівалентності має побудову (10). Навпаки, якщо -- якесь розбиття множини , то

(11)

є графіком спряженого відношення еквівалентності; це зрозуміло з того, що (11) рівносильне (9).

приклади. 9. Для відношення рівності елементів (див. Приклад 1) спряженим розбиттям множини є розбиття на одиничні множини. Якщо

, то , а графік...

10. Для відношення подібності трикутників на множині всіх трикутників кожний клас спряженого розбиття складається з усіх подібних між собою трикутників, або, що те саме, з усіх трикутників з попарно рівними внутрішніми кутами.

11. Для відношення конгурентності цілих чисел за модулем (див. Приклад 4) класами спряженого розбиття є множини -- сукупність усіх цілих чисел , які при діленні на дають остачу.

12. Для відношення рівносильності висловлень спряжене розбиття множини усіх висловлень складається з двох класів -- клас істинних висловлень і клас хибних висловлень.

Приклади 9 -- 12 ілюстрували ті випадки , коли для заданого відношення будується спряжене розбиття. В наступних прикладах за даним розбиттям будується спряжене відношення еквівалентності.

Приклади. 13. Для розбиття колективу факультету на академічні групи (приклад 7) спряженим відношенням еквівалентності є таке: студенти факультету та еквівалентні тоді і тільки тоді, коли вчаться в тій самій академічній групі.

14. Розглянемо таке розбиття множини всіх невід?ємних дійсних чисел

.

Спряжене відношення визначається тим, що тоді і тільки тоді, коли числа і мають однакові цілі частини. Для цього відношення графік

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

Перейдемо тепер до означення відношення порядку.

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

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

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

Приклади. 1. Відношення «менше» на множині всіх дійсних чисел:

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

2. Відношення «не більше» на множині всіх дійсних чисел:.

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

3. На множині всіх людей розглянемо відношення

.

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

4. На множині натуральних чисел введемо відношення

,

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

5. Нехай -- деяка сукупність множин. Для довільних

приймемо.

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

6. З двох прямокутників назвемо «більшим» той, який має більшу площу. Цим введемо на множині всіх прямокутників відношення, що має властивості транзитивності, антисиметричності та антирефлексивності.

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

Щоб зберегти поняття порядку для всіх цих відношень, введемо такі два означення:

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

Означення 2. Відношення називається відношенням нестрогого порядку (нестрогим порядком), якщо вон рефлексивне, антисиметричне і транзитивне.

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

хибне для усіх

.

Але це так, бо, припустивши істинність цього висловлення, дістанемо за транзитивністю відношення , що , а це суперечить умові антирефлексивності.

Найбільш важливим прикладом строгого порядку є відношення «менше» або «більше» на множині усіх дійсних чисел.

Аналогічну роль серед відношень нестрогого порядку відіграє відношення «не більше» або «не менше» на множині усіх дійсних чисел.

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

З наведених вище прикладів відношеннями строгого порядку є також приклади 3,6, нестрогого порядку -- приклади 4,5.

Між цими прикладами є ще одна істотна відмінність, а саме: деякі з них -- досконалі, а деякі -- ні. Нагадаємо, що досконалість відношення на множині полягає в тому, що для будь-яких елементів

істинне висловлення

,

тобто довільні різні елементи пов?язані відношенням або . Інакше це висловлюють так: будь-які два елементи множини порівняні. Саме така ситуація має місце у прикладах 1,2. але решта наведених відношень цієї властивості не мають. Так, у прикладі 3 відношення «бути нащадком» має місце не для будь-яких пар людей, а лише для деяких. Так само, якщо та -- будь-які множини, то зовсім не обов?язково, щоб справджувалось відношення або . Два різні прямокутники (приклад 6) можуть мати однакову площу і тому не будуть порівняні за введеним відношенням порядку.

У зв'язку із сказаним введемо таке означення.

Означення 3. відношення строгого (нестрогого) порядку називається лінійним строгим (нестрогим) порядком, якщо воно досконале.

Прикладами лінійного порядку (крім уже згаданих відношень чи між дійсними числами) можуть бути такі.

Приклади. 7. розглянемо напрямлену пряму . Якщо -- дві різні точки цієї прямої і напрямок відрізка збігається з напрямком прямої , будемо говорити, що точка «передує» точці (або точка «іде за» точкою ) і записувати . Відношення на множині точок прямої є досконалим відношенням строгого порядку. Саме в зв'язку з цим досконалий порядок називають лінійним.

8. порядок слів у словнику є лінійним строгим порядком, який називають лексикографічним. Цей порядок можна означити (стосовно до українського словника) так. Якщо -- різні слова, то при попарному порівнянні букв, з яких вони складені (перша з першою, друга з другою і т.д, рахуючи зліва), обов?язково виявиться пара різних букв. При цьому вважатимемо, що обидва порівняні слова мають однакову кількість букв, тобто доповнюватимемо коротше слово справа «порожніми» буквами (позначеними, наприклад, ). Нехай -- така пара різних букв з найменшим номером (тобто всі пари відповідних букв, які стоять перед , якщо такі є, були однаковими буквами), причому . Слово передує слову (слово іде за словом ), якщо буква передує букві в українському алфавіті (при умові, що «порожня» буква передує усім іншим буквам алфавіту).

Так, слово «батько» передує слову «бути» (бо буква «а» в алфавіті передує букві «у»), слово «земля» ( або «земля») передує слову «земляний» (бо буква «» передує букві «н»).

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

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

На практиці множину називають просто упорядкованою, якщо відомо, якщо відомо, яке відношення порядку розглядається. Проте важливо розуміти, що упорядкованість не є властивістю самої множини, бо ту сому множину можна по-різному упорядкувати за допомогою різних відношень порядку.

Зрозумілі такі вирази: строго (нестрого) упорядкована множина; лінійно упорядкована множина тощо.

Кожний з наведених вище прикладів відношення порядку є водночас прикладом деякої упорядкованої множини. Так, множина лінійно упорядкована в розумінні як строгого порядку , так і нестрогого .

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

, або .

Нехай і -- два елементи строго упорядкованої множини . Якщо елемент наступний відносно елемента і передує елементу , тобто

,

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

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

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

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

Теорема 4. якщо відношення -- порядок (строгий чи нестрогий) на множині, то і відношення -- порядок (строгий чи не строгий) на множині.

Доведення. Перш за все зрозуміло, що рефлексивність (чи антирефлексивність) рівносильна рефлексивності (чи антирефлексивності) , бо для довільного маємо

.

Далі, антисиметричність рівносильна антисиметричності , бо для довільних .

Те саме має місце і для транзитивності; адже для будь-яких



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

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

закінчуючи розгляд відношень порядку, для яких основною спільною рисою є властивість транзитивності, зауважимо, що в математиці розглядаються і нетранзитивні відношення, які також абстраговані від деяких реальних співвідношень між об?єктами. Одним з класів таких відношень є так звані відношення толерантності, які характеризуються властивостями рефлексивності і симетричності. Ці відношення виражають певну схожість об?єктів, яка, на відміну від еквівалентності, не зберігається при композиції відношення самий з собою. Прикладом може бути таке відношення «схожості» між словами: два слова, що мають однакову кількість букв, вважаємо схожими, якщо вони можуть бути утворені одне з одного заміною не більше, як однієї букви. Рефлексивність і симетричність такого відношення очевидні ґ, але транзитивність місця не має; наприклад, слова «кара» і «каре» схожі, слова «каре» і «кафе» схожі, але слово «кафе» (яке ми дістали двічі заміняючи по одній букві у слові «кара») не схоже з словом «кара».

Усі розглянуті вище типи відношень можна звести в таку таблицю.



Клас відношень	Властивості
	Рефл.	Антирефл.	Симет.	Антисиметр	Транзит.	Досконалість.
Еквівалентність Строгий порядок Строгий лінійний порядок Нестрогий порядок Нестрогий лінійний порядок Толерантність	+ + + +	+ +	+ +	+ + + +	+ + + + +	+ +

Размещено на Allbest.ru