Релации

Релацията е математическото съответствие на обикновеното понятие „връзка“. В обикновения живот например Моника е във връзка с Яна, и по-точно това е връзката „майка – дъщеря“. Друга такава връзка е „държава – столица на тази държава“. Като пример можем да вземем Египет – Кайро.

Още примери за релации

Нека вземем още примери. В увода споменахме релациите (връзките) „да бъдеш майка на дъщеря си“ и „да бъдеш столица на държава“. Ето още една: „да бъдеш четно число“. В тази релация са числата 2, 4, 8, 18, 58, 66 и много други. Числата 1, 3, −7, 19 не са в релацията „да бъдеш четно число“. Релация от обикновения свят може да бъде „да бъдеш мъж“. Адам, Мирослав, Лукаш или Мартин са в релацията „да бъдеш мъж“.

Друг пример е релацията „по-малко от“. Например числото три е „по-малко от“ числото пет. Математически можем да го запишем като 3<5. Или релацията равенство: числото три „е равно на“ числото три, математически: 3 = 3.

Можем да имаме и по-сложни примери: „бащата и майката са родители на детето“. В тази релация има тройка хора: бащата Даниел, майката Мария и детето Красимира. В математиката можем да измислим релация с три елемента така: сборът на първите две числа е равен на третото число. Например тези числа, в този ред, са в тази релация: 3, 4, 7, защото 3 + 4 = 7. Тези числа не са в релацията: 3, 5, 12, защото 3 + 5 ≠ 12.

Арност на релация

Арността е странно звучащ термин, който обаче просто показва колко елемента имаме в релацията. В предишните примери работихме с различен брой елементи. При релацията „да бъдеш мъж“ ни стигна един елемент, можем да кажем: „Иван е мъж“. Достатъчно ни е едно име, един елемент. За такава релация казваме, че е унарна.

В следващия пример имахме релацията „по-малко от“. Тя работеше с две числа, с два елемента. Казахме, че числото три е по-малко от пет. Използвахме два елемента, затова релацията е бинарна.

В последния пример използвахме общо три елемента: сборът на две числа трябваше да е равен на третото. Имахме числа a, b, c и трябваше да е изпълнено a + b = c. Тази релация е тернарна.

За по-високи арности можем да използваме означението n-арна релация. Можем да го използваме и за по-ниски арности: бинарната релация можем да запишем като 2-арна релация. Елементите на релацията тогава записваме като наредени n-торки. Ако имаме бинарна релация, ги записваме като двойки, обикновено в кръгли или в квадратни скоби. Така, ако искаме да запишем, че числата три и пет са в релацията „по-малко от“, трябва да запишем числата като двойка: (3; 5), или [3; 5]. Внимавай за реда, защото в обратен ред не би било вярно: (3; 5) ≠ (5; 3) – петицата не е по-малка от тройката.

Семеен пример

Преди да преминем към математическите определения, ще разгледаме още един типичен пример със семейство. Нека имаме тези членове на едно семейство:

• Максим: дядо по бащина линия;
• Георги: баща;
• Десислава: майка;
• Сандра: дъщеря;
• Иван: син.

Първо ще потърсим всички членове на семейството, които отговарят на релацията „да бъдеш мъж“. Това е 1-арна, тоест унарна, релация. В релацията винаги ще има само един елемент, един член на семейството. Сега трябва да изброим всички членове на семейството от мъжки пол. Редът засега няма значение. Релацията „да бъдеш мъж“ съдържа тези елементи: {[Максим], [Георги], [Иван]}. Обърни внимание, че макар да е унарна релация, използвахме квадратни скоби. Не е задължително, записът би бил четим и без тях, но за последователност съм оставил скобите. Съвкупността от всички елементи на релацията е обикновено множество, затова са тези фигурни скоби.

Сега ще потърсим всички двойки на релацията „баща – син“. Още от пръв поглед се вижда, че това е бинарна релация – в резултата ще има наредени двойки елементи. Полученото множество изглежда така: {(Георги; Иван), (Максим; Георги)}. Бащата Георги е баща на сина Иван, а дядо Максим е баща на бащата Георги. Обърни внимание, че редът наистина има значение: Георги се среща два пъти, но веднъж на първо място в ролята на баща, а втория път на второ място в ролята на син.

Ще опитаме още една релация: „родител – дете“. Тук ще има повече двойки, защото на първо място може да бъде който и да е родител, както бащата, така и майката, а на второ място може да бъде което и да е дете, както синът, така и дъщерята. Трябва да вземем предвид и че дядо Максим е родител на Георги, но не е родител на Десислава. Георги и Десислава обаче са и двамата родители на Сандра и Иван. Сандра и Иван не са родители на никого, защото са само на деветнайсет и тринайсет години. Накрая ще получим тези наредени двойки: {(Максим; Георги), (Георги; Сандра), (Георги; Иван), (Десислава; Сандра), (Десислава; Иван)}. Обърни внимание, че Георги и Десислава се срещат по два пъти – веднъж като родители на дъщерята Сандра и втори път като родители на Иван.

И последен капан при бинарните релации. Нека имаме релацията „брат или сестра – брат или сестра“. Тук трябва да си дадем сметка, че при релациите редът има значение, така че ако в резултата на тази релация запишем само „Сандра – Иван“, това би било грешно, защото това е съвсем различна наредена двойка от „Иван – Сандра“. Затова правилният резултат е: {(Сандра; Иван), (Иван; Сандра)}.

И още един съвсем кратък пример за тернарна релация: запиши всички наредени тройки на тази релация: „дядо – баща – дете“. В условието имаме само един дядо и един баща, но две деца. Не е достатъчно да запишем само варианта със Сандра или с Иван, трябва да изброим и двамата. Друго би било, ако накрая вместо „дете“ беше посочен „син“. Правилният резултат е: {(Максим; Георги; Сандра), (Максим; Георги; Иван)}.

Определение на унарна релация

Ще разгледаме най-простите релации, унарните. Под унарна релация разбираме някакво множество от елементи. Множеството {2, 3} може да представя някаква релация. Например релацията „да бъдеш просто число, по-малко от пет“ или „да бъдеш нетривиален делител на числото шест“, според това как я тълкуваме.

По-наблюдателните читатели са забелязали, че втората релация е определена малко странно. Тя казва, че релацията трябва да съдържа нетривиалните делители на числото шест, а в полученото множество имаме числата 2 и 3. Не ни ли липсват някои? Числата 1 и 6 са тривиални делители, те не ни интересуват. Но трябва да има и отрицателни числа, тоест −2 и −3. Множеството на всички нетривиални делители на числото 6 изглежда така: {−3, −2, 2, 3}.

Подобно на функциите, при които задаваме дефиниционно множество, и при релацията задаваме носещо множество – множеството, от което избираме елементите на релацията. В предишните примери например зададохме семейство, в което имаше дядо Максим и т.н. Не избирахме бащи и деца от всички семейства по света. Ако за носещо множество зададем множеството на естествените числа, релацията ни ще е наред.

Вече можем да преминем към определението на релация. Ако носещото множество са естествените числа, какви елементи може да съдържа унарната ни релация? Пак само естествени числа. Или всички, или само някаква част от тях. Можем да кажем, че дадената релация ще бъде подмножество на множеството на естествените числа. По-общо, ако имаме унарна релация R и носещо множество M, е изпълнено R ⊆ M, релацията R е подмножество на множеството M.

Определение на бинарна релация

Как ще изглежда това при бинарна релация? При бинарната релация елементите на релацията R са наредени двойки. Всеки елемент на двойката може да е от различно множество. Можем да имаме релацията „родител – брой деца“. Родителят ще се избира от множеството на хората, например в Европа, а броят на децата ще се избира от множеството на естествените числа плюс нулата.

Как от две множества получаваме множеството на всички възможни двойки? С декартово произведение. Ако имаме множествата A = {a, b, c}, B = {1, 2}, чрез декартовото произведение получаваме:

$$A\times B=\{(a;1),(a;2),(b;1),(b;2),(c;1),(c;2)\}$$

Това е множеството на всички възможни двойки, които можем да получим така, че на първо място да е елемент от множеството A, а на второ място – елемент от множеството B. Тоест ако имаме бинарна релация R между множествата A и B, можем да определим тази релация като R ⊆ A × B.

Ако запазим предишните множества A и B и определим релацията R между тях така: „буква – пореден номер на буквата в азбуката“, тази релация ще изглежда така: R = {(a; 1), (b; 2)}. Буквата c вече няма да е там, защото в декартовото произведение A × B няма двойка (c; 3).

Определение на n-арна релация

Накрая ще определим общата n-арна релация R между множествата M₁, M₂, …, M_n:

$$R\subseteq M_1\times M_2\times \dots \times M_n$$

Релацията е подмножество на наредените n-торки. Пример за бинарна релация е релацията „по-малко от“, тоест <. Можем да я определим между някакви числови множества, например между естествените числа. Тогава релацията ще изглежда така:

$$<\subseteq \mathbb{N}\times \mathbb{N}$$

(Не се плаши, че знакът < стои толкова странно отляво. Това е само името на релацията. Там отново можеше да бъде R, като R представя релацията „по-малко от“.)

Конкретно релацията би изглеждала така:

$$\begin{array}{rcl}<=& & (1;2),(1;3),(1;4),(1;5),\dots \\ & & (2;3),(2;4),(2;5),(2;6),\dots \\ & & (3;4),(3;5),(3;6),(3;7),\dots \\ & & (4;5),(4;6),(4;7),(4;8),\dots \\ & & \dots \\ & & \end{array}$$

Това е множеството на наредените двойки, за които естественото число на първо място е по-малко от естественото число на второ място.

Запис на релации

Релациите обикновено именуваме с главни букви R, S и т.н. или с установени символи: <, ⊆, = и т.н. От предишните определения се вижда, че релацията всъщност е множество. Впрочем почти всичко в математиката всъщност е множество :-). Затова, ако искаме да кажем, че елементът r принадлежи на релацията R, можем да го запишем като r ∈ R.

Например можем да запишем (1; 3) ∈ < и това означава, че двойката числа едно и три принадлежи на релацията „по-малко от“. При бинарните релации често се среща по-приятен запис, който познаваш още от началното училище. Вместо да използваме оператора за принадлежност ∈, просто пишем 1 < 3. Подобно, обикновено не пишем (5; 5) ∈ =, а пишем 5 = 5.