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

Отношение $\rho$ на множестве $X$ называется рефлексивным, если для любого элемента $x\in X$ выполняется $x\rho x$.

Отношение $\rho$ на множестве $X$ называется иррефлексивным, если для любого $x\in X$ выполняется $(x,x)\notin\rho$.

Отношение $\rho$ на множестве $X$ называется симметричным, если для любых $x,y\in X$ из $x\rho y$ следует $y\rho x$.

Отношение $\rho$ на множестве $X$ называется антисимметричным, если для любых $x,y\in X$ из $x\rho y$ и $y\rho x$ следует $x=y$.

Отношение $\rho$ на множестве $X$ называется транзитивным, если для любых $x,y,z\in X$ из $x\rho y$ и $y\rho z$ следует $x\rho z$.

Определение:

Бинарное отношение $\rho$ на множестве $X$ называется отношением эквивалентности, если оно рефлексивно, транзитивно и симметрично. Если $\rho$ — отношение эквивалентности и $x\rho y$, говорят, что $x$ и $y$ эквивалентны.

1) $\rho_= = \{(x,y) | x,y\in\mathbb{R}, x=y\}$ — отношение эквивалентности.

2) Отношение подобия на множестве треугольников является отношением эквивалентности.

3) Отношение сравнимости по модулю $n$ $x\rho y \Leftrightarrow x\equiv y (\mod{ n})$ на множестве всех целых чисел $\mathbb{Z}$ является отношением эквивалентности.

Определение:

Пусть на множестве $X$ введено отношение эквивалентности $\rho$.

Классом эквивалентности, порожденным элементом $x$, называется подмножество множества $X$, состоящее из всех элементов, эквивалентных $x$:

[math]\displaystyle{ [x] = \{ y | y\in X, x\rho y \} }[/math].

Пример

1) Классы эквивалентности по отношению равенства на множестве вещественных чисел состоят из единственного элемента: $[x]=\{x\}$.

2) Класс эквивалентности по отношению подобия треугольников состоит из всех треугольников, подобных порождающему класс.

3) Класс эквивалентности для отношения сравнимости по модулю $n$ на множестве целых чисел $\mathbb{Z}$, порожденный элементом $a$, имеет вид $\{a+kn | k\in \mathbb{Z}\}$. Очевидно, что числа $0$, $1$, $2$, ..., $n-1$ порождают различные классы. С другой стороны, для любого числа $t\in \mathbb{Z}$ оно представимо в виде $t=a+kn$, где $k\in \mathbb{Z}$, а $a\in\{0,1,...,n-1\}$. Значит, для любого целого числа порожденный им класс эквивалентности совпадает с одним из указанных. Таким образом, отношение сравнимости по модулю $n$ порождает $n$ различных классов эквивалентности: $[0],[1],..., [n-1]$.

Утверждение:

Пусть $\rho$ — отношение эквивалентности на множестве $X$. Тогда 1) для любого $x\in X$ верно, что $x\in[x]$; 2) для любых $x,y\in X$, если $x \rho y$, то $[x]=[y]$ (класс эквивалентности порождается любым своим элементом).

Доказательство:

Доказательство пункта 1) следует из рефлексивности отношения $\rho$.

Докажем 2). Пусть $z\in[y]$. По определению класса эквивалентности $y\rho z$. Тогда из $x\rho y$ и $y\rho z$ в силу транзитивности отношения $\rho$ следует $x\rho z$ и $z\in [x]$. Следовательно, $[y]\subseteq [x]$.

В силу симметричности отношения $\rho$ верно и $y\rho x$. Значит, рассуждая аналогично $\forall z\in [x]$ $\Rightarrow$ $x\rho z \Rightarrow y\rho z \Rightarrow z\in [y]$. Таким образом, получим $[x]\subseteq [y]$, что и требовалось доказать.

[math]\displaystyle{ \blacksquare }[/math]

Определение:

Разбиением множества $A$ называется совокупность его попарно непересекающихся непустых подмножеств $A_i$ таких,

что каждый элемент $x\in A$ принадлежит одному из этих подмножеств:

$\{A_1, A_2, ..., A_k\}: A_i\neq\varnothing, i=\overline{1,k}, A_i\cap A_j=\varnothing, i,j=\overline{1,k}, i\neq j, A = A_1\cup A_2 \cup ... \cup A_k.$

Утверждение:

Всякое разбиение множества $X$ определяет на $X$ отношение эквивалентности $\rho$: $x \rho y$ тогда и только тогда, когда $x$ и $y$ принадлежат одному подмножеству разбиения.

Доказательство:

Рефлексивность и симметричность очевидны. Покажем транзитивность. Пусть $x\rho y$ и $y\rho z$. Тогда $x,y\in X_1$ и $y,z\in X_2$, где $X_1$ и $X_2$ — подмножества разбиения $X$. Поскольку $y\in X_1$ и $y\in X_2$, а подмножества разбиения не могут пересекаться, то $X_1=X_2$. Таким образом, $x,z\in X_1$ и $x\rho z$.

Всякое отношение эквивалентности $\rho$ определяет разбиение множества $X$ на классы эквивалентности по этому отношению.

Покажем, что набор классов эквивалентности по отношению $\rho$ образуют разбиение $X$. Из доказанного ранее утверждения следует, что каждый элемент множества $X$ принадлежит некоторому классу эквивалентности. Следовательно, объединение классов эквивалентности равно $X$. В то же время, из того же утверждения следует, что любые два класса эквивалентности либо не пересекаются, либо совпадают, если имеют хоть один общий элемент: $z\in [x]$, $z\in [y]$ $\Rightarrow$ $x\rho z$, $z\rho y$ $\Rightarrow$ $x\rho y$ $\Rightarrow$ $[x]=[y]$.

Совокупность классов эквивалентности элементов множества $X$ по отношению эквивалентности $\rho$ называется фактор-множеством множества $X$ по отношению $\rho$ и обозначается $X/\rho$.

[math]\displaystyle{ \blacksquare }[/math]