Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

Відношення

Розглянемо декартовий добуток другого степеня множини Х: Х2 = Х ´ Х. Довільну підмножину R множини Х2 (R Í Х2) будемо називати бінарним відношенням (або просто відношенням), заданим на множині Х. Вважатимемо, що впорядковані елементи x, х' Î Х знаходяться між собою у відношенні R, коли (x, х') Î R. Якщо на Х задано відношення R Í X 2, то запис x R х' означає, що x і х' знаходяться у відношенні R, тобто(x, х') Î R.

Розглянемо кілька прикладів відношень:

1) на множині N відношення £ . Ясно, що впорядковані пари (3, 7) і (5, 5) належать цьому відношенню, а пара (4, 1) не належить;

2) на множині Р(Х) всіх підмножин множини Х = {1, 3, 5, 7, 9} відношення Í. Пари підмножин ({1, 3}, {1, 3, 9}) і ({5, 7, 9}, {5, 7, 9}) належать цьому відношенню, а пара підмножин ({1, 5, 7}, {3, 5, 9}) не належить.

Відношення R на множині X називається:

1) рефлективним, якщо довільний елемент множини знаходиться у відношенні сам з собою, тобто для будь-якого х Î Х виконується х R х. Прикладами рефлективних відношень можуть бути ≤, ≥, = на множині натуральних чисел;

2) антирефлективним, якщо для будь-якого х Î Х пара (х, х) не належить до відношення R. Прикладами антирефлективних відношень можуть бути <, >, ≠ на множині раціональних чисел;

3) симетричним, якщо для довільних x, х' Î Х з того, що x R х' випливає х' R x;

4) антисиметричним, якщо для довільних x, х' Î Х з того, що x R х' і х' R x, випливає x = х' (наприклад, £ на N, тому що з x £ х' і х' £ x випливає х= х');

5) транзитивним, якщо для довільних x, х', х'' Î Х з того, що x R х' і х' R х'', випливає x R х'' (наприклад, відношення Í на множині Р(Х) чи відношення £ на множині N).

Наведемо деякі приклади відношень:

1) R = {(x, х') | x, х' Î Q, | x - х' | £ 2007}

Відношення рефлективне, бо для будь-якого xÎQвиконується нерівність | x - х | £ 2007

Відношення не є антирефлективним, бо скажімо для елемента x=5ÎQ нерівність | x - х | £ 2007 виконується.

Відношення є симетричним, бо для довільних x, х' Î Q, з нерівності | x - х' | £ 2007 випливає нерівність | x' - х | £ 2007

Відношення не є антисиметричним, бо для різних елементів x=7 та x'=5 з множини Q одночасно виконуються нерівності | x - х' | £ 2007 та | x' - х | £ 2007

Відношення не є транзитивним, бо для елементів x=2010, x'=1 та x''=10 з множини Q нерівності | x - х' | £ 2007 та | x' - x'' | £ 2007 виконуються, а нерівність | x - х'' | £ 2007 не виконується.

2) R = {(x, y) | x, y Î С, якщо |x| £ |y| £ |y2|}

 

Розглянемо далі відношення, які мають особливе значення.

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

а) рефлективності: (x, х) Î R при будь-якому х Î Х;

б) симетричності: з (x1, х2) Î R випливає (x2, х1) Î R;

в) транзитивності: якщо (x1, х2) Î R і (x2, х3) Î R, то (x1, х3) Î R;

Замість того, щоб писати (x1, х2) Î R, часто пишуть x1 ~ x2 або x1 º x2(mod R) (читається так: x1 конгруентно x2 за модулем R) чи, простіше, (x1 ~ x2 або x1 º x2, якщо немає необхідності ще раз вказувати, що мова йде про одне й те саме відношення R).

Приклади: 1)°Визначимо на множині цілих чисел Z відношення еквівалентності так, що рºq, тоді і тільки тоді, коли p - q ділиться без остачі на деяке наперед задане натуральне число m >1, скажімо m=5. У теорії чисел таке відношення записується у вигляді р º q(mod т).

2)°Нехай Х - множина прямих на площині. Визначимо відношення еквівалентності для прямих x1 іx2, покладаючи x1 º x2, коли ці прямі паралельні.

3) Нехай Х – множина всіх студентів, які присутні на лекції з дискретної математики. Два студенти еквівалентні, якщо вони народилися в тому самому місяці року.

Для x Î X позначимо через K(x)підмножину, що складається з елементів, еквівалентних x, тобто K(x) = {y | y Î X; y ~ x}. Таку підмножину будемо називати класом еквівалентності. Зрозуміло, що клас еквівалентності є множиною всіх елементів, еквівалентних довільному елементу з цього класу. Справедлива наступна теорема:

Теорема 1. Два класи еквівалентності або не перетинаються або співпадають.

Доведення. Припустимо, що перетин множин K(x K(х')непорожній, і візьмемо z Î K(x) Ç K(х'). Клас еквівалентності K(x) утворений з елементів, еквівалентних одному зі своїх елементів x. Оскільки x і z еквівалентні, то за властивістю транзитивності отримуємо, що K(x) утворений також з елементів, еквівалентних z. Аналогічно K(х') утворений з елементів, еквівалентних z. Таким чином, K(х) і K(х') співпадають.

Відношення еквівалентності на множині Х породжує деяке розбиття множини Х, тобто деяку сім’ю непорожніх підмножин множини X (класів еквівалентності), які попарно не перетинаються,а їхоб’єднання рівне X. Будь-які два елементи з одного класу зв’язані відношенням еквівалентності, тобто еквівалентні;з різних класів - не еквівалентні.

Навпаки, будь-яке розбиття множини X: Х =, де Xj непорожні і попарно не перетинаються, визначає деяке відношення еквівалентності, а саме x º х', якщо існує такий індекс j Î J, що x,х' Î Xj. У цьому випадку підмножини Xj є класами еквівалентності для цього відношення.


Читайте також:

  1. Аналіз співвідношення активів із джерелами їх фінансування
  2. Антонімічні відношення
  3. Безрозмірною характеристикою гідротрансформатора називається залежність коефіцієнтів пропорційності моментів насосного і турбінного коліс від його передаточного відношення.
  4. Бінарне відношення порядку.
  5. Варіанти співвідношення потреб і виробництва
  6. Взаємовідношення біологічного, соціального і духовного в людині.
  7. Взаємовідношення віри і розуму, філософії та теології у Фоми Аквінського та пізній схоластиці.
  8. Взаємовідношення віри і розуму, філософії та теології у Фоми Аквінського та пізній схоластиці.
  9. Взаємовідношення ініціатора і реципієнта трансферу технологій
  10. Взаємозалежність і співвідношення громадянського суспільства і правової держави.
  11. Взаємозалежність і співвідношення громадянського суспільства і правової держави.
  12. Види інноваційних стратегій та їх співвідношення




Переглядів: 1219

<== попередня сторінка | наступна сторінка ==>
Композиція відображень | Зчисленні множини

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.004 сек.