Релации

Множеството $R$ се нарича релация ако елементите му са наредени двойки. За всяка релация $R$ съществуват множествата
$\{X|$съществува $Y$ такова че $(X,Y)\in R\}$ и $\{Y|$ съществува $X$ такова че $(X,Y)\in R\}$, които се наричат съответно дефиниционно множество и множество от стойности на $R$ и се означават с $\text{dom }R$ и $\text{ran }R$, съответно. Често вместо $(x,y)\in R$ пишем $xRy$ и казваме, че $x$ и $y$ са в релацията $R$. Релациите определят връзки между елементите на две множества. Ако $M$ е множество и $R\subset M\times M$, казваме че $R$ е релация в множеството $M$.
За всяко множество $M$ и релация $R$ съществуват множествата $\{y\in\text{ran }R|$ съществува $x\in M$, такова че $xRy\}$ и $\{x\in\text{dom }R|$ съществува $y\in M$, такова че $xRy\}$, които се наричат съответно образ и прообраз на $M$, при релацията $R$ и се означават съответно с $R(M)$ и $R^{-1}(M)$. За всяка релация $R$, съществува множеството $\{(x,y)|(y,x)\in R\}$, което се нарича обратна релация на $R$ и се означава с $R^{-1}$. За всеки две релации $R$ и $S$, съществува множеството $\{(x,y)|$съществува $z$, такова че $xRz$ и $zSy\}$, което очевидно е релация, която се нарича композиция на $R$ и $S$ и се означава с $S\circ R$. Така, по определение $(x,y)\in S\circ R$, тогава и само тогава, когато съществува $z$, такова че $xRz$ и $zSy$.

Упражнения

2.1. Нека $A$ и $B$ са множества, и $R$ е релация. Докажете, че \newline a) $R(A\cup B)=R(A)\cup R(B)$, б) $R(A\cap B)\subset R(A)\cap R(B)$, в) $R(A\setminus B)\subset R(A)\setminus R(B)$.
2.2. Проверете, че образът на всяко множество $A$ при релацията $R^{-1}$ съвпада с прообраза на $A$ при релацията $R$.
2.3. Покажете, че ако $R,S,T$ са релации, то $(R\circ S)\circ T=R\circ (S\circ T)$ и $S\circ R\neq R\circ S$.

Релации на наредба

Казваме, че релацията $R$ e
a) рефлексивна, ако $aRa$ за всички $a$,
б) симетрична, ако за всички $a,b$ от $aRb$ следва $bRa$,
в) транзитивна, ако за всички $a,b,c$ от $aRb$ и $bRc$ следва $aRc$
г) антисиметрична, ако за всички $a,b\in A$, от $aRb$ и $bRa$ следва $a=b$.
д) асиметрична, ако за всички $a,b\in A$, от $(a,b)\in R$ следва $(b,a)\notin R$

Всяка релация $R$ в $A$, която е рефлексивна, антисиметрична и транзитивна, се нарича релация на частична наредба в множеството $A$, а наредената двойка $(A,R)$ се нарича частично наредено множество. Често използвано означение за частична наредба в множество $A$ е $\leq_A$, при което ако $a,b\in A$ и $a\leq_A b$, казваме, че $a$ e по-малко или равно на $b$, или че $a$ не надминава $b$. Обратната релация на $\leq_A$ означаваме с $\geq_A$. Ясно е тогава, че $a\leq_A b$, точно когато $b\geq_Aa$ и в последния случай казваме, че $b$ е по-голямо или равно на $a$.

Всяка асиметрична и транзитивна релация $R$ в множество $A$ се нарича строга частична наредба в $A$, а двойката $(A,R)$ се нарича строго частично наредено множество. Означението за строга частична наредба в $A$ е $<_A$, при което, ако $a<_A b$, казваме, че $a$ е строго по-малко от $b$. Обратната релация на $<_A$ означаваме с $>_A$, при което е ясно, че $a<_Ab$, точно когато $b>_Aa$ и в последния случай казваме, че $b$ е строго по-голямо от $a$.

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

Нека $A$ е множество с частична или строга частична наредба $R$, $a\in A$ и $b\in A$. Казваме, че елементите $a$ и $b$ са сравними, ако $aRb$ или $bRa$. Казваме, че $a$ и $b$ са несравними, ако не са сравними. Казваме, че наредбата $R$ е пълна (линейна) наредба, ако всеки два елемента на $A$ са сравними. Ако $R$ е пълна наредба в $A$, наредената двойка $(A,R)$ се нарича напълно (линейно) наредено множество.

Нека $A$ множество, $R$ e частична наредба в $A$ и $B\subset A$. Казваме, че елементът $b\in B$ е
a) най-малък (най-голям) елемент на $B$ в наредбата $R$, ако $bRx$ ($xRb$) за всеки елемент $x\in B$.
б) минимален (максимален) елемент на $B$ в наредбата $R$, ако не съществува $x\in B$, такъв че $xRb$ ($bRx$) и $x\neq b$.

Забележка. Разликата между най-малък (най-голям) и минимален (максимален) елемент на $B$, е, че най-малкият (най-големият) елемент е сравним със всеки елемент на $B$ и е единствен, докато един минимален (максимален) елемент може да не е сравним с някои елементи и не е длъжен да бъде единствен. В случай, че $R$ е пълна наредба двете понятия съвпадат.

Нека $(A,\leq_A)$ е частично наредено множество и $B\subset A$. Казваме, че елементът $a\in A$ е долна (горна) граница на $B$, ако $a\leq_A x$ ($x\leq_A a$) за всяко $x\in B$. Казваме, че $B$ е ограничено отдолу (отгоре), ако има долна (горна) граница. Казваме, че $B$ е ограничено, ако е ограничено отгоре и отдолу. Казваме, че $a$ е точна долна (точна горна) граница на $B$, ако $a$ е най-големият (най-малкият) елемент на множеството от всички долни (горни) граници на $B$, който се нарича инфимум (супремум) на $B$ и се означава с $\inf B$ ($\sup B$). Да забележим, че ако $a$ е долна (горна) граница на $B$, то всеки елемент $b\in A$, такъв че $b\leq_A a$ ($a\leq_A b$) е долна (горна) граница на $B$, така че, ако съществува, инфимумът (супремумът) е най-голямата (най-малката) от всички долни (горни) граници на $B$.

Забележка. Разликата между инфимум (супремум) на $B$ и най-малък (най-голям) елемент на $B$, е, че инфимумът (супремумът), не е длъжен да е елемент на $B$, така че той може да съществува, без множеството да има най-малък (най-голям) елемент.
Ако $B$ е линейно наредено множество, най-малкият (най големият) елемент на $B$ (когато съществува), означаваме с $\min B$ ($\max B$).

Пример. Множеството $\mathbb{N}$ е ограничено отдолу и $\emptyset$ е негова долна граница, която е и най-малкият елемент.

Упражнения

2.1. Нека $A$ е множество. Проверете, че релацията $$\{(x,y)\in A\times A|x\subset y\},$$ която означаваме с $\subset_A$, е частична наредба в множеството $A$.
2.2. Нека $R$ е релация в множеството $A$. Докажете, че
а) ако $R$ е частична наредба в $A$, то релацията $S_R=\{(x,y)\in A\times A|xRy$ и $x\neq y\}$ е строга частична наредба в $A$,
б) ако $S$ е строга частична наредба в $A$, то релацията $R_S=\{(x,y)\in A\times A|xSy$ или $x=y\}$ е частична наредба в $A$.
в) Ако $\rho$ и $\sigma$ са съответно частична и строга частична наредба в $A$, то $R_{S_{\rho}}=\rho$ и $S_{R_{\sigma}}=\sigma$.
2.3. Нека $(A,\leq_A)$ е наредено множество и $B\subset A$. Покажете, че
a) ако $a\in B$ е най-малък (най-голям) елемент на множеството $B$, то $a=\inf B$ ($a=\sup B$).
б) ако $a=\inf B$ ($a=\sup B$) и $a\in B$, то $a$ е най-малък (най-голям) елемент на $B$ (по отношение на $\leq_A$).
в) $a\in B$ е точна долна (горна) граница на $B$ тогава и само тогава, когато $a$ е долна (горна) граница на $B$ и ако $b$ e долна (горна) граница на $B$, то $b\leq_A a$ ($a\leq_A b$).
2.4. Нека $(A,<_A)$ и $(B,<_B)$ са строго частично наредени множества и $A\cap B=\emptyset$. Проверете, че ако $<=<_A\cup<_B\cup A\times B$, то $(A\cup B,<)$ е строго частично наредено множество.
Забележка. Така определената наредба на $A\cup B$ съвпада с наредбата $<_A$ върху $A$ и с $<_B$ върху $B$, и относно нея всеки елемент на $A$ е по-малък от всеки елемент на $B$.
2.5. Нека $A$ е непразно множество и $\mathcal S\subset\mathcal P(A)$. Покажете, че а) $\sup\mathcal S=\cup\mathcal S$, б) $\inf\mathcal S=\cap\mathcal S$.

Наредба в множеството на естествените числа

Като конкретен пример на множество с наредба ще разгледаме множеството на естествените числа.

Твърдение 2.1. Mножеството $\{(x,y)\in\mathbb{N}\times\mathbb{N}|x\in y\}$ е релация на строга линейна наредба в $\mathbb{N}$. Тази наредба ще означаваме с $<_{\mathbb{N}}$, а когато това не предизвиква объркване с $<$.
Доказателство. Ясно е, че посоченото множество е релация в $\mathbb{N}$. Ако $x\in y$ и $y\in z$, тъй като $z$ е транзитивно (Твърдение 1.3), имаме $y\subset z$. Следователно $x\in y\subset z$, откъдето $x\in z$. Следователно релацията е транзитивна. Ако $x\in y$ и допуснем, че $y\in x$, тъй като $x,y$ са транзитивни имаме $x\subset y$ и $y\subset x$. Следователно $y=x$, откъдето $x\in x$, което е противоречие с Твърдение 1.5 б). Следователно $x\in y$ и $y\in x$ не са изпълнени едновременно, което показва, че релацията е асиметрична. Следователно тя е строга наредба в $\mathbb{N}$. Остава да се покаже, че тази наредба е пълна. Ще приложим метода за доказване по индукция. Нека $P(X)$ е твърдението “за всяко $m\in\mathbb{N}$, $m\in X$ или $m=X$, или $X\in m$“. За да покажем верността на $P(\emptyset)$, достатъчно е да докажем, че за всяко $m\in\mathbb{N}$, $\emptyset\in m$, или $\emptyset=m$ ($m\in \emptyset$ не е изпълнено за никое $m$). За целта ще покажем, че $M=\{m\in\mathbb{N}|\emptyset=m $ или $\emptyset\in m\}$ е индуктивно множество и следователно съгласно принципа на индукцията съвпада с $\mathbb{N}$. Ясно е, че $\emptyset\in M$. Ако $k\in M$, то $\emptyset\in k$ или $\emptyset=k$. Следователно $\emptyset\in k\cup\{k\}$, което показва, че $k\cup\{k\}\in M$. Следователно $M=\mathbb{N}$, което показва, че $P(\emptyset)$ е вярно. Нека $k\in\mathbb{N}$ и е вярно $P(k)$. Тогава за всяко $m\in\mathbb{N}$, $m\in k$ или $m=k$, или $k\in m$. Ако $m\in k$ или $m=k$, то $m\in k\subset k\cup\{k\}$ или $m=k\in k\cup\{k\}$ съответно, т. е. $m\in k\cup\{k\}$. Ако $k\in m$, от Твърдение 5.1 а) имаме $k\cup\{k\}\in m\cup\{m\}$, откъдето $k\cup\{k\}\in m$ или $k\cup\{k\}=m$. Следователно е вярно $P(k\cup\{k\})$, откъдето $P(n)$ е вярно за всяко $n\in\mathbb{N}$. Оттук получаваме, че ако $m, n\in\mathbb{N}$ и $n\neq m$, то $m\in n$ или $n\in m$, което искахме да докажем.

В Твърдение 1.4 доказахме, че всяко естествено число е множество, което е подмножество на $\mathbb{N}$. Сега ще докажем, че при така въведената релация на наредба, всяко естествено число е множество, чиито елементи са всички по-малки от него естествени числа.

Твърдение 2.2. За всяко $n\in\mathbb{N}$ е вярно $n=\{x\in\mathbb{N}|x<_{\mathbb{N}} n\}$.
Доказателство. Нека $A=\{x\in\mathbb{N}|x<_{\mathbb{N}} n\}$ и $x\in n$. Тогава $x<_{\mathbb{N}} n$, т. е. $x\in n$ и тъй като $n$ е транзитивно получаваме $x\subset n$. Следователно $n\subset A$. Нека $x\in A$. Тогава $x<_{\mathbb{N}} n$, т. е. $x\in n$, откъдето $A\subset n$. Следователно $n=A$.

В следващите твърдения ще разгледаме свойства на естествените числа свързани с наредбата.
Първо ще се убедим, че всяко непразно множество от естествени числа има най-малък елемент.

Твърдение 2.3. Нека $A\subset\mathbb{N}$ и $A\neq\emptyset$. Тогава съществува $\min A$.
Доказателство. Нека допуснем противното и нека $B=\{n\in\mathbb{N}|{k\in\mathbb{N}|k\leq n}\subset\mathbb{N}\setminus A\}$. Тогава $0\in B$, иначе $0\in A$, при което $\min A=0$ – противоречие. Нека $p\in B$, тогава за всяко естествено $k\leq p$ е вярно $k\notin A$. Ако $p\cup\{ p\}\in A$, то $\min A=p\cup\{p\}$ – противоречие. Следователно $p\cup\{p\}\notin A$, откъдето $p\cup\{p\}\in B$. От принципа на индукцията получаваме $B=\mathbb{N}$. Следователно за всяко $n\in\mathbb{N}$ е вярно $n\notin A$, т. е. $A=\emptyset$, което е противоречие.

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

Твърдение 2.4. Нека $A\subset\mathbb{N}$, $A\neq\emptyset$ и $A$ е ограничено отгоре. Тогава съществува $\max A$.
Доказателство.
Нека $B=\{n\in\mathbb{N}|n$ е горна граница на $A\}$. Тогава $B\neq\emptyset$, тъй като $B$ е ограничено отгоре. Съгласно Твърдение 2.3 съществува $\min B$. Трябва да покажем, че $\min B\in A$. Ако $\min B=0$, то $A={0}$ (иначе $A=\emptyset$) и следователно $\min B\in A$. Ако $\min B\neq 0$, съгласно Твърдение 1.2 съществува $n\in\mathbb{N}$, за което $\min B=n\cup{n}$. Ако $\min B\notin A$, то $n$ е горна граница на $A$, т. е. $n\in B$ и $n<\min B$, което е противоречие. Следователно $\min B\in A$ и $\max A=\min B$.

Релации на еквивалентност. Разбивания на множества

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

Релацията $R$ се нарича релация на еквивалентност, ако е рефлексивна, симетрична и транзитивна. Ако $R$ е релация на еквивалентост и $aRb$, казваме, че $a$ и $b$ са еквивалентни (по отношение на $R$, или по модул $R$). Нека $E$ е релация на еквивалентност в множество $A$ и $a\in A$. Множеството $\{x\in A|(a,x)\in E\}$ се нарича клас на еквивалентност по модул $E$ и се означава с $[a]_E$ или $[a]$. Елементът $a$ се нарича представител на класа на еквивалентност $[a]$.

Твърдение 2.5. Нека $A\neq\emptyset$ и $E\subset A\times A$ е релация на еквивалентност. Тогава
a) $(x,y)\in E$ тогава и само тогава когато $[x]=[y]$,
б) $(x,y)\notin E$, тогава и само тогава, когато $[x]\cap [y]=\emptyset$.
Забележка. Оттук виждаме, че два класа на еквивалентост или съвпадат, или не се пресичат. При това представителите на съвпадащите класове са еквивалентни и еквивалентните елементи са представители на едни и същи класове на еквивалентост. Нееквивалентните елементи определят различни класове на еквивалентност и представителите на различни класове са нееквивалентни.
Доказателство.
a) Нека $(x,y)\in E$ и $t\in [x]$. Тогава $(t,x)\in E$ и от транзитивността на $E$ имаме $(t,y)\in E$, т. е. $t\in [y]$. Следователно $[x]\subset[y]$. Аналогично $[y]\subset[x]$, откъдето $[x]=[y]$. Обратно, ако $[x]=[y]$ и $t\in [x]$, то $(t,x)\in E$, $(t,y)\in E$ и тъй като $E$ е симетрична и транзитивна, получаваме $(x,y)\in E$.
б) Нека $(x,y)\notin E$ и да допуснем, че $t\in [x]\cap [y]$. Тогава $(t,x)\in E$ и $(t,y)\in E$, откъдето $(x,y)\in E$, което е противоречие. Обратно, нека $[x]\cap[y]=\emptyset$ и да допуснем, че $(x,y)\in E$. Тогава от a) имаме $[x]=[y]$, което е противоречие.

Казваме, че множеството $S$ е разбиване на множеството $A\neq\emptyset$, ако
1) $S\neq\emptyset$,
2) ако $X\in S$, то $X\neq\emptyset$,
3) ако $X\in S$, $Y\in S$ и $X\neq Y$, то $X\cap Y=\emptyset$,
4) $\cup S=A$.

Твърдение 2.6. Нека $E$ е релация на еквивалентност в множеството $A$ и $S$ е разбиване на $A$. Тогава
a) съществува множеството $\{[a]_E|a\in A\}$, което се нарича фактормножество на $A$ по $E$ (факторизация на $A$ по $E$) и се означава с $A/E$.
б) $A/E$ е разбиване на $A$. Казваме че $A/E$ е разбиване на $A$, получено чрез факторизиране на $A$ по $E$.
в) множеството $E_S=\{(x,y)\in A\times A|$ съществува $C\in S$, такова че $x\in C$ и $y\in C\}$ е релация на еквивалентност в $A$,
г) ако $S=A/E$, то $E_S=E$
д) $A/E_S=S$.
Забележка. Оттук виждаме, че всяка релация на еквивалентност в дадено множество определя разбиване на множеството (чрез факторизиране по нея), и всяко разбиване на множеството определя релация на еквивалентност в това множество (два елемента са еквивалентни, ако принадлежат на един елемент от разбиването). При това релацията на еквивалелнтост, съответстваща на фактормножество, съвпада с релацията, по която се факторизира, и факторизацията на множество по релация на еквивалентност, съответстваща на дадено разбиване на множеството, съвпада със самото разбиване.
Доказателство. a) По определение $A/E\subset\mathcal{P}(A)$,
б) Ще проверим, че $A/E$ удовлетворява определението за разбиване.
1) $A/E\neq\emptyset$, щом $A\neq\emptyset$.
2) Aко $X\in A/E$, то съществува $a\in A$, за което $X=[a]\neq\emptyset$.
3) Ако $X,Y\in A/E$ и $X\neq Y$, то съществуват $a,b\in A$, за които $X=[a]$, $Y=[b]$ и $(a,b)\notin E$, иначе от Твърдение 2.5 а) бихме имали $X=[a]=[b]=Y$, което е противоречие. Тогава от Твърдение 2.5 б) получаваме $X\cap Y=\emptyset$.
4) Имаме, че $x\in\cup (A/E)$, точно когато съществува $y\in A/E$, за което $x\in y$ (вж. Аксиома 5). От друга страна $y\in A/E$, точно когато съществува $a\in A$, за което $y=[a]$. Тогава $x\in y$, точно когато $(x,a)\in E$, откъдето $x\in A$. Следователно $\cup (A/E)\subset A$. От друга страна, ако $x\in A$, то $x\in[x]\in A/E$, откъдето $x\in \cup (A/E)$. Следователно $A\subset A/E$. От Аксиома 2 получаваме $A=\cup (A/E)$. Следователно $A/E$ е разбиване на $A$.
в) Тъй като $\cup S=A$, за всяко $a\in A$, съществува $C\in S$, такова че $x\in C$. Следователно $(x,x)\in E_S$, т. е. релацията $E_S$ е рефлексивна. Ясно е, че ако $(x,y)\in E_S$, то $(y,x)\in E_S$, т. е. релацията $E_S$ е симетрична. Нека $(x,y)\in E_S$ и $(y,z)\in E_S$. Тогава съществуват $C, D\in S$, такива че $x\in C$, $y\in C$, $y\in D$, $z\in D$. Тъй като $S$ е разбиване имаме $C=D$ (иначе $C\cap D=\emptyset$, което е противоречие с $y\in C\cap D$). Следователно $x,z\in C$, откъдето $(x,z)\in E_S$, т. е. $E_S$ е транзитивна. Следователно $E_S$ е релация на еквивалентност.
г) Нека $S=A/E$ и $(x,y)\in E_S$. Тогава съществува $C\in S$, за което $x\in C$, $y\in C$, т. е. съществува $a\in A$, за което $C=[a]$ и $(x,a)\in E$ и $(y,a)\in E$. От симетричността и транзитивността на $E$ имаме $(x,y)\in E$, което показва, че $E_S\subset E$. Нека $(x,y)\in E$. Тогава $x\in A$, $[x]\in S$, $x\in[x]$ и $y\in[x]$. Следователно $(x,y)\in E_S$, откъдето $E\subset E_S$. И тъй $E_S=E$.
д) Нека $x\in A/E_S$. Тогава съществува $a\in A$, такова че $x=[a]_{E_S}$. Тъй като $S$ е разбиване на $A$, съществува $C\in S$, за което $a\in C$. От друга страна, ако $y\in x$, то $(a,y)\in E_S$, т. е. съществува $D\in S$, за което $a\in D$, $y\in D$. Тъй като $S$ е разбиване имаме $C=D$ (в противен случай $C\cap D=\emptyset$, което е противоречие с $a\in C\cap D$). Следователно $y\in C$, т. е. $x\subset C$. Нека сега $t\in C$. Тогава $(a,t)\in E_S$ т. е. $t\in [a]_{E_S}=x$, откъдето $C\subset x$. Следователно $x=C\in S$, откъдето $A/E_S\subset S$. Обратно, нека $x\in S$ и да докажем, че $x\in A/E_S$. Тъй като $x\neq\emptyset$, съществува $a\in A$, такова че $a\in x$. От друга страна, за всяко $y\in x$ имаме $(a,y)\in E_S$, т. е. $y\in[a]_{E_S}$, което показва, че $x\subset [a]_{E_S}$. Нека сега $t\in [a]_{E_S}$. Тогава $(a,t)\in E_S$, т. е. съществува $s\in S$, за което $a\in s$ и $t\in s$. Тъй като $S$ е разбиване на $A$ имаме, че $s=x$ (иначе $s\cap x=\emptyset$, което е противоречие с $a\in s\cap x$). Следователно $t\in s=x$, т. е, откъдето $[a]_{E_S}\subset x$. Следователно $x=[a]_{E_S}\in A/E_S$.

назад