Отношение эквивалентности

Определения

Определение 1. Пусть $\rho$ — некоторое бинарное отношение на множестве $ A $. Будем говорить, что $\rho$отношение эквивалентности1), если оно одновременно удовлетворяет свойствам

  1. рефлексивности: $(x,x)\in\rho$ для всех $x\in A$;
  2. симметричности: $(x,y)\in\rho\Rightarrow (y,x)\in\rho$ для всех $x,y\in A$;
  3. транзитивности: $((x,y)\in\rho)\wedge((y,z)\in\rho)\Rightarrow (x,z)\in\rho$ для всех $x,y,z\in A$.

В этом случае вместо $(x,y)\in\rho$ употребляется запись $x\sim_{\rho}y$2), где $x,y\in A$.

Пример 1. Отношение равенства $ = $ на множестве действительных чисел является отношением эквивалентности.

Пример 2. Отношение $(n,m)\sim(p,q)\Leftrightarrow nq=mp$ на множестве $\mathbb{Z}^2$ является отношением эквивалентности.

Определение 2. Подмножество $\overline{x}=\{y\in A\vert y\sim_{\rho}x\}$ называется классом эквивалентности3), содержащим $ x $. Любой элемент $y\in\overline{x}$ называется представителем класса4) $\overline{x}$.

Разбиение множества

Определение 3. Набор подмножеств $\{A_{\alpha}\}_{\alpha\in I}$ называется разбиением5) множества $ A $, если

  1. $A_{\alpha}\cap A_{\beta}=\varnothing$ для любых различных $\alpha,\beta\in I$;
  2. $A=\underset{\alpha\in I}{\cup}A_{\alpha}$.

Предложение 1. Множество классов эквивалентности по отношению $\rho$ является разбиением множества $ A $.

Данное предложение означает, что любые два класса эквивалентности либо совпадают, либо не пересекаются и любой элемент множества $ A $ принадлежит какому-либо классу эквивалентности.

Предложение 2. Любое разбиение множества $ A $ определяет некоторое отношение эквиваленитности $\rho$.

Определение 4. Множество всех классов эквивалентности множества $ A $ по отношению $\rho$ называется фактормножеством6) и обозначается $A/\rho$.

Каноническая проекция

Определение 5. Отображение $\pi:A\rightarrow A/\rho:x\mapsto\overline{x}$, которое каждому элементу ставит в соответствие его класс эквивалентности, называется канонической проекцией7), или естественным отображением8) $ A $ на фактормножество $A/\rho$.

Заметим, что каноническая проекция всегда является сюръективным отображением.

Литература

1) equivalence relation
2) $ x $ находится в отношении $\rho$ к $ y $
3) equivalence class
4) class representative
5) set partition
6) factor set
7) canonical projection
8) natural mapping
glossary/relation/equivalence.txt · Последние изменения: 15.02.2014 15:55:53 — ladilova
Наверх
Яндекс.Метрика
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0