Отношение эквивалентности
Отношение $\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$.
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$, называется подмножество множества $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]$.
Доказательство пункта 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]$, что и требовалось доказать.
что каждый элемент $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\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$.
Конспект: Дискретная математика