Отношение эквивалентности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Определение == {{Определение |definition = Бинарное отношение <tex>R</tex> на множестве <tex>X</tex> наз...»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 8 участников)
Строка 1: Строка 1:
== Определение ==
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''отношением эквивалентности''', если оно обладает следующими свойствами:
+
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''отношением эквивалентности''' (англ. ''equivalence binary relation''), если оно обладает следующими свойствами:
 
* [[Рефлексивное отношение|Рефлексивность]]: <tex>\forall x \in X: xRx</tex>.
 
* [[Рефлексивное отношение|Рефлексивность]]: <tex>\forall x \in X: xRx</tex>.
 
* [[Симметричное отношение|Симметричность]]: <tex>\forall x, y \in X:</tex> если <tex>xRy</tex>, то <tex>yRx</tex>.
 
* [[Симметричное отношение|Симметричность]]: <tex>\forall x, y \in X:</tex> если <tex>xRy</tex>, то <tex>yRx</tex>.
Строка 11: Строка 10:
 
== Примеры отношений эквивалентности ==
 
== Примеры отношений эквивалентности ==
 
* Отношение ''равенства''(<tex>=</tex>) является тривиальным примером отношения эквивалентности на любом множестве.
 
* Отношение ''равенства''(<tex>=</tex>) является тривиальным примером отношения эквивалентности на любом множестве.
* Отношение ''равенства по модулю <tex>k</tex>'': <tex>a \equiv b (mod~k)</tex>.
+
* Отношение ''равенства по модулю <tex>k</tex>'': <tex>a \equiv b \mod k </tex> на множестве целых чисел.
 
* Отношение ''параллельности'' прямых на плоскости.
 
* Отношение ''параллельности'' прямых на плоскости.
 
* Отношение ''подобия'' фигур на плоскости.
 
* Отношение ''подобия'' фигур на плоскости.
Строка 18: Строка 17:
 
* Отношение ''быть одного роста'' на множестве людей.
 
* Отношение ''быть одного роста'' на множестве людей.
 
Следующие отношения не являются отношениями эквивалентности:
 
Следующие отношения не являются отношениями эквивалентности:
* [[Отношение порядка|Отношения порядка]], т.к. они не являются симметричными.
+
* [[Отношение порядка|Отношения порядка]], так как они не являются симметричными.
* Отношение ''быть знакомым'' на множестве людей, т.к. оно не транзитивное.
+
* Отношение ''быть знакомым'' на множестве людей, так как оно не транзитивное.
  
 
== Классы эквивалентности ==
 
== Классы эквивалентности ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Система непустых подмножеств <tex>\{M_1, M_2, ..., M_n\}</tex> множества <tex>M</tex> называется '''разбиением''' данного множества, если:
+
Система непустых подмножеств <tex>\{M_1, M_2, \ldots, M_n, \ldots\}</tex> множества <tex>M</tex> называется '''разбиением''' (англ. ''partition'') данного множества, если:
* <tex>M = M_1 \cup M_2 \cup ... \cup M_n</tex>.
+
* <tex>M = M_1 \cup M_2 \cup \ldots \cup M_n \cup \ldots</tex>
 
* <tex>M_i \cap M_j = \varnothing</tex> при <tex>i \neq j</tex>.
 
* <tex>M_i \cap M_j = \varnothing</tex> при <tex>i \neq j</tex>.
Множества <tex>M_1, M_2, ..., M_n</tex> называются '''классами''' данного разбиения.
+
Множества <tex>M_1, M_2, \ldots, M_n, \ldots</tex> называются '''классами''' данного разбиения.
 
}}
 
}}
 
Примерами разбиений являются:
 
Примерами разбиений являются:
Строка 38: Строка 37:
 
Если на множестве M задано отношение эквивалентности <tex>\thicksim</tex>, то оно порождает разбиение этого множества на '''классы эквивалентности''' такое, что:
 
Если на множестве M задано отношение эквивалентности <tex>\thicksim</tex>, то оно порождает разбиение этого множества на '''классы эквивалентности''' такое, что:
 
* любые два элемента одного класса находятся в отношении <tex>\thicksim</tex>
 
* любые два элемента одного класса находятся в отношении <tex>\thicksim</tex>
* любые два элементы разных классов не находятся в отношении <tex>\thicksim</tex>
+
* любые два элемента разных классов не находятся в отношении <tex>\thicksim</tex>
 
}}
 
}}
 
Семейство всех классов эквивалентности множества образует множество, называемое ''фактор-множеством'', или ''факторизацией'' множества <tex>M</tex> по отношению <tex>\thicksim</tex>, и обозначаемое <tex>M/^{\thicksim}</tex>.
 
Семейство всех классов эквивалентности множества образует множество, называемое ''фактор-множеством'', или ''факторизацией'' множества <tex>M</tex> по отношению <tex>\thicksim</tex>, и обозначаемое <tex>M/^{\thicksim}</tex>.
  
== Ссылки ==
+
== Примеры ==
 +
 
 +
* ''Равенство'' - классический пример отношения эквивалентности на любом множестве, в т. ч. [[Вещественные числа|вещественных чисел]]
 +
* Равенство по ''модулю:'' <tex> a \equiv b~(mod ~ m) </tex>
 +
* В ''Евклидовой геометрии:''
 +
** отношение подобия<tex> ("\thicksim ") </tex>
 +
** отношение параллельности<tex>\colon ~ ("\parallel ") </tex>
 +
** отношение конгруэнтности<tex>\colon ~ ("\cong ") </tex>
 +
* Разбиение многоугольников по количеству вершин
 +
* Отношение ''равносильности'' на множестве уравнений
 +
* Отношение [[Мощность множества|равномощности]] множеств
 +
* Отношение ''принадлежать к одному виду'' на множестве животных
 +
* Отношение ''жить в одном городе'' на множестве людей
 +
 
 +
== См. также ==
 +
* [[Определение_отношения|Определение отношения]]
 +
* [[Рефлексивное_отношение|Рефлексивное отношение]]
 +
* [[Симметричное_отношение|Симметричное отношение]]
 +
* [[Транзитивное_отношение|Транзитивное отношение]]
 +
* [[Отношение_порядка|Отношение порядка]]
 +
 
 +
== Источники информации ==
 
* [http://ru.wikipedia.org/wiki/Отношение_эквивалентности Wikipedia | Отношение эквивалентности]
 
* [http://ru.wikipedia.org/wiki/Отношение_эквивалентности Wikipedia | Отношение эквивалентности]
 +
* [http://en.wikipedia.org/wiki/Equivalence_relation Wikipedia | Equivalence relation]
 
* [http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/1.htm Бинарные отношения. Отношение эквивалентности]
 
* [http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/1.htm Бинарные отношения. Отношение эквивалентности]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Отношения]]

Текущая версия на 19:07, 4 сентября 2022

Определение:
Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется отношением эквивалентности (англ. equivalence binary relation), если оно обладает следующими свойствами:

Отношение эквивалентности обозначают символом [math]\thicksim[/math]. Запись вида [math]a \thicksim b[/math] читают как "[math]a[/math] эквивалентно [math]b[/math]"

Примеры отношений эквивалентности

  • Отношение равенства([math]=[/math]) является тривиальным примером отношения эквивалентности на любом множестве.
  • Отношение равенства по модулю [math]k[/math]: [math]a \equiv b \mod k [/math] на множестве целых чисел.
  • Отношение параллельности прямых на плоскости.
  • Отношение подобия фигур на плоскости.
  • Отношение равносильности на множестве уравнений.
  • Отношение связности вершин в графе.
  • Отношение быть одного роста на множестве людей.

Следующие отношения не являются отношениями эквивалентности:

  • Отношения порядка, так как они не являются симметричными.
  • Отношение быть знакомым на множестве людей, так как оно не транзитивное.

Классы эквивалентности

Определение:
Система непустых подмножеств [math]\{M_1, M_2, \ldots, M_n, \ldots\}[/math] множества [math]M[/math] называется разбиением (англ. partition) данного множества, если:
  • [math]M = M_1 \cup M_2 \cup \ldots \cup M_n \cup \ldots[/math]
  • [math]M_i \cap M_j = \varnothing[/math] при [math]i \neq j[/math].
Множества [math]M_1, M_2, \ldots, M_n, \ldots[/math] называются классами данного разбиения.

Примерами разбиений являются:

  • Разбиение многоугольников на группы по числу вершин.
  • Разбиение треугольников по свойствам углов (остроугольные, прямоугольные, тупоугольные).
  • Разбиение учащихся школы по классам.
Теорема:
Если на множестве M задано отношение эквивалентности [math]\thicksim[/math], то оно порождает разбиение этого множества на классы эквивалентности такое, что:
  • любые два элемента одного класса находятся в отношении [math]\thicksim[/math]
  • любые два элемента разных классов не находятся в отношении [math]\thicksim[/math]

Семейство всех классов эквивалентности множества образует множество, называемое фактор-множеством, или факторизацией множества [math]M[/math] по отношению [math]\thicksim[/math], и обозначаемое [math]M/^{\thicksim}[/math].

Примеры

  • Равенство - классический пример отношения эквивалентности на любом множестве, в т. ч. вещественных чисел
  • Равенство по модулю: [math] a \equiv b~(mod ~ m) [/math]
  • В Евклидовой геометрии:
    • отношение подобия[math] ("\thicksim ") [/math]
    • отношение параллельности[math]\colon ~ ("\parallel ") [/math]
    • отношение конгруэнтности[math]\colon ~ ("\cong ") [/math]
  • Разбиение многоугольников по количеству вершин
  • Отношение равносильности на множестве уравнений
  • Отношение равномощности множеств
  • Отношение принадлежать к одному виду на множестве животных
  • Отношение жить в одном городе на множестве людей

См. также

Источники информации