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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Відно́шення еквівале́нтності (\sim) на множині X — це бінарне відношення для якого виконуються наступні умови:

  1. Рефлексивність: \,a \sim a для будь-якого a в X,
  2. Симетричність: якщо \,a \sim b, то \,b \sim a,
  3. Транзитивність: якщо \,a \sim b та \,b \sim c, то \,a \sim c.

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

Пов'язані визначення[ред.ред. код]

  • Класом еквівалентності C(a) елемента a називається підмножина елементів, еквівалентних a. З зазначеного визначення випливає що, якщо b \in C(a), то C(a) = C(b).

Множина всіх класів еквівалентності позначається X/{\sim}.

  • Для класу еквівалентності елемента a використовується наступне позначення: [a], a / {\sim}, \overline{a}.
  • Множина класів еквівалентності по відношенню \sim є розбиттям множини.


Приклади відношень еквівалентності[ред.ред. код]

Факторизація відображень[ред.ред. код]

Множина класів еквівалентності, яка відповідає відношенню еквівалентності \sim, позначається символом X/{\sim} і називається фактормножиною відносно \sim. При цьому сюр'єктивне відображення

p\colon x \mapsto C_x

називається дійсним відображенням (чи канонічною проекцією) X на фактормножену X/{\sim}.

Нехай X, Y — множини, f\colon X \to Y — відображення, тоді бінарне відношення x \, {R_f} \,y визначене правилом

x \mathop{R_f} y \iff f(x) = f(y), \quad x, y \in X

є відношенням еквівалентності на X. При цьому відображення утворює відображення \overline{f}\colon X/R_f \to Y, яке визначається правилом

\overline{f}(C_x) = f(x)

чи

(\overline{f}\circ p)(x) = f(x).

При цьому отримується факторизація відображення f на сюр'єктивне відображення p та ін'ективне відображення \overline{f}.

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

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

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

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

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

Сукупність множин {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.

Див. також[ред.ред. код]

Джерела[ред.ред. код]

  • А. И. Кострикин, Введение в алгебру. М.: Наука, 1977, 47—51.
  • А. И. Мальцев, Алгебраические системы, М.: Наука, 1970, 23—30.
  • В. В. Иванов, Математический анализ. НГУ, 2009.