Отношения на еквивалентност

Класна стая на Google

Еквивалентни изрази

Преди да продължим е важно да припомним, че следните изрази са еквивалентни

$A \equiv B (mod C)$ ‍
$A mod C = B mod C$ ‍
$C | (A - B)$ ‍ (Символът | означава "се дели на" или "е делител на")
$A = B + K \cdot C$ ‍ (където $K$ ‍ е цяло число)

Това ни позволява да преминаваме между различни начини на изразяване на една и съща идея.

Например следните са еквивалентни:

$13 \equiv 23 (mod 5)$ ‍
$13 mod 5 = 23 mod 5$ ‍
$5 | (13 - 23)$ ‍, $(5 | - 10$ ‍, което е истина, тъй като $5 \cdot (- 2) = - 10)$ ‍
$13 = 23 + K \cdot 5$ ‍. Можем да удовлетворим това с $K = - 2$ ‍: $13 = 23 + (- 2) \cdot 5$ ‍

Сравнението по модул е релация на еквивалентност

Убеди се, че "резените" от предния пример имат следните свойства:

Всяка двойка стойности в един сектор е свързана с останалите
Никога няма да намерим стойност в повече от един сектор (секторите са взаимно изключващи се)
Ако комбинираме всички сектори, ще получим диаграма, която съдържа всички стойности

Торта от резени с такива свойства притежава релация на еквивалентност.
Релацията на еквивалентност дефинира как може да "разрежем" нашата торта (как разделяме множеството) на резени (класове на еквивалентност.

Като обобщение, релациите на еквивалентност трябва да имат следните свойства:

Диаграмата: Колекция от стойностите, от които се интересуваме
Сектор от диаграмата: Клас на еквивалентност
Как разделяме диаграмата на сектори: релация на еквивалентност

По-конкретно в предния пример:

Диаграмата: Колекция от всички цели числа
Сектор от диаграмата с надпис $B$ ‍: Еквивалентен клас, в който за всички стойности е изпълнено $mod C = B$ ‍
Как разделяме диаграмата на сектори: Използваме релацията тъждествен модул C, $\equiv (mod C)$ ‍

Затова казваме, че сравнимост по модул C е релация на еквивалентност. Тя разделя целите числа на C различни класа на еквивалентност.

Защо има значение, че сравнимостта по модул C е релация на еквивалентност?

Знанието, че сравнимостта по модул C е релация на еквивалентност ни дава някои свойства, които тя трябва да притежава.
Релациите на еквивалентност имат следните свойства:

Те са рефлексивни: A е свързано с A
Те са симетрични: Ако A е свързано с B, то B е свързано с A
Те са транзитивни: Ако А е свързано с В и В е свързано с С, то А е свързано с С

Следователно сравнението по модул е релация на еквивалентност за (mod C). Това означава, че:

$A \equiv A (mod C)$ ‍
ако $A \equiv B (mod C)$ ‍, то $B \equiv A (mod C)$ ‍
ако $A \equiv B (mod C)$ ‍ и $B \equiv D (mod C)$ ‍, то $A \equiv D (mod C)$ ‍

Пример

Да приложим тези свойства към конкретен пример, като използваме

mod 5 :

$3 \equiv 3 (mod 5)$ ‍ (рефлексивно свойство)
ако $3 \equiv 8 (mod 5)$ ‍, то $8 \equiv 3 (mod 5)$ ‍ (симетрично свойство)
ако $3 \equiv 8 (mod 5)$ ‍ и ако $8 \equiv 18 (mod 5)$ ‍, то $3 \equiv 18 (mod 5)$ ‍ (транзитивно свойство)

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.