Перегляд вихідного коду сторінки Відношення еквівалентності

'''Відно́шення еквівале́нтності''' (<math>\sim</math>) на множині <math>X</math>&nbsp;— це [[бінарне відношення]] для якого виконуються наступні умови:

# [[Рефлексивне відношення|Рефлексивність]]: <math>\,a \sim a</math> для будь-якого <math>a</math> в <math>X</math>,
# [[симетричне відношення|Симетричність]]: якщо <math>\,a \sim b</math>, то <math>\,b \sim a</math>,
# [[Транзитивне відношення|Транзитивність]]: якщо <math>\,a \sim b</math> та <math>\,b \sim c</math>, то <math>\,a \sim c</math>.

Запис вигляду «<math>\,a \sim b</math>» читається як «<math>a</math> еквівалентно <math>b</math>».

Наслідком властивостей рефлексивності, симетричності і транзитивності є те, що будь-яке відношення еквівалентності забезпечує [[Розбиття множини|розбиття]] будь-якої базової множини на непересічні [[Клас еквівалентності|класи еквівалентності]]. Два елементи даної множини еквівалентні між собою тоді і тільки тоді, коли вони належать одному класу еквівалентності.

== Позначення ==
В літературі можуть застосовуватися різні символи для позначення двох елементів {{math|''a''}} і {{math|''b''}} із множини що є еквівалентними відповідно до відношення еквівалентності {{math|''R''}}; найбільш загальними позначеннями є "{{math|''a'' ~ ''b''}}" і "{{math|''a'' ≡ ''b''}}", які використовують коли {{math|''R''}} є неявною, і варіації позначень "{{math|''a'' ~<sub>''R''</sub> ''b''}}", "{{math|''a'' ≡<sub>''R''</sub> ''b''}}", або "{{math|''aRb''}}", які вказують {{math|''R''}} явним чином. Нееквівалентність може записуватися як "{{math|''a'' ≁ ''b''}}" або "<math>a \not\equiv b</math>".

== Пов'язані визначення ==
* '''[[клас еквівалентності|Класом еквівалентності]]''' <math>C(a)</math> елемента <math>a</math> називається підмножина елементів, еквівалентних <math>a</math>. З зазначеного визначення випливає що, якщо <math>b \in C(a)</math>, то <math>C(a) = C(b)</math>.
Множина всіх класів еквівалентності позначається <math>X/{\sim}</math>.
* Для класу еквівалентності елемента <math>a</math> використовується наступне позначення: <math>[a]</math>, <math>a / {\sim}</math>, <math>\overline{a}</math>.
* Множина класів еквівалентності по відношенню <math>\sim</math> є [[Розбиття множини|розбиттям множини]].

== Приклади відношень еквівалентності ==
* Найбільш наочний приклад відношення еквівалентності&nbsp;— поділ учнів школи на класи.
* [[Відношення рівності]] («<math>\;=</math>») тривіальне відношення еквівалентності на довільній множині, зокрема на [[Дійсні числа|множині дійсних чисел]].
* [[Порівняння по модулю]], («а ≡ b (mod n)»).
* В [[Евклідова геометрія|Евклідовій геометрії]]
** Відношення [[Конгруентність (геометрія)|конгруентності]] («<math>\cong</math>»).
** Відношення [[Подібність (геометрія)|подібності]] («<math>\ \sim</math>»).
** Відношення [[Паралельні прямі|паралельності прямих]] («<math>\|</math>»).
* Відношення [[Рівнопотужність|рівнопотужності]] множин є відношенням еквівалентності.
* Еквівалентність функцій в [[Математичний аналіз|математичному аналізі]]:
*: кажуть що функція <math>\, f(x)</math> еквівалентна функції <math>\, g(x)</math> при <math>\, x \rightarrow x_0</math>, якщо вона може бути представлена у вигляді: <math>\, f(x) = \alpha(x) g(x),</math> де <math>\, \alpha(x) \rightarrow 1,</math> при <math>\, x \rightarrow x_0</math>. В даному випадку пишуть <math>\, f(x) \sim g(x)</math>, при <math>\, x \rightarrow x_0</math>. Якщо <math>\, g(x) \ne 0,</math> при <math>\, x \ne x_0</math>, еквівалентність функції <math>\, f(x)</math> та <math>\, g(x),</math> при <math>\, x \rightarrow x_0</math>, очевидно, рівносильна відношенню <math>\lim_{x \rightarrow x_0}{\frac{f(x)}{g(x)}} = 1</math>.
* [[Еквівалентність категорій]]

== Факторизація відображень ==
{{Див. також|Факторизація}}
Множина класів еквівалентності, яка відповідає відношенню еквівалентності <math>\sim</math>, позначається символом <math>X/{\sim}</math> і називається ''фактор-множиною'' відносно <math>\sim</math>.
При цьому [[Сюр'єкція|сюр'єктивне відображення]]
: <math>p\colon x \mapsto C_x</math>
називається ''дійсним відображенням'' (чи ''канонічною проєкцією'') <math>X</math> на фактор-множину <math>X/{\sim}</math>.

Нехай <math>X</math>, <math>Y</math>&nbsp;— множини, <math>f\colon X \to Y</math>&nbsp;— відображення, тоді бінарне відношення <math>x \, {R_f} \,y</math> визначене правилом
: <math>x \mathop{R_f} y \iff f(x) = f(y), \quad x, y \in X</math>
є відношенням еквівалентності на <math>X</math>.
При цьому відображення утворює відображення <math>\overline{f}\colon X/R_f \to Y</math>, яке визначається правилом
: <math>\overline{f}(C_x) = f(x)</math>
чи
: <math>(\overline{f}\circ p)(x) = f(x)</math>.
При цьому отримується ''факторизація'' відображення <math>f</math> на сюр'єктивне відображення <math>p</math> та [[Ін'єкція (математика)|ін'ективне відображення]] <math>\overline{f}</math>.

Факторизація відображень широко використовується в гуманітарних науках та в тих галузях техніки де немає можливостей використовувати числові значення. Вона дозволяє уникати формул там, де їх неможливо використати. Наведемо загально відомий всім приклад:

[[Розклад занять|Розклад уроків]] в школі&nbsp;— є типовий приклад факторизації. В даному випадку <math>X</math>&nbsp;— множина всіх учнів школи, <math>Y</math>&nbsp;— множина всіх предметів, упорядкованих по днях тижня та часом їх проведення. Класами еквівалентності є класи (групи учнів). Відображення <math>f</math>&nbsp;— розклад уроків записаних у щоденники учнів. Відображення <math>\overline{f}</math>&nbsp;— розклад уроків по класам, який вивішують у вестибюлі школи. Там же і вивішується відображення <math>p</math>&nbsp;— списки класів. Цей простий приклад наочно демонструє практичні вигоди факторизації: неможливо собі уявити розклад занять як таблицю в якій занесені всі учні школи в особистому порядку. Факторизація дозволила зобразити потрібну учням інформацію у зручному для використання вигляді в ситуації коли формули застосовувати неможливо.

На цьому переваги факторизації не закінчується. Вона дала можливість розділити роботу між людьми: завуч складає розклад, а учні записують його у щоденники. Аналогічно факторизація дозволила розділити роботу медика, який ставить діагноз та виписує рецепт, і фармацевта який еквівалентно рецепту підбирає ліки. Апофеозом факторизації є конвеєр, де реалізоване максимальне розбиття праці за рахунок стандартизації деталей.

Факторизація дозволила забезпечити модульність сучасної техніки. Наприклад, можна замінити телефон але залишити сім-карту і карту пам'яті зі старого телефону, або поміняти оперативну пам'ять в комп'ютері більше нічого не чіпаючи. Все це гнучкість і модульність в основі яких лежить факторизація.

== Фактор-множина та класи еквівалентності ==

Сукупність множин {B<sub>i</sub>|i∈I} називається [[розбиття множини|розбиттям]] множини A, якщо B<sub>i</sub>=A і B<sub>i</sub>∩B<sub>j</sub> = ∅ для i≠j. Множини B<sub>i</sub>, i∈I є [[підмножина]]ми множини A і називаються '''класами, суміжними класами, блоками''' або '''елементами розбиття'''. Очевидно, що кожний елемент a∈A належить одній і тільки одній множині B<sub>i</sub>, i∈I.

Нехай тепер на множині M задано відношення еквівалентності R. Виконаємо таку побудову. Виберемо деякий [[Елемент (математика)|елемент]] a∈M і утворимо підмножину S<sub>a</sub><sup>R</sup> = {x| x∈M і aRx}, яка складається з усіх елементів множини M, еквівалентних елементу a. Візьмемо другий елемент b∈M такий, що b∉S<sub>a</sub><sup>R</sup> і утворимо множину S<sub>b</sub><sup>R</sup> = {x | x∈M і bRx } з елементів еквівалентних b і&nbsp;т.&nbsp;д. Таким чином одержимо сукупність множин (можливо, нескінченну) {S<sub>a</sub><sup>R</sup>, S<sub>b</sub><sup>R</sup>,…}.

Побудована сукупність множин { S<sub>i</sub><sup>R</sup> | i∈I} є '''[[Фактор-множина|фактор-множиною]]''' множини M за еквівалентністю R і позначається M/R.

Очевидно, що будь-які два елементи з одного класу S<sub>i</sub><sup>R</sup> еквівалентні між собою, в той час як будь-які два елементи з різних класів фактор-множини M/R нееквівалентні.

Класи S<sub>i</sub><sup>R</sup> називають '''[[клас еквівалентності|класами еквівалентності]]''' за відношенням R. Клас еквівалентності, який містить елемент a∈M часто позначають через [a]<sub>R</sub>.

== Див. також ==
* [[Асимптотична рівність]]
* [[Відношення порядку]]
* [[Відношення толерантності]]
* [[Вільний добуток]]

== Джерела ==
* {{Куратовский.Мостовский.Теория множеств}}
* {{Хаусдорф.Теория множеств}}
* {{Мальцев.Алгебраические системы}}
* ''А.&nbsp;И.&nbsp;Кострикин'', Введение в алгебру. {{М.}}: Наука, 1977, 47—51.
* {{MathWorld|urlname=EquivalenceRelation}}
* {{PlanetMath|urlname=EquivalenceRelation}}
* {{springer|urlname=Equivalence_relation}}

{{Теорія порядку|state=expanded}}
{{Математична логіка}}

[[Категорія:Бінарні відношення]]
[[Категорія:Еквівалентність (математика)]]