Бінарні відносини і їх властивості приклади розв'язання. Бінарні відносини. Приклади бінарних відносин. Бінарні відносини і їх властивості

для відносини несуворого порядку:

хX - істинно (рефлексивність);

ху і ух х \u003d у- (антисиметричність);

х у й у z xу z- (транзитивність).

безліч Xназивають упорядкованим, якщо будь-які два елементи хі уцієї множини можна порівняти, т. е. якщо для них виконується одна з умов: х< у, х= у, у< х.

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

У всіх цих множинах місце кожного елемента цілком визначено і не може довільно змінюватися.

При обробці конструкторської інформації на ЕОМ часто використовують відносини домінування. Кажуть що хXдомінує над уx,т. е. х \u003e\u003e у,якщо елемент хв чому-небудь перевершує (має пріоритет) елемент утого ж безлічі. Наприклад, під хможна розуміти один зі списків даних, який повинен надійти на обробку першим. При аналізі декількох конструкцій РЕА будь-якої з них повинен бути відданий пріоритет, так як ця конструкція володіє кращими, з нашої точки зору, властивостями, ніж інші, т. Е. Конструкція хдомінує над конструкцією у.

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

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

На практиці доводиться мати справу і з багатозначними відображеннями безлічі Xна безлічі Y,які визначають закон, згідно з яким кожному елементу хXставиться у відповідність деякий підмножина , зване чином елементів. Можливі випадки, коли Гх \u003d 0.

Нехай задано деяку підмножину Аx.для будь-якого хАчином хє підмножина . Сукупність усіх елементів Y,є образами для всіх х в А,назвемо чином безлічі Аі будемо позначати ГА.В цьому випадку

Бінарні відносини.

Нехай A і B - довільні множини. Візьмемо по одному елементу з кожного безлічі, a з A, b з B і запишемо їх так: (Спочатку елемент першої множини, потім елемент другої множини - тобто нам важливий порядок, в якому беруться елементи). Такий об'єкт будемо називати впорядкованої парою. рівними вважатимемо тільки ті пари, у яких елементи з однаковими номерами рівні. = , Якщо a \u003d c і b \u003d d. Очевидно, що якщо a ≠ b, то ≠ .

декартових твором довільних множин A і B (позначається: AB) називається множина, що складається з усіх можливих впорядкованих пар, перший елемент яких належить A, а другий належить B. За визначенням: AB \u003d ( | aA і bB). Очевидно, що якщо A ≠ B, то AB ≠ BA. Декартово твір безлічі A саме на себе n разів називається декартовой ступенем A (позначається: A n).

Приклад 5. Нехай A \u003d (x, y) і B \u003d (1, 2, 3).

AB \u003d ( , , , , , }.

BA \u003d (<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.

AA \u003d A 2 \u003d ( , , , }.

BB \u003d B 2 \u003d (<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.

бінарним відношенням на множині M називається безліч деяких упорядкованих пар елементів безлічі M. Якщо r - бінарне відношення і пара належить цьому відношенню, то пишуть: r або x r y. Очевидно, r Í M 2.

Приклад 6. Безліч (<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>) Є бінарним відношенням на множині (1, 2, 3, 4, 5).

Приклад 7. Ставлення ³ на множині цілих чисел є бінарним відношенням. Це безліч впорядкованих пар виду , Де x ³ y, x і y - цілі числа. Цьому відношенню належать, наприклад, пари<5, 3>, <2, 2>, <324, -23> і не належать пари<5, 7>, <-3, 2>.

Приклад 8. Ставлення рівності на множині A є бінарним відношенням: I A \u003d ( | x Î A). I A називається діагоналлю безлічі A.

Оскільки бінарні відносини є множинами, то до них застосовні операції об'єднання, перетину, доповнення та різниці.

областю визначення бінарного відношення r називається безліч D (r) \u003d (x | існує таке y, що xry). областю значень бінарного відношення r називається безліч R (r) \u003d (y | існує таке x, що xry).

ставленням, зворотним до бінарним відношенню r Í M 2, називається бінарне відношення r -1 \u003d ( | Î r). Очевидно, що D (r -1) \u003d R (r), R (r -1) \u003d D (r), r - 1 Í M 2.

композицією бінарних відносин r 1 і r 2, заданих на множині M, називається бінарне відношення r 2 o r 1 \u003d ( | існує y таке, що Î r 1 і Í r 2). Очевидно, що r 2 o r 1 Í M 2.

Приклад 9. Нехай бінарне відношення r задано на множині M \u003d (a, b, c, d), r \u003d ( , , , ). Тоді D (r) \u003d (a, c), R (r) \u003d (b, c, d), r 1 \u003d ( , , , ), R o r \u003d ( , , , ), R -1 o r \u003d ( , , , ), R o r -1 \u003d ( , , , , , , }.

Нехай r - бінарне відношення на множині M. Ставлення r називається рефлексивним, Якщо x r x для будь-якого x Î M. Ставлення r називається симетричним, Якщо разом з кожною парою воно містить і пару . Ставлення r називається транзитивним, Якщо з того, що x r y і y r z слід, що x r z. Ставлення r називається антисиметричних, Якщо воно не містить одночасно пари і різних елементів x ¹ y безлічі M.

Зазначимо критерії виконання цих властивостей.

Бінарне відношення r на множині M рефлексивно тоді і тільки тоді, коли I M Í r.

Бінарне відношення r симетрично тоді і тільки тоді, коли r \u003d r -1.

Бінарне відношення r на множині M антисиметрично тоді і тільки тоді, коли r Ç r -1 \u003d I M.

Бінарне відношення r транзитивно тоді і тільки тоді, коли r o r Í r.

Приклад 10. Ставлення з прикладу 6 є антисиметричних, але не є симетричним, рефлексивним і транзитивним. Ставлення з прикладу 7 є рефлексивним, антисиметричних і транзитивним, але не є симетричним. Ставлення I A володіє всіма чотирма розглянутими властивостями. Відносини r -1 o r і r o r -1 є симетричними, транзитивними, але не є антисиметричного і рефлексивними.

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

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

Приклад 11. Ставлення з прикладу 7 є відношенням часткового порядку. Ставлення I A є відношенням еквівалентності і часткового порядку. Ставлення паралельності на безлічі прямих є відношенням еквівалентності.

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

1) рефлексивність;

2) симетричність;

3) транзитивність.

4) зв'язаність.

ставлення R на безлічі Х називається рефлексивним, якщо про кожен елемент безлічі Х можна сказати, що він знаходиться в відношенні R з самим собою: хRх. Якщо відношення рефлексивно, то в кожній вершині графа є петля. І назад, граф, кожна вершина якого містить петлю, являє собою граф рефлексивного ставлення.

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

Існують відносини, що не володіють властивістю рефлексивності, наприклад, відношення перпендикулярності відрізків: ab, ba (Немає жодного відрізка, про який можна сказати, що він перпендикулярний самому собі) . Тому на графі даного відносини немає жодної петлі.

Не володіє властивістю рефлексивності і ставлення «довші» для відрізків, «більше на 2» для натуральних чисел та ін.

ставлення R на безлічі Хназивається антирефлексивне, Якщо для будь-якого елемента з безлічі Хзавжди помилково хrх: .

Існують відносини, які не є ні рефлексивними, ні антирефлексивне. Прикладом такого ставлення може бути ставлення «точка х симетрична точці увідносно прямої l», Заданий на множині точок площини. Дійсно, всі точки прямої l симетричні самі собі, а точки, що не лежать на прямій l, собі не симетричні.

ставлення Rна безлічі Х називається симетричним, якщо виконується умова: з того, що елемент х знаходиться в відношенні з елементом y, Випливає, що і елемент y знаходиться в відношенні R з елементом х:xRyyRx.

Граф симетричного відносини володіє наступною особливістю: разом з кожної стрілкою, що йде від х до y, Граф містить стрілку, що йде від y до х (Рис. 35).

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

Існують відносини, які не володіють властивістю симетричності.

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

ставлення R називають антисиметричних, Якщо для будь-яких елементів х і yз істинності xRyслід хибність yRx:: xRyyRx.

Крім відносини «довші» на безлічі відрізків існують і інші антисиметричні відносини. Наприклад, ставлення «більше» для чисел (якщо х більше у, то у не може бути більше х), Відношення «більше на» і ін.

Існують відносини, які не володіють ні властивістю симетричності, ні властивістю антисиметричність.

Відношення R на множині Хназивають транзитивним, якщо з того, що елемент х знаходиться в відношенні R з елементом y, а елемент y знаходиться в відношенні R з елементом z, Випливає, що елемент х знаходиться в відношенні R з елементом z: xRy і yRzxRz.

Граф транзитивного відносини з кожною парою стрілок, що йдуть від х до y і от y до z, Містить стрілку, що йде від хдо z.

Властивістю транзитивності володіє і ставлення «довші» на безлічі відрізків: якщо відрізок а довше відрізка b, відрізок bдовше відрізка з, То відрізок адовше відрізка с. Ставлення «рівності» на безлічі відрізків також має властивість транзитивності: (А \u003db, b \u003d с) (а \u003d с).

Існують відносини, які не володіють властивістю транзитивності. Таким ставленням є, наприклад, відношення перпендикулярності: якщо відрізок а перпендикулярний відрізку b, А відрізок b перпендикулярний відрізку з, То відрізки а і з НЕ перпендикулярні!

Існує ще одна властивість відносин, яке називається властивістю пов'язаності, а відношення, що володіє їм, називають пов'язаним.

ставлення R на безлічі Х називається пов'язаним, якщо для будь-яких елементів х і y з даної множини виконується умова: якщо х і y різні, то або х знаходиться в відношенні R з елементом y, Або елемент y знаходиться в відношенні R з елементом х. За допомогою символів це можна записати так: xy xRy або yRx.

Наприклад, властивістю пов'язаності володіє відношення «більше» для натуральних чисел: для будь-яких різних чисел х і y можна стверджувати, або x\u003e y, або y\u003e x.

На графі пов'язаного відносини будь-які дві вершини з'єднані стрілкою. Справедливо і зворотне твердження.

Існують відносини, які не володіють властивістю пов'язаності. Таким ставленням, наприклад, є ставлення подільності на множині натуральних чисел: можна назвати такі числа х і y, Що ні число хне є дільником числа y, Ні число y не є дільником числа х(числа 17 і 11 , 3 і 10 і т.д.) .

Розглянемо кілька прикладів. на безлічі Х \u003d (1, 2, 4, 8, 12) задано відношення «число хкратно числу y». Побудуємо граф даного відносини і сформулюємо його властивості.

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

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

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

У розглянутому вище відносно «рівності дробів», безліч Хрозбилося на три підмножини: ( ; ; }, {; } , (). Ці підмножини не перетинаються, а їх об'єднання збігається з безліччю Х, Тобто маємо розбиття множини на класи.

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

Так, ми встановили, що стосовно рівності на множині
Х\u003d (;;;;;) відповідає розбиття цієї множини на класи еквівалентності, кожен з яких складається з рівних між собою дробів.

Принцип розбиття множини на класи за допомогою деякого відносини еквівалентності є важливим принципом математики. Чому?

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

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

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

Іншим важливим видом відносин є відносини порядку. Розглянемо задачу.На безлічі Х={3, 4, 5, 6, 7, 8, 9, 10 ) Задано відношення «мати один і той же залишок при діленні на 3 ». Це ставлення породжує розбиття множини Х на класи: в один потраплять всі числа, при розподілі яких на 3 виходить в залишку 0 (Це числа 3, 6, 9 ). У другій - числа, при розподілі яких на 3 в залишку виходить 1 (Це числа 4, 7, 10 ). У третій потраплять всі числа, при розподілі яких на 3 в залишку виходить 2 (Це числа 5, 8 ). Дійсно, отримані множини не перетинаються і їх об'єднання збігається з безліччю Х. Отже, ставлення «мати один і той же залишок при діленні на 3 », Заданий на множині Х, Є відношенням еквівалентності.

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

ставлення Rна безлічі Х називається ставленням суворого порядку, Якщо воно одночасно має властивості антисиметричність і транзитивності. Наприклад, ставлення « х< y».

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

Прикладами відносини порядку можуть служити: ставлення «менше» на безлічі натуральних чисел, відношення «коротше» на безлічі відрізків. Якщо відношення порядку має ще й властивістю пов'язаності, то кажуть, що воно є ставленням лінійного порядку. Наприклад, ставлення «менше» на безлічі натуральних чисел.

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

Наприклад, безліч Х \u003d{2, 8, 12, 32 ) Можна впорядкувати за допомогою відносини «менше» (рис. 41), а можна це зробити за допомогою відносини «кратно» (рис. 42). Але, будучи відношенням порядку, відносини «менше» і «кратно» впорядковують безліч натуральних чисел по-різному. Ставлення «менше» дозволяє порівнювати два будь-яких числа з безлічі Х, А відношення «кратно» таким властивістю не володіє. Так, пара чисел 8 і 12 ставленням «кратно» не пов'язана: не можна сказати, що 8 кратно 12 або 12 кратно 8.

Не слід думати, що всі відносини діляться на відносини еквівалентності і відносини порядку. Існує величезна кількість відносин, які не є ні відносинами еквівалентності, ні відносинами порядку.

Основи дискретної математики.

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

Безліч - сукупність об'єктів, що володіють певним властивістю, об'єднаних в єдине ціле.

Об'єкти, що становлять безліч називаються елементами безлічі. Для того щоб деяку сукупність об'єктів можна було називати безліччю повинні виконуватися наступні умови:

· Має існувати правило, за яким моно визначити чи належить елемент до даної сукупності.

· Має існувати правило, за яким елементи можна відрізнити один від одного.

Безлічі позначаються великими буквами, а його елементи маленькими. Способи завдання множин:

· Перерахування елементів множини. - для кінцевих множин.

· Вказівка \u200b\u200bхарактеристичного властивості .

порожнім безліччю - називається безліч, що не містить жодного елемента (Ø).

Два безлічі називаються рівними, якщо вони складаються з одних і тих же елементів. , A \u003d B

безліч B називається підмножиною множини А (, Тоді і тільки тоді коли всі елементи безлічі B належать множині A.

Наприклад:, B =>

властивість:

Примітка: зазвичай розглядають підмножина одного і того е тим натовпом, що називається універсальним (U). Універсальне безліч містить всі елементи.

Операції над множинами.

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

Н-р:,,

Властивість: операції об'єднання і перетину.

· Комутативність.

· Асоціативність. ;

· Дистрибутивний. ;

Бінарні відносини і їх властивості.

нехай А і В це безлічі похідною природи, розглянемо впорядковану пару елементів (А, в) а ε А, в ε Вможна розглядати впорядковані «енки».

(А 1, а 2, а 3, ... а n), де а 1 ε А 1; а 2 ε А 2; ...; а n ε А n;

Декартових (прямим) добутком множин А 1, А 2, ..., А n, Називається мн-во, яке складається з упорядкованих n k виду.

Н-р: М= {1,2,3}

М × М \u003d М 2= {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

Підмножини декартова твори називається відношенням ступеня n або енарним ставленням. якщо n\u003d 2, то розглядають бінарні відносини. При чому говорять, що а 1, а 2 знаходяться в бінарному відношенні R, коли а 1 R а 2.

Бінарним відношенням на множині M називається підмножина прямого твори безлічі n самого на себе.

М × М \u003d М 2= {(a, b)| a, b ε M) В попередньому прикладі ставлення менше на безлічі М породжує наступне безліч: ((1,2); (1,3); (2,3))

Бінарні відносини мають різні властивості в тому числі:

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

· Антирефлексивне (іррефлексівность):.

· Симетричність:.

· Антисиметричного:.

· Транзитивність:.

· Асимметричность:.

Види відносин.

· Ставлення еквівалентності;

· Ставлення порядку.

v Рефлексивне Транзитивне відношення називається ставленням квазіпорядка.

v Рефлексивне симетричне Транзитивне відношення називається відношенням еквівалентності.

v Рефлексивне антисиметричною Транзитивне відношення називається ставленням (часткового) порядку.

v антирефлексивне антисиметричною Транзитивне відношення називається ставленням суворого порядку.

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

• 1. Бінарне відношення на множині X називається рефлексивним, якщо для будь-якого елемента aX виконується умова a:
  • (AX) a * a.

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

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

2. Бінарне відношення на X називається антирефлексивне, якщо ні для одного aX не виконується умова a * a:

Позначимо через I x відношення на множині X, що складається з пар виду (a, a), де a X:

I x \u003d ((a, a) | a X).

Ставлення Ix зазвичай називають діагоналлю безлічі X або відношенням тотожності на X.

Очевидно, що відношення на множині X рефлексивно, якщо діагональ I x є підмножиною множини:

Ставлення антирефлексивне, якщо діагональ I x і ставлення б не мають жодного спільного елемента:

• 3. Бінарне відношення на множині X називається симетричним, якщо з a * b слід b * a:
  • (A, bX) (a * b b * a).

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

відношення перпендикулярності на безлічі прямих;

ставлення торкання на безлічі кіл;

відношення "бути схожим" на безлічі людей;

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

Ставлення "x брат y" на множині всіх людей не є симетричним. У той же час відношення "x брат y" на безлічі чоловіків симетричним є.

У графі симетричного відносини для кожної дуги з вершини x в вершину y є дуга з y в x. Тому симетричні відносини можна представляти графами з неорієнтованими ребрами. При цьому кожна пара орієнтованих ребер xy і yx замінюється одним неорієнтованим ребром.

На малюнку 8 представлено відношення

б \u003d ((a, b), (b, a), (b, c), (c, b), (d, c))

за допомогою орієнтованого і неорієнтованого графів.

Рис. 8.

Матриця симетричного відносини симетрична щодо головної діагоналі.

Теорема: Об'єднання і перетин будь-якого сімейства симетричних відносин знову є симетричними відносинами.

Визначення. Бінарне відношення на множині X називається антисиметричних, якщо для будь-яких різних елементів a і b умови a * b і b * a не виконуються одночасно:

(A, bX) (a * b & b * a a \u003d b).

Наприклад, ставлення "ділиться" на безлічі натуральних чисел є антисиметричних, так як з a b і b a випливає, що a \u003d b. Однак на множині цілих чисел відношення "ділиться" антисиметричних не є, так як (-2) 2 і 2 (-2), але -22.

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

У графі антисиметричного відносини дві різні вершини можуть бути з'єднані не більше ніж однією дугою.

Визначення 3.5. Бінарне відношення a на безлічі X називається транзитивним, якщо для будь-яких трьох елементів a, b, c X з a * b і b * c слід a * c:

(A, b, c X) (a * b & b * c a * c).

Прикладами транзитивних відносин служать:

відношення "ділиться" на множині дійсних чисел;

відношення "більше" на множині дійсних чисел;

відношення "старше" на безлічі людей іграшок;

відношення "мати однаковий колір" на безлічі дитячих іграшок;

д) відношення "бути нащадком" на безлічі людей.

Феодальне ставлення "бути васалом" не є транзитивним. Це зокрема підкреслюється в деяких підручниках історії: "васал мого васала не мій васал".

Ставлення "бути схожим" на безлічі людей не має властивість транзитивності.

Для довільного відносини можна знайти мінімальне Транзитивне ставлення таке, що аb. Таким ставленням є транзитивне замикання відношення.

Приклад 3.1. Транзитивним замиканням бінарного відношення на безлічі людей "бути дитиною" є відношення "бути нащадком".

Справедлива теорема.

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

Визначення 3.6. Бінарне відношення на множині X називається зв'язковим, якщо для будь-яких двох різних елементів a і b має місце a * b, або b * a:

(A, b, c X) (ab a * b b * a).

Прикладом зв'язкового відносини є відношення "більше" на множині дійсних чисел. Ставлення "ділиться" на множині цілих чисел зв'язковим не є.

4. Инвариантность відносин

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

Теорема 4.4. Щоб твір симетричних відносин було симетрично, необхідно і достатньо, щоб відносини і комутованого.

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

Важливим видом бінарного відносини є відношення еквівалентності.

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

Ставлення еквівалентності часто позначають символами ~ ,.

Прикладами відносини еквівалентності служать:

відношення тотожності I X \u003d ((a, a) | aX) на непорожня множина X;

відношення паралельності на безлічі прямих площині;

відношення подібності на множині фігур площині;

ставлення равносильности на безлічі рівнянь;

відношення "мати однакові залишки при діленні на фіксоване натуральне число m" на множині цілих чисел. Це відношення в математиці називають ставленням порівнянності по модулю m і позначають ab (mod m);

відношення "належати одному виду" на безлічі тварин;

відношення "бути родичами" на безлічі людей;

відношення "бути однакові на зріст" на безлічі людей;

відношення "жити в одному будинку" на безлічі людей.

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

З перерахованих вище властивостей бінарних відносин слід, що перетин відносин еквівалентності є відношенням еквівалентності.

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

З відношенням еквівалентності тісно пов'язане розбиття множини на класи.

Визначення 1. Система непустих підмножин

(M 1, M 2, ...)

безлічі M називається розбиттям цього безлічі, якщо

Самі безлічі M 1, M 2, ... називаються при цьому класами даного розбиття.

Прикладами розбиття служать:

розкладання всіх багатокутників на групи по числу вершин - трикутники, чотирикутники, п'ятикутник і т. д .;

розбиття всіх трикутників за властивостями кутів (гострокутні, прямокутні, тупоугольние);

розбиття всіх трикутників за властивостями сторін (різнобічні, рівнобедрені, рівносторонні);

розбиття всіх трикутників на класи подібних трикутників;

розбиття множини всіх учнів даної школи за класами.

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

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

Про подібні фігури зазвичай говорять, що вони мають однакову форму. Але що таке форма геометричної фігури? Інтуїтивно ясно, що це щось спільне, що об'єднує подібні фігури. За допомогою відношення еквівалентності вдається це інтуїтивне поняття перевести в точне математичне. Відношення подібності, будучи ставленням еквівалентності, розбиває безліч фігур на класи подібних фігур. Кожен такий клас можна назвати формою. Тоді вираз "дві однакові фігури мають однакову форму" має наступний точний сенс "дві подібні фігури належать одній формі".

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

Наведемо елементарний приклад. Коли діти грають з безліччю різнокольорових іграшок (наприклад, з блоками Дьенеша) і вирішують задачу розкласти іграшки за кольорами, то вони користуються відношенням "мати один колір". Отримані в результаті класи одноколірних фігур сприймаються дітьми як нові поняття: червоні, жовті, сині і т. Д.

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

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

Теорема 1-яке розбиття непорожньої безлічі M на класи визначає (індукує) на цій множині відношення еквівалентності таке, що:

всякі два елементи одного класу перебувають у відношенні;

всякі два елементи різних класів не перебувають у відношенні. Доведення. Нехай є деяка розбиття непорожньої безлічі M. Визначимо бінарне відношення в такий спосіб: xay (K) (xK & yK).

Тобто два елемента x і y aіз безлічі M пов'язані ставленням в тому і тільки в тому випадку, якщо у разі необхідності розділення знайдеться такий клас K, якому одночасно належать елементи x та y.

Так певне ставлення, очевидно, рефлексивно і симетрично. Доведемо транзитивність відносини. Нехай x * y і x * z. Тоді за визначенням в існують класи K 1 і K 2 такі, що x, yK 1 і y, zK 2. Так як різні класи в розбитті не мають спільних елементів, то K 1 \u003d K 2, тобто x, z K 1. Тому x * z, що й треба було довести.

Теорема 2. Будь-яке відношення еквівалентності в непорожня множина M породжує розбиття цієї множини на класи еквівалентності таке, що всякі два елементи одного класу перебувають у відношенні;

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

Доведення. Нехай б - деяке відношення еквівалентності на безлічі M. Кожному елементу x з поставимо у відповідність підмножина [x] безлічі M, що складається з усіх елементів y, що у відношенні з елементом x:

Система підмножин [x], утворює розбиття множини M. Дійсно, по-перше, кожна підмножина [x] O, так як в силу рефлексивності відносини x [x].

По-друге, два різних підмножини [x] і [y] не мають спільних елементів. Розмірковуючи від протилежного, припустимо існування елемента z такого, що z [x] і z [y]. Тоді zax і zay. Тому для будь-якого елемента a [x] з a * x, z * x і z * y в силу симетричності і транзитивності відносини випливає a * y, тобто a [y]. Отже, [x] [y]. Аналогічно отримуємо, що [y] [x]. Отримані два включення тягнуть рівність [x] \u003d [y], що суперечить припущенню про розбіжності підмножин [x] і [y]. Таким чином, [x] y] \u003d O.

По-третє, об'єднання всіх підмножин [x] збігається з безліччю M, бо для будь-якого елемента xM виконується умова x [x].

Отже, система підмножин [x], утворює розбиття множини M. Нескладно показати, що побудоване розбиття задовольняє умовам теореми. Розбиття множини M, що володіє властивостями, зазначеними в теоремі, називається фактор-множиною множини M по відношенню і позначається M / б.