Релация на еквивалентност

Релацията на еквивалентност е бинарна релация върху множество, която е рефлексивна, симетрична и транзитивна.

Мотивация

Релацията на еквивалентност е нещо като по-мека форма на релацията равенство. Винаги можем да решим дали два елемента на множеството са еднакви, тоест дали a = b. Понякога обаче ни е удобно да разберем дали два елемента са само подобни, не непременно еднакви. С други думи – дали имат еднакво някакво съществено свойство. Например две книги можем да смятаме за подобни, ако са от един и същ жанр – или чрез еквивалентност: две книги са еквивалентни, ако са от един и същ жанр.

Какво бихме очаквали от такава еквивалентност? Нека вземем друг пример. Две думи са подобни/еквивалентни, ако са еднакво дълги.

Вероятно бихме очаквали, че ако измерим подобието на две еднакви думи, ще получим, че са подобни. Тоест за всички думи трябва да е изпълнено, че са подобни/еквивалентни на себе си. На езика на релациите: релацията на еквивалентност трябва да е рефлексивна.

Освен това, ако думата „поток“ е подобна/еквивалентна на думата „Мария“, със сигурност очакваме и думата „Мария“ да е еквивалентна на думата „поток“. С други думи, редът няма значение. На езика на релациите: релацията на еквивалентност трябва да е симетрична.

И накрая, ако думата „лято“ е подобна/еквивалентна на думата „вода“, а думата „вода“ е еквивалентна на думата „нога“, очакваме и двойката думи „лято“ и „нога“ да са еквивалентни. Тоест релацията на еквивалентност трябва да е и транзитивна.

Нищо друго не очакваме от еквивалентността.

Примери

Още примери за еквивалентности:

• Да живееш в един и същ град. Иван със сигурност живее в същия град като Иван (рефлексивност). Ако Иван живее в същия град като Петър, то и Петър живее в същия град като Иван (симетричност). А ако Петър живее в същия град като Николай, то и Иван живее в същия град като Николай (транзитивност).
• Песни с един и същ автор. Песента „Утро“ със сигурност има същия автор като песента „Утро“ (рефлексивност). Ако песните „Утро“ и „Вечер“ имат един и същ автор, то и „Вечер“ и „Утро“ имат един и същ автор (симетричност). А ако „Вечер“ и „Нощ“ имат един и същ автор, то и „Утро“ и „Нощ“ имат един и същ автор (транзитивност).
• (a; b) ∈ R тогава и само тогава, когато a − b е четно число; a, b са цели числа. Рефлексивност: a − a = 0, нулата е четно число. Симетричност: нека c = a − b. Тогава b − a = −(a − b) = −c. Ако c е четно, трябва да е четно и −c. Транзитивност: нека p = a − b, а освен това q = b − c. Знаем, че и p, и q са четни числа. Сега трябва да докажем, че a − c е четно число. В този израз вместо c заместваме c = b − q: a − (b − q), което е равно на a − b + q. От условията знаем, че a − b е четно число. Ако към четно число прибавим още едно четно число q, отново получаваме четно число.
• Равенство. Равенството е еквивалентност и освен това е най-малката еквивалентност върху произволно множество M.

Тривиални еквивалентности

Имаме непразно множество M. Коя е най-малката възможна еквивалентност R върху множеството M? Най-малкото възможно подмножество на декартовото произведение M × M е празното множество ∅. Удовлетворява ли празното множество условията на еквивалентност?

Със сигурност е симетрично, тъй като релацията R няма елементи, условието за симетричност е изпълнено автоматично и тривиално. Подобно е и с транзитивността. Проблемът е с рефлексивността. Определението казва, че за всички елементи x на множеството M е изпълнено (x; x) ∈ R. Изпълнено ли е това? Множеството M е непразно, значи съдържа някакъв елемент, например q. Двойката (q; q) в релацията R ли е? Не е. Релацията R не е рефлексивна.

Коя е най-малката релация, която удовлетворява рефлексивността? Релацията равенство. Релацията R трябва да съдържа поне двойките (x; x) за всички елементи на M. Това е точно релацията на идентичността. Симетрична ли е такава релация? Лесно се вижда, че е. Също толкова лесно се вижда, че е и транзитивна. Най-малката релация на еквивалентност върху множеството M е релацията на идентичността, означаваме я с id_M, и тя съдържа двойките (x; x) за всички x ∈ M.

Коя е най-голямата възможна еквивалентност върху множеството M? Най-голямото подмножество е цялото множество M × M. Удовлетворява ли условията на еквивалентност? Вероятно се вижда тривиално, че да.

Клас на еквивалентност

Всяка еквивалентност разбива множеството M на система от непресичащи се множества, които наричаме класове на еквивалентност.

Нека имаме множеството на всички думи M и еквивалентността R „еднакво дълга дума“. Тоест (a; b) ∈ R тогава и само тогава, когато думите a и b имат еднаква дължина. Тази еквивалентност разбива множеството на думите на няколко по-малки множества, които винаги ще съдържат думи с еднаква дължина. Отделните класове на еквивалентност можем да различаваме с долен индекс, който същевременно ще показва дължината на думите в даденото множество:

• M₁ = {а, и, в, с, е, …}
• M₂ = {на, за, от, до, се, …}
• M₃ = {или, над, под, при, той, …}
• M₄ = {град, парк, вода, нива, …}
• …

Обърни внимание на две неща: 1) отделните множества са взаимно непресичащи се, нямат общ елемент. 2) всички елементи във всяко отделно множество са взаимно еквивалентни. Всички думи в множеството M₃ са взаимно еквивалентни, защото всички думи имат дължина три, тоест еднаква дължина, което е условието за еквивалентност.

При това всеки елемент еднозначно определя своя клас на еквивалентност. Това обикновено записваме с означението M[x], където x ∈ M. Ако напишем M[или], с това еднозначно определяме класа на еквивалентност, който вече означихме като M₃.

Как всъщност намираме класа на еквивалентност, ако знаем някое x ∈ M? Преглеждаме всички елементи в M и установяваме кои от тях са еквивалентни на елемента x. Това ще са всички елементи, които ще са част от класа на еквивалентност M[x].

За M[или] бихме прегледали всички думи в M и бихме запазили в M₃ думите, които имат дължина три.

Определение и свойства на класа на еквивалентност

Класа на еквивалентност можем да определим така. Нека имаме множество M и определена върху него еквивалентност R. Тогава класът на разбиването, който съдържа елемента x ∈ M, е:

$$M[x]=\{y\in M;(x;y)\in R\}$$

Определението казва, че това са всички y, които са еквивалентни на зададения елемент x. Тъй като релацията на еквивалентност е рефлексивна, по този начин в класа попада и самият елемент x – защото x е еквивалентен на себе си.

Разбиване на еквивалентността наричаме множеството на всички класове на еквивалентност. Така разбиването на множеството на всички думи би било множеството {M₁, M₂, M₃, …}.

Основни свойства на класовете на еквивалентност:

• (a; b) ∈ R тогава и само тогава, когато M[a] = M[b]. Ако имаме два елемента a, b, които са еквивалентни, техните класове на еквивалентност трябва да са равни.
• Обратно, ако не е изпълнено (a; b) ∈ R, то също M[a] ≠ M[b], по-точно M[a] ∩ M[b] = ∅. Ако имаме два елемента, които не са еквивалентни, техните класове на разбиването са непресичащи се.
• Обединението на всички класове на еквивалентност трябва да даде първоначалното множество M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Предишният запис е само за краен брой класове на еквивалентност, но в общия случай те могат да бъдат безброй много.)

Примери за разбивания на еквивалентност

Първи пример, нечетни и четни числа:

Нека имаме проста еквивалентност R, определена върху естествените числа N. (a; b) ∈ R тогава и само тогава, когато и a, и b са нечетни, или и a, и b са четни. Примери за елементи: (1; 7), (13; 9), (4; 6), (8; 136). Сега ще определим разбиването на тази еквивалентност на класове на еквивалентност.

Започваме последователно. На какво ще е равен класът N[1]? Трябва да намерим всички числа, които са еквивалентни на числото едно. Според условието за еквивалентност това са всички нечетни числа, така че N[1] = {1, 3, 5, 7, 9, …}.

На какво ще е равен класът N[2]? Намираме всички числа, които са еквивалентни на двойката. Това са всички четни числа: N[2] = {2, 4, 6, 8, 10, …}.

Сега N[3]. Кои числа са еквивалентни на тройката? Всички нечетни числа. Така обаче получаваме множеството N[1], което пресметнахме преди два абзаца. Подобно е и за N[4], където отново получаваме множеството на четните числа.

Виждаме, че по-нататък винаги ще се повтарят същите множества. Това се вижда и от факта, че което и друго естествено число n да вземем, ще е изпълнено n ∈ N[1] или n ∈ N[2]. Други естествени числа освен нечетните и четните нямаме, така че тези две множества образуват разбиването на еквивалентността.

Подобно е, ако си представим еквивалентност върху множество от хора – и a, и b са мъже, или и a, и b са жени. Тогава като разбиване бихме получили множеството на жените и множеството на мъжете.

Втори пример, абсолютна стойност:

Нека имаме еквивалентността R върху множеството на целите числа Z, определена така: (a; b) ∈ R тогава и само тогава, когато |a| = |b|. (Тези вертикални черти са абсолютна стойност.) Отново ще вървим последователно:

• Z[0] = {0}. Нулата е в релация само с нулата.
• Z[1] = {−1, 1}. Единицата е в релация с единицата и с минус едно, защото |1| = |−1|.
• Z[2] = {−2, 2}. Двойката е в релация с двойката и с минус две.
• Z[3] = {−3, 3}.
• …

Вероятно е ясно как ще продължи. Цялото разбиване би било множеството от класове:

$$\{\{a,-a\};a\in {\mathbb{Z}}_0^{+}\}$$

(Тоест всички двойки a, −a, където a е цяло неотрицателно число.) Виждаш, че класовете са безброй много.