рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Відношення еквівалентності - раздел Математика, Основи Дискретної математики   Рефлексивне, Симетричне Та Транзитивне Відношення На Множині ...

 

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

Прикладом відношення еквівалентності на множині А={a,b,c,d} є відношення R=iAÈ{<a,d>,<d,a>,<c,b>,<b,c>}. Відношення R={<x,y>| x та y – особи одного року народження} на множині людей є відношенням еквівалентності, оскільки R рефлексивне (адже твердження «х та х – особи одного року народження» істинне для будь-якого х з множини людей, отже, R містить усі діагональні пари), симетричне (якщо <x,yR, то це означає, що х та у – особи одного року народження, але тоді у та х – особи одного року народження, звідки <y,xR), транзитивне (якщо <x,yR та <y,zR, тобто х та у – особи одного року народження й у та z – особи одного року народження, то й х та z – особи одного року народження, отже, <x,zR). Відношення іА (тобто відношення тотожності на А) на довільній множині А є відношенням еквівалентності, оскільки іАÍіА (іА рефлексивне), <x,yіА Þ x=y Þ <y,xіА (іА симетричне), <x,yіА, <y,zіА Þ x=y=z Þ <x,zіА (іА транзитивне). Відношення R={<1,1>,<2,1>,<1,2>} на множині {1,2} не є відношенням еквівалентності, оскільки воно не рефлексивне (<2,2>ÏR) (а також не транзитивне). Відношення {<x,y>| x не вищий на зріст за y} на множині людей не є відношенням еквівалентності, тому що воно не симетричне.

Теорема 7. Бінарне відношення R на множині А є відношенням еквівалентності тоді й тільки тоді, коли існує розбиття Р множини А таке, що R={<x,y>| x,yÎC для деякої множини С з Р}.

Доведення. Нехай Р – розбиття множини А. Покажемо, що відношення R={<x,y>| x,yÎC для деякої С з Р} є відношенням еквівалентності на А. Нехай х – довільний елемент множини А. Оскільки Р – розбиття А, то знайдеться така множина С з розбиття Р, що хÎС, але тоді, за визначенням відношення R, <x,xR, отже, iAÍR, тобто R рефлексивне. Нехай <x,yR. Це означає, що x,yÎC для деякої С з Р, але тоді у,хÎC для деякої С з Р, тобто <y,xR, отже, R симетричне. Нехай <x,yR, <y,zR. Це означає, що x,yÎC для деякої С з Р й у,zÎC1 для деякої С1 з Р, але оскільки Р – розбиття, то кожен елемент множини А належить лише одній множині з розбиття, тому yÎC, yÎC1 Þ C=C1, а тоді xÎC, zÎC, звідки <x,zR, тобто R транзитивне. Отже, R – відношення еквівалентності на А.

Нехай тепер R – відношення еквівалентності на А. Покажемо, що існує таке розбиття Р множини А, що <x,yR Û x,yÎC для деякої множини С з Р. Нехай хÎА. Розглянемо множину К(х)={u| uÎA, <x,uR}. Назвемо К(х) класом елементу х. Оскільки <x,xR для кожного х з А, то хÎК(х), отже, К(х)¹Æ для кожного х з А. Таким чином, множина усіх класів елементів множини А утворює покриття множини А. Покажемо, що для будь-яких х та у з множини А або К(х)=К(у), або К(хК(у)=Æ. Для довільного елемента у множини А можуть бути два випадки: уÎК(х) або уÏК(х). Покажемо, що у випадку уÎК(х) К(х)=К(у). Нехай аÎК(х). Тоді <x,аR, але з визначення класу елемента х випливає, що <x,yR. Оскільки R симетричне, то <у,хR. З транзитивності R маємо <у,аR, отже, аÎК(у), тобто К(хК(у). Аналогічно доводиться, що К(уК(х). Таким чином, якщо уÎК(х), то К(х)=К(у). Розглянемо випадок уÏК(х). Припустимо, що К(хК(у)¹Æ. Тоді існує сÎК(хК(у), звідки сÎК(х) та сÎК(у), отже, <x,cR та <y,cR. Оскільки R симетричне та транзитивне, то <x,yR, тобто уÎК(х), отже, маємо суперечність (ми розглядаємо випадок уÏК(х)). Таким чином, якщо уÏК(х), то К(хК(у)=Æ. Ми довели, що покриття множини А, котре утворюється усіма класами елементів цієї множини, складається з множин, кожні дві з яких або не перетинаються, або збігаються. Сукупність усіх попарно різних множин даного покриття утворює деяке розбиття Р множини А. За побудовою Р <x,yR Û x,yÎC для деякої множини С з Р.

Розглянемо приклади побудови розбиття множини за визначеним на ній відношенням еквівалентності. Нехай на множині А={a,b,c,d,e} задано відношення еквівалентності R=iAÈ{<a,c>,<c,a>,<d,e>,<e,d>}. Визначимо для кожного елемента х множини А клас К(х) цього елемента. Маємо: К(а)={a,c}, K(b)={b}, K(c)={c,a}, K(d)={d,e}, K(e)={e,d}. Виберемо з побудованої сукупності класів ті, які є попарно різними. Маємо:

Р={{a,c}, {b}, {d,e}}. Це й є шукане розбиття.

Нехай на множині N задано відношення R таке, що xRy Û х та у – числа однакової парності (тобто х та у обидва парні або х та у обидва непарні). R є відношенням еквівалентності, оскільки для кожного хÎN х та х – числа однакової парності, отже, іАÍR, тобто R рефлексивне. Якщо х та у – числа однакової парності, то у та х теж числа однакової парності, тобто R симетричне. Якщо х та у – числа однакової парності й у та z – числа однакової парності, то, зрозуміло, х та z також є числа однакової парності, тобто R транзитивне. Таким чином, R є відношенням еквівалентності на N, отже, визначає на N деяке розбиття Р. Кожен елемент множини N належить лише одному класу розбиття. Позначимо Р0 – клас розбиття, який містить число 0. Цьому класу будуть також належати ті числа з N, котрі мають ту ж саму парність, що й число 0, тобто усі додатні парні числа. Таким чином, Р0={2k| kÎN}. Число 1 не входить у Р0, отже, у Р існує клас розбиття (позначимо його Р1), що містить число 1. Цей клас містить також усі числа, що мають ту саму парність, що й число 1, тобто усі додатні непарні числа. Отже, Р1={2k+1| kÎN}. Таким чином, Р={P1,P2} – шукане розбиття, оскільки P1ÈP2=N, P1ÇP2=Æ й <х,уR Û x,y належать одному й тому самому класу розбиття (тобто або х,уÎP1, або х,уÎР2).

 

– Конец работы –

Эта тема принадлежит разделу:

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

Київський національний університет технологій та дизайну... М К МОРОХОВЕЦЬ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Відношення еквівалентності

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

КИЇВ КНУТД 2005
  УДК 51.681.3517   Конспект лекцій з курсу “Основи дискретної математики” для студентів спеціальності “Комп’ютерні науки” 6.0402 / Автор М.К.Мороховец

Лекція 1. Поняття множини. Операції над множинами
    Теорія множин як математична дисципліна створена німецьким мате-матиком Г.Кантором. Згідно з його визначенням, множиною є довільне зі-брання певних об’єктів н

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

Включення та рівність множин
Нехай А та В – множини. Будемо говорити, що А включається у В, або А є підмножиною В (й позначати АÍВ), якщо кожен елемент множини

Операції над множинами
  Об’єднанням множин А та В (позначається АÈВ) називається множина усіх об’єктів, що є елементами множини А або В, тобто А

Властивості операцій над множинами
Теорема 1. Для будь-яких підмножин А, В, С універсальної множини U наведені нижче рівності є тотожностями (вираз А' слід розуміти як UА

Булеан множини
  Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо

Задачі та вправи
  І. Описати словами множини: 1) {x| x=2y+1, yÎN}, 2) {x| x=2y-1, yÎN},

Декартів добуток множин
  Упорядкованою парою об’єктів х та y (позначається <x,y>) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у

Поняття відношення
  Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням R, заданим на множинах А та В, називається довільна підмножина декар

Операції над відношеннями
  Нехай R1, R2 – відношення, задані на множинах A1,…,An. Об’єднанням відношень R1 та R2

Види бінарних відношень
  Бінарне відношення R на множині А називається симетричним, якщо <x,y>ÎR Þ <y,x>ÎR. Пару

Фактор-множина
  Нехай R – відношення еквівалентності на А. Тоді, як відомо, існує розбиття множини А, яке визначається відношенням R. Позначимо це розбиття через А

Замикання відношень
  Рефлексивним замиканням бінарного відношення R, заданого на множині А (позначається Rr), називається відношення Rr=i

Задачі та вправи
  І. Чи існують на множині {1,2,3,4} такі два різні відношення R та S, що: 1) Rr=Sr; 2) Rs=Ss; 3)

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

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

Задачі та вправи
  І. Які з відношень завдань XXVIІ-XXІX до попереднього розділу є відношен-нями: 1) часткового порядку, 2) строгого порядку, 3) передпорядку, 4) лінійного порядку, 5) повного порядку.

Поняття відображення
  Відношення R, задане на множинах А та В, називається функціональним, якщо для кожного елемента xÎА існує не більше одного елемента

Види відображень
  Відображення F множини А у множину В називається відображенням А на В (або сюр’єктивним відображенням, або сюр’єкцією), як

Задачі та вправи
  І. Визначити, які з відображень є: а) частковими, б) сюр’єктивними, в) ін’єктивними, г) взаємно однозначними. А={a,b,c,d}, B={b

Рівнопотужні множини
  Множини А та В називаються рівнопотужними (еквівалентними), якщо існує взаємно однозначне відображення А на В. Наприклад, множини

Потужність множини
  Визначимо відношення ~ на множині усіх множин U: A~В Û А та В рівнопотужні. Дане відношення рефлексивне (А~А), симетричне (якщ

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

Задачі та вправи
  І. Навести приклад множини Y, еквівалентної множині X={1,2,3,4,5}. Скільки взаємно однозначних відображень існує між Х та Y? ІІ. Чи рівнопотужні

СПИСОК ВИКОРИСТАНОЇ ТА РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ
    1. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. – 400 с. 2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программировани

СИМВОЛИ ТА ПОЗНАЧЕННЯ
    N – множина усіх невід’ємних цілих чисел N+ – множина усіх додатних цілих чисел Z – м

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги