Бинарни релации върху множество

Под бинарна релация върху множество разбираме бинарна релация, определена между две еднакви множества.

Примери

Бинарната релация върху множество е специален вид бинарна релация, при която двете носещи множества са еднакви. Бинарната релация върху множество е релация R, за която R ⊆ M × M.

Релацията „по-голямо от“ е бинарна релация върху множество, защото и от двете страни работим с числа. Тоест е изпълнено > ⊆ ℝ × ℝ. Релацията „баща – брой деца“ не е бинарна релация върху множество, защото бащата избираме от множеството на всички хора, а броя на децата – от някакво числово множество.

Свойства

Бинарната релация R върху множество M може да има някои интересни свойства. Казваме, че релацията R е…

• рефлексивна, ако за всяко a ∈ M е изпълнено (a; a) ∈ R.
• симетрична, ако за всички a, b ∈ M е изпълнено, че ако (a; b) ∈ R, то и (b; a) ∈ R.
• антисиметрична, ако за всички a, b ∈ M е изпълнено, че ако (a; b) ∈ R и (b; a) ∈ R, то a = b.
• транзитивна, ако за всички a, b, c ∈ M е изпълнено, че ако (a; b) ∈ R и (b; c) ∈ R, то и (a; c) е в R.

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

Рефлексивността означава, че елементът е в релация със себе си. Типичен пример е равенството. Ако имаме определено равенство върху естествените числа, със сигурност за всеки елемент a е изпълнено a = a. Друг пример може да е делимостта. Там отново числото a се дели на себе си, тоест двойката (a; a) е в релацията делимост (седем дели седем).

Релацията „по-малко от“ обаче вече не е рефлексивна, защото не е вярно, че a < a. Това е невъзможно, седем не може да е по-малко от седем. Подобно е и с релацията „да бъдеш баща на детето си“ – не мога да бъда собствен баща. Такива релации не са рефлексивни.

Важно е, че рефлексивността трябва да е изпълнена за всички елементи, не е достатъчно да намерим само някои. Например релацията „да харесваш някого“. Мога да харесвам някого, например контрольора в автобуса, но мога да харесвам и себе си. Със сигурност има човек, който харесва себе си. Но със същата сигурност има и човек, който не харесва себе си. Тогава такава релация не е рефлексивна – всички хора би трябвало да харесват себе си.

Примери за симетричност

При симетричната релация, ако в релацията има някаква двойка, в нея е и обратната двойка. Например релацията „да бъдеш брат или сестра“. Ако Иван е брат или сестра на Яна, то и Яна е брат или сестра на Иван. От числовите релации би могла да бъде релацията „да бъдеш противоположно число“. Имам предвид двойките 2 и −2 или −7 и 7. Това са две числа, които в сбор дават нула. Тази релация е симетрична, защото редът просто няма значение: (2; −2) и (−2; 2) са пак взаимно противоположни числа и в сбор дават нула.

Релация, която не е симетрична, е „по-малко от“ (над реалните числа). Тя няма нито един симетричен елемент, защото никога не може да е изпълнено a < b и b < a. Ако 5 < 15, не може да е изпълнено 15 < 5. Не е симетрична и релацията „да бъдеш баща на сина си“. Можеш да си баща на сина си, но тогава синът не може да е баща на баща си.

Това свойство отново трябва да е изпълнено за всички случаи. Ако релацията „да харесваш някого“ (върху множеството на всички хора) трябва да е симетрична, то ако аз харесвам някоя известна певица, тя би трябвало също да харесва мен. А тъй като дори не ме познава, не мога да кажа, че ме харесва, което е жалко, и релацията не е симетрична. Което също е жалко.

Примери за антисиметричност

Класически пример за антисиметрична релация е „по-малко или равно“. Антисиметричността ни казва, че ако елементите (a; b) и (b; a) са в релацията, това е възможно само когато са равни, a = b. Релацията „по-малко или равно“ удовлетворява това условие. Кога е изпълнено a ≤ b и b ≤ a? Само ако a = b. Ако заместим: вярно ли е 3 ≤ 5 и 5 ≤ 3? Не. Но е вярно 4 ≤ 4 и 4 ≤ 4.

Пример за релация, която не е антисиметрична, може да са двойките думи с еднаква дължина, например (събота; брадва). Такава релация не е антисиметрична, защото намираме двойка думи, които са в релацията, обратният ѝ елемент също е в релацията, а двете думи са различни. Така вече споменатият елемент (събота; брадва) и обратният му: (брадва; събота). И двата очевидно са в нашата релация, но събота ≠ брадва, така че релацията не е антисиметрична.

Пример за транзитивност

Транзитивна е релацията „по-малко от“. Транзитивността ни казва, че ако 3 < 4 и 4 < 5, то със сигурност трябва да е изпълнено и 3 < 5. За много релации това е доста естествено свойство. Подобно е и в примера с еднаквата дължина на думите. Ако в релацията са (брадва; събота) и са в релацията (събота; ябълка), то в релацията са и думите (брадва; ябълка).

Транзитивна не е релацията „да бъдеш баща на сина“. Ако Тодор е баща на Стефан, а Стефан е баща на Мирослав, то Тодор не е баща на Мирослав, а е негов дядо. По същия начин не е транзитивна и релацията „да харесваш някого“. Ако аз харесвам Мария и Мария харесва своя съпруг, това не означава, че харесвам и съпруга на Мария.

Транзитивността се разглежда и при обикновените зарове. Да разгледаме релацията зарът A е по-добър от зара B, ако на зара A по-често (с по-голяма вероятност) се пада по-голямо число, отколкото на зара B. Транзитивна ли е такава релация? На това отговаря статията нетранзитивни зарове.

Еквивалентност и наредба

Някои специални видове бинарни релации имат и свои имена:

• Еквивалентност е релация, която е рефлексивна, симетрична и транзитивна.
• Наредба е релация, която е рефлексивна, антисиметрична и транзитивна.