Відношення еквівалентності

Матеріал з Вікіпедії — вільної енциклопедії.

ВІДНОШЕННЯ ЕКВІВАЛЕНТНОСТІ в математиці - бінарне відношення, яке є рефлексивне, симетричне і транзитивне.

Формально, для деякого бінарного відношення RM:

  1. aRa для всіх aM (рефлексивність)
  2. Якщо aRb, то bRa для a,b∈M (симетричність)
  3. Якщо aRb і bRc, то aRc для a,b,c∈M (транзитивність)

Приклади:

  1. Відношення рівності на будь-якій множині M є відношенням еквівалентності.
  2. Відношення рівнопотужності множин є еквівалентністю.
  3. Відношення "мають однакову остачу при діленні на k" або конгруентність за модулем k, яке є відношенням еквівалентності на множині N натуральних чисел для будь-якого фіксованого k∈N. Відношення конгруентності за модулем k часто позначають a ≡ b (mod k). Цьому відношенню належать, наприклад, пари натуральних чисел (17,22), (1221,6), (42,57) для k=5, тобто 17 ≡ 22(mod 5), 1221 ≡ 6 (mod 5), 42 ≡ 57 (mod 5).

[ред.] Фактормножина та класи еквівалентності

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

Нехай тепер на множині M задано відношення еквівалентності R. Виконаємо таку побудову. Виберемо деякий елемент a∈M і утворимо підмножину SaR = {x| x∈M і aRx}, яка складається з усіх елементів множини M, еквівалентних елементу a. Візьмемо другий елемент b∈M такий, що b∉SaR і утворимо множину SbR = {x | x∈M і bRx } з елементів еквівалентних b і т.д. Таким чином одержимо сукупність множин (можливо, нескінченну) {SaR, SbR,...}.

Побудована сукупність множин { SiR | i∈I} називається фактор-множиною множини M за еквівалентністю R і позначається M/R.

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

Класи SiR називають класами еквівалентності за відношенням R. Клас еквівалентності, який містить елемент a∈M часто позначають через [a]R.

Потужність фактор-множини |M/R| називається індексом розбиття або індексом відношення еквівалентності R.