СВ в 09:41, 24 октября 2026

2026-10-24T09:41:12Z

← Предыдущая		Версия 09:41, 24 октября 2026
Строка 23:		Строка 23:

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

			[[Файл:p11-01-equivalence-classes.svg\|frame\|none\|800px\|alt=Множество из девяти чисел разбито на три класса по остаткам 0, 1 и 2 при делении на 3\|Рис. 1. Сравнимость по модулю 3 разбивает <math>X=\{0,\ldots,8\}</math> на три класса <math>[0]</math>, <math>[1]</math>, <math>[2]</math>. Классы не пересекаются, их объединение — всё <math>X</math>, а фактор-множество состоит из трёх элементов.]]

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

СВ в 19:13, 9 октября 2026

2026-10-09T19:13:50Z

← Предыдущая		Версия 19:13, 9 октября 2026
Строка 83:		Строка 83:
	эквивалентности $\rho$ называется ''фактор-множеством'' множества $X$ по отношению $\rho$ и обозначается $X/\rho$.		эквивалентности $\rho$ называется ''фактор-множеством'' множества $X$ по отношению $\rho$ и обозначается $X/\rho$.
	}}		}}

			Конспект: [[Дискретная математика]]

СВ в 18:55, 9 октября 2026

2026-10-09T18:55:18Z

← Предыдущая		Версия 18:55, 9 октября 2026
Строка 19:		Строка 19:

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

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

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

Строка 26:		Строка 28:
	Пусть на множестве $X$ введено отношение эквивалентности $\rho$.		Пусть на множестве $X$ введено отношение эквивалентности $\rho$.
	Классом эквивалентности, порожденным элементом $x$, называется подмножество множества $X$, состоящее из всех элементов, эквивалентных $x$:		Классом эквивалентности, порожденным элементом $x$, называется подмножество множества $X$, состоящее из всех элементов, эквивалентных $x$:
	$[x] = \{y \| y\in X, x\rho y\}.$		<math>[x] = \{ y \| y\in X, x\rho y \}</math>.
	}}		}}

СВ: Новая страница: «Отношение $\rho$ на множестве $X$ называется '''рефлексивным''', если для любого элемента $x\in X$...»

2026-10-09T18:53:33Z

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

Новая страница

Отношение $\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$.

{{Определение
|definition=

Бинарное отношение $\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}$ является отношением эквивалентности.

{{Определение
|definition=
Пусть на множестве $X$ введено отношение эквивалентности $\rho$.
Классом эквивалентности, порожденным элементом $x$, называется подмножество множества $X$, состоящее из всех элементов, эквивалентных $x$:
$[x] = \{y | y\in X, x\rho y\}.$
}}

== Пример ==

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]$.

{{Утверждение
|statement=Пусть $\rho$ {{---}} отношение эквивалентности на множестве $X$. Тогда 1) для любого $x\in X$ верно, что $x\in[x]$;
2) для любых $x,y\in X$, если $x \rho y$, то $[x]=[y]$ (класс эквивалентности порождается любым своим элементом).
|proof=
Доказательство пункта 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]$, что и требовалось доказать.
}}
{{Определение
|definition=
Разбиением множества $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.$
}}

{{Утверждение
|statement=Всякое разбиение множества $X$ определяет на $X$ отношение эквивалентности $\rho$: $x \rho y$ тогда и только тогда, когда $x$ и $y$ принадлежат одному подмножеству разбиения.
|proof=
Рефлексивность и симметричность очевидны.
Покажем транзитивность. Пусть $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$.
}}

Отношение эквивалентности - История изменений

СВ в 09:41, 24 октября 2026

СВ в 19:13, 9 октября 2026

СВ в 18:55, 9 октября 2026

СВ: Новая страница: «Отношение $\rho$ на множестве $X$ называется '''рефлексивным''', если для любого элемента $x\in X$...»