Содержание

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

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

Определения

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

рефлексивности: $(x,x)\in\rho$ для всех $x\in A$ ;
симметричности: $(x,y)\in\rho\Rightarrow (y,x)\in\rho$ для всех $x,y\in A$ ;
транзитивности: $((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$ ²⁾, где $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\}$ называется классом эквивалентности³⁾, содержащим $x$ . Любой элемент $y\in\overline{x}$ называется представителем класса⁴⁾ $\overline{x}$ .

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

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

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

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

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

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

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

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

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

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

Литература

теория множеств, естественное отображение, каноническая проекция, класс эквивалентности, множество, отношение эквивалентности, разбиение множества, фактормножество

¹⁾

equivalence relation

²⁾

$x$ находится в отношении $\rho$ к $y$

³⁾

equivalence class

⁴⁾

class representative

⁵⁾

set partition

⁶⁾

factor set

⁷⁾

canonical projection

⁸⁾

natural mapping

glossary/relation/equivalence.txt · Последние изменения: 26.02.2022 13:13:40 — Ладилова Анна

Наверх