18278

ВІДНОШЕННЯ НА МНОЖИНІ

Лекция

Математика и математический анализ

Лекція 5 ВІДНОШЕННЯ НА МНОЖИНІ Відношення на множині та його основні характеристики. Особливості графа відношення на множині. Способи задання відношень на множині. Основні властивості відношень на множині: рефлективність і антирефлексивність симетричність ...

Украинкский

2013-07-07

121.5 KB

33 чел.

Лекція 5

ВІДНОШЕННЯ НА МНОЖИНІ

  1.  Відношення на множині та його основні характеристики. Особливості графа відношення на множині. Способи задання відношень на множині.
  2.  Основні властивості відношень на множині: рефлективність і антирефлексивність, симетричність і антисиметричність, транзитивність і зв’язність.
  3.  Відношення еквівалентності з розбиттям множини на класи.
  4.  Відношення порядку та його види.

  1.  Відношення на множині та його основні характеристики. Особливості графа відношення на множині.

Способи задання відношень на множині.

Якщо відношення ρ визначене між елементами двох рівних множин A і B, тобто коли A = B, або, що те саме, області відправлення і прибуття відношення ρ збігаються, то говорять про відношення між елементами множини A, яке також називають відношенням на множині A. Для нього зберігаються ті ж характеристики, що й для відношення між елементами двох множин.

Означення відношення між елементами множини можна дати незалежно від поняття про відношення між елементами двох множин. Довільна підмножина декартового квадрату множини називається відношенням між елементами цієї множини або відношенням на цій множині. Якщо ρ відношення на множині A, то це записується ρ Ì A2.

Граф відношення на множині має особливості:

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

2) дуги графа можуть починатися і закінчуватися в одній і тій же вершині, такі дуги називаються петлями і на них напрям можна не вказувати;

3) якщо дві різні вершини графа з'єднуються двома дугами, напрями яких протилежні, то для спрощення дві дуги замінюють однією і називають її подвійною;

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

  1.  Основні властивості відношень на множині: рефлективність і антирефлексивність, симетричність і антисиметричність, транзитивність і зв’язність.

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

Говорять, що відношення ρ між елементами множини A має:

1) рефлексивну властивість, якщо кожний елемент множини A перебуває у відношенні ρ сам із собою;

2) антирефлексивну властивість якщо жоден елемент множини A не перебуває у відношенні ρ сам із собою;

3) симетричну властивість, якщо для будь-яких елементів x і y множини A з того, що x перебуває у відношенні ρ з y випливає, що y перебуває у відношенні ρ з x;

4) антисиметричну властивість, якщо для будь-яких елементів x і y множини A з того, що x перебуває у відношенні ρ з y і y перебуває у відношенні ρ з x випливає, що x = y;

5) транзитивну властивість, якщо для будь-яких елементів x, y і z множини A з того, що x перебуває у відношенні ρ з y і y перебуває у відношенні ρ з z випливає, що x перебуває у відношенні ρ з z;

6) властивість зв'язності, якщо для довільних елементів x і y множини A має місце принаймні одне з трьох відношень: x перебуває у відношенні ρ з y, y перебуває у відношенні ρ з x, або x дорівнює y.

Антисиметричну властивість відношення можна сформулювати і так: відношення ρ має антисиметричну властивість, якщо для будь-яких різних елементів x і y множини A з того, що x перебуває у відношенні ρ з y випливає, що y не перебуває у відношенні ρ з x. Відношення, які мають рефлексивну, антирефлексивну, симетричну, антисиметричну, транзитивну властивості та властивість зв'язності відповідно називають рефлексивним, антирефлексивним, симетричним, антисиметричним, транзитивним і зв'язним.

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

1) рефлексивного відношення у кожній  вершині є петля;

2) антирефлексивного відношення відсутні петлі;

3) симетричного відношення всі дуги подвійні;

4) антисиметричного відношення не має подвійних дуг, за винятком петель;

5) транзитивного відношення, якщо три вершини з'єднані дугами, то аналогічно додаванню векторів;

6) зв'язного відношення між двома різними вершинами проведена принаймні одна дуга.

Задача 2. Побудувати  граф і точковий графік відношень ρ, ρ-1 і  між елементами множини A = {2, 3, 4, 5, 6}, якщо x ρ y тоді і тільки тоді, коли x ділиться на y, тобто xy. Встановити властивості цих відношень.

► 1. Для розв'язування задачі знайдемо декартів квадрат множини A, який зручно записати у вигляді таблиці:

(2, 2), (2, 3), (2, 4), (2, 5), (2, 6),

(3, 2), (3, 3), (3, 4), (3, 5), (3, 6)

(4, 2), (4, 3), (4, 4), (4, 5), (4, 6)

(5, 2), (5, 3), (5, 4), (5, 5), (5, 6)

(6, 2), (6, 3), (6, 4), (6, 5), (6, 6).

2. Знаходимо графік відношення ρ. Щоб не записувати його, підкреслимо у декартовому квадраті множини A ті пари, які складають графік відношення.

Будуємо граф (мал. 3) і точковий графік (мал. 4) відношення ρ.

Мал. 3.

Мал. 4.

Відношення ρ:

1) рефлексивне, бо у кожній вершині його графа є петля;

2) антисиметричне, бо подвійних дуг, крім петель, його граф не має;

3) транзитивне, бо для довільних елементів x, y і z множини A, якщо xy і yz, то й xz.

3. Знаходимо тепер графік відношення ρ-1:

ρ-1 = {(2, 2), (3, 3), (2, 4), (4, 4), (5, 5), (2, 6), (3, 6), (6, 6)}.

Будуємо граф і точковий графік відношення ρ-1, мал. 5 і 6 відповідно. Точкові графіки відношень ρ і ρ-1 симетричні відносно бісектриси першого і третього координатних кутів, а їх графи відрізняються лише напрямком дуг. Отже, відношення ρ-1 має ті ж властивості, що й відношення ρ, а саме: воно рефлексивне, антисиметричне і транзитивне.

Мал. 5.

Мал. 6.

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

Будуємо граф (мал. 7) і точковий графік (мал. 8) відношення .

Відношення :

1) антирефлексивне, бо на його графі відсутні петлі;

2) зв'язне, бо на його графі довільні дві різні вершини з'єднані принаймні однією дугою.  ◄

Мал. 7.

Мал. 8.

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

Теорема 1. Якщо відношення на множині має деякі із перерахованих властивостей 1) – 6), то й обернене йому відношення має ті ж самі властивості.

► Нехай відношення ρ між елементами множини A транзитивне.

Доведемо, що й обернене йому відношення ρ-1 транзитивне.

Дійсно, якщо x, y і z – будь-які елементи множини A такі, що

x ρ-1 y  і  y ρ-1 z Þ за означенням оберненого відношення

z ρ y  i  y ρ x Þ за транзитивністю відношення ρ

z ρ x Þ за означенням оберненого відношення

x ρ-1 z.

Отже, маємо, що для будь-яких елементів x, y і z множини A, якщо x ρ1 y  і  y ρ-1 z, то x ρ-1 z, а тому відношення ρ-1 транзитивне.

Аналогічно доводяться інші властивості.  

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

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

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

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

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

Якщо ρ – відношення еквівалентності на множині A і a – довільний елемент множини A, то повний образ елемента a при відношенні ρ називається класом елементів еквівалентних елементу a або просто класом еквівалентності і позначається Ka:

Ka := {x Î A |a ρ x}.

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

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

Теорема 3. Якщо ρ – відношення еквівалентності на множині A, то для довільних двох класів еквівалентності має місце одне і тільки одне із відношень: або ці класи не перетинаються, або вони збігаються.

► Нехай ρ – відношення еквівалентності на множині A і Ka та Kb – довільні класи еквівалентності. Ці класи є непорожніми підмножинами множини A, а тому для них можливе одне і тільки одне із відношень: або вони не перетинаються, тобто Ka Ç Kb = Æ, або перетинаються, тобто Ka Ç Kb ≠ Æ. Щоб довести теорему, достатньо довести, що у другому випадку Ka = Kb.

Припустимо, що класи Ka і Kb перетинаються, тобто існує принаймні один елемент x такий, що

x Î Ka  і  x Î Kb Þ за означенням класів еквівалентності та симетричної властивості відношення

a ρ x  і  x ρ b Þ за транзитивністю відношення еквівалентності

a ρ b Þ за означенням класів еквівалентності

ab Î Ka  і  ab Î Kb.

Нехай y – довільний елемент такий, що y Î Ka. Оскільки за доведеним b Î Ka, то звідси за означенням класів еквівалентності маємо

b ρ a  і  a ρ y Þ за транзитивною властивістю відношення еквівалентності

b ρ y Þ за означенням класу еквівалентності

y Î Kb.

Отже, будь-який елемент множини Ka є елементом множини Kb, тобто за означенням підмножини множини має місце включення

Ka Ì Kb.

(1)

Аналогічно можна довести включення

Ka É Kb.

(2)

На основі (1) і (2) за антисиметричною властивістю відношення включення має місце рівність

Ka = Kb.  

Із теореми 3 одержуються наслідки.

Наслідок 1. Якщо ρ – відношення еквівалентності на множині A і Ka та Kb – довільні класи еквівалентності, то Ka = Kb тоді і тільки тоді, коли a ρ b.

Коли ρ – відношення еквівалентності на множині A і Ka – клас еквівалентності, то будь-який елемент з цього класу називається його представником.

Наслідок 2. Клас еквівалентності однозначно визначається будь-яким своїм представником.

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

Теорема 4. Кожне відношення еквівалентності на множині задає єдине розбиття цієї множини на класи. Навпаки, кожне розбиття множини на класи задає єдине відношення еквівалентності на цій множині.

► Нехай ρ – відношення еквівалентності на множині A. Розглянемо множину M всіх її різних класів еквівалентності. Згідно теореми 3 елементи множини M задають розбиття множини A на класи. Доведемо, що це розбиття єдине. Припустимо, що є ще й інше розбиття множини A на класи за допомогою відношення ρ. Множину класів цього розбиття позначимо N, а довільний клас — K, який є непорожньою множиною. У множині A знайдеться елемент a такий, що a Î K. Оскільки кожний із класів еквівалентності однозначно задається будь-яким своїм елементом (представником), то K Î M, тобто має місце включення

N Ì M.

(3)

Аналогічно можна довести включення

M Ì N.

(4)

З (3) і (4) випливає, що

M = N.

2. Нехай тепер задано розбиття множини A на класи. Задамо відношення j так: довільні елементи x і y множини A перебувають у відношенні j тоді і тільки тоді, коли x і y належать одному і тому ж класу розбиття. Покажемо, що j є відношенням еквівалентності.

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

Нехай x і y – довільні елементи множини A такі, що x j  y. Це значить, що елементи x і y належать одному і тому ж класу розбиття. Але тоді і елементи y та x з одного й того ж класу розбиття, отже, y j  x, тобто j є симетричним відношенням.

Нехай тепер x, y і z – довільні елементи множини A такі, що x j  y і y j  z. Це означає, що x, y і z належать одному класу розбиття. Але тоді x j  z, тобто j – транзитивне відношення.

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

Припустимо, що для даного розбиття множини A на класи, крім відношення j, можна означити інше відношення еквівалентності y: Довільні елементи x і y множини A тоді і тільки тоді знаходяться у відношенні y, коли елементи x і y належать одному класу розбиття. Тоді для довільної пари (xyΠj дістанемо, що елементи x і y належать одному і тому ж класу розбиття, а, отже, (xyΠy, тобто має місце включення

             j  Ì y.

(5)

Аналогічно можна показати, що має місце включення

            y Ì j.

(6)

З (5) і (6) одержуємо рівність

            j  = y.  

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

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

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

Задача 3. Відношення ρ – "число x має ту ж саму остачу при діленні на 3, що й число y", задане на множині. A = {x Î N | x  7}. Побудувати граф відношення ρ. Довести, що ρ – відношення еквівалентності і записати всі класи еквівалентності.

► Побудуємо граф відношення ρ (мал. 9).

Мал. 9.

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

Кожний з трьох одержаних графів задає клас еквівалентності, а саме: K1 = {1, 4, 7}, K2 = {2, 5}, R0 = {3, 6}.  

  1.  Відношення порядку та його види.

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

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

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

1) відношенням нестрогого порядку, якщо воно рефлексивне;

2) відношенням строгого порядку, якщо воно антирефлексивне;

3) відношенням часткового порядку, якщо воно незв'язне;

4) відношенням лінійного порядку, якщо воно зв'язне.

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

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

1) відношення "x ділиться на y (xy)" є відношенням нестрогого часткового порядку;

2) відношення "x менше y (x < y)" є відношенням строгого лінійного порядку;

3) відношення "x менше або дорівнює y (x ≤ y)" є відношенням нестрогого лінійного порядку.

Якщо множина A впорядкована відношенням ρ, тоді

1) говорять, що елемент z лежить між елементами x і y, якщо ці три елементи різні і x ρ z та z ρ y, записують x ρ z ρ y;

2) елементи x і y називаються сусідніми, якщо вони різні, x ρ y і не існує елемента, який лежить між ними, при цьому елемент x називається попереднім до y, а елемент yнаступним за x. Наприклад, на множині натуральних чисел N, впорядкованої відношенням "менше", число 2 лежить між числами 1 і 3, числа 1 і 2 будуть сусідніми, причому 1 є попереднім до 2, а число 2 буде наступним за 1.

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

Аналогічно поступають при існуванні кількох наступних елементів для одного і того ж елемента.

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

Отже, геометрично відношення порядку, визначене на скінченній множині, можна задати ще й діаграмою. Користуючись діаграмою відношення порядку, визначеного на скінченній множині A, завжди можна вказати лише пари графіка з різними компонентами: для довільних різних елементів x і y множини A x ρ y тоді і тільки тоді, коли існує ланцюг відрізків, який піднімається знизу від вершини x вверх до вершини y. Тому при заданні відношення порядку діаграмою вказується є воно строгого чи нестрогого порядку. Інші властивості впорядкованої множини можна встановити за допомогою діаграми. Зокрема, діаграма лінійного порядку має єдиний ланцюг, який можна зобразити вертикальним відрізком.

Задача 4. На множині A = {x Î N | x < 10} задано відношення ρ – "x ділиться на y (xy)". Довести, що це відношення є відношенням часткового порядку і побудувати його діаграму.

► Як встановлено в одному з попередніх прикладів, відношення подільності є відношенням нестрогого часткового порядку на множині натуральних чисел N, а тому воно буде відношенням нестрогого порядку і на довільній підмножині натуральних чисел. Відношення ρ незв'язне, бо числа 2 і 3 різні, але жодне з них не ділиться на друге. Значить, відношення ρ є відношенням часткового порядку.

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

Оскільки число 1 не ділиться на жодне інше число множини A, то воно не є попереднім для жодного з них. Попередніми ж числами для числа 1 є числа 2, 3, 5 і 7. Для числа 2 попередніми числами є числа 4 і 6, для 3 – числа 6 і 9. Число 4 має попереднім число 8. Числа 5, 6, 7, 8 і 9 у множині A попередніх не мають. Отже, діаграму даного відношення нестрогого часткового порядку можна зобразити так, як на мал. 10.

Мал. 10.  ◄

Зауваження. У математичній літературі по-різному означаються відношення порядку, а тому при її читанні слід завжди звертати увагу на те, в якому значенні вживається термін "відношення порядку".


 

А также другие работы, которые могут Вас заинтересовать

58310. Ознайомлення з дією віднімання. Знак «–». Складання прикладів на віднімання за числовим відрізком та предметними малюнками. Написання цифр 28 KB
  Мета: на основі розгляду малюнків і практичних дій з предметами розкрити зміст дії віднімання взаємозв’язок дій додавання й віднімання; продовжувати роботу над формуванням в учнів навичок складання й розв’язання прикладів на додавання...
58311. Дія віднімання. Складання, запис і розв’язання прикладів на додавання й віднімання. Написання цифр 26.5 KB
  Мета: продовжувати роботу над формуванням в учнів вміння розрізняти дії віднімання та додавання; дати поняття про те що при відніманні результат обов’язково зменшується а при додаванні збільшується; вдосконалювати навички усної лічби...
58312. Зв’язок додавання й віднімання. Складання прикладів на віднімання з прикладів на додавання. Вимірювання довжини відрізків 29.5 KB
  Мета: формувати в учнів уміння складати приклади на додавання з прикладів на віднімання; вдосконалювати навички усної лічби розвивати логічне мислення учнів спостережливість увагу. Обладнання: предметні малюнки до теми таблиці прикладів картки доміно картки цифр.