Zdrojový kód
%\wikiskriptum{01ALG}
\xxx{Relace}
\define Nechť $M_1\cldc M_n$ jsou libovolné množiny.
Potom libovolné $\rho\sse M_1\times\cdots\times M_n$ nazveme \defined[relace]{$n$-ární relací
na $M_1\times\cdots\times M_n$} a číslo $n$ \defined[arita]{aritou} relace $\rho$.
\define
\begin{enumerate}%XX
\item Každé $R\sse M^2$ nazýváme \defined[relace!binární]{binární relace} na $M^2$.
\item $R^\1:=\set{\anglevector{a,b}}{\anglevector{b,a}\in R}$ je \defined[relace!inverzní]{inverzní relace} k~$R$.
\item $R\circ S=RS:=\set{\anglevector{a,c}}{\EE b\in M (\anglevector{a,b}\in R \Land \anglevector{b,c}\in S)}$
je \defined[součin!relací]{součin relací}.
\item $D_M=\set{\anglevector{a,a}}{a\in M}$ je \defined[diagonála]{diagonála}.
\end{enumerate}%XX
\define
\def\rEl#1#2#3#4{\anglevector{#1,#2}#3#4}
\def\rR#1#2{\rEl {#1}{#2}\in R}
Definujeme obecné vlastnosti, předpokládáme platnost výroků pro všechna $a,b,c\in M$.
Binární relace je:
\begin{enumerate}%XX
\item \defined[relace!reflexivní]{reflexivní} $\equivs \rR aa \equivs D_M\sse R$;
\item \defined[relace!transitivní]{transitivní} $\equivs \rR ab \Land \rR bc \Limpl \rR ac \equivs RR\sse R$;
\item \defined[relace!symetrická]{symetrická} $\equivs \rR ab \Lequiv \rR ba \equivs R^\1=R$;
\item \defined[relace!antisymetrická]{slabě antisymetrická}
$\equivs \rR ab \Land \rR ba \Limpl a=b \equivs R^\1\cap R\sse D_M$;
\item \defined[relace!antisymetrická]{silně antisymetrická}
$\equivs \rR ab \Limpl \rEl ba\notin R \equivs R^\1\cap R=\emptyset$;
\item \defined[relace!trichotonická]{trichotonická}
$\equivs \rEl ab\notin R \Limpl (\rR ba \Lor a=b) \equivs R^\1\cup R\cup D_M=M^2$;
\end{enumerate}%XX
\define
Rozlišujeme následující typy relací:
\begin{enumerate}%XX
\item
\defined[ekvivalence (teorie množin)]{ekvivalence} (zn. $\equiv$) je reflexivní, transitivní a symetrická.
Ekvivalence rozděluje množinu na \defined{třídy ekvivalence}.
Množina $M_{/{\equiv}}$ všech tříd ekvivalence se nazývá \defined{faktorová množina}
nebo též \defined{faktor-množina} $M$ podle $\equiv$.
\item
\defined[uspořádání]{uspořádání} (zn. $\leq$) je relace reflexivní, transitivní a slabě antisymetrická.
\item
\defined[uspořádání!ostré]{ostré uspořádání} (zn. $<$) je relace transitivní a silně antisymetrická.
Platí: $$a\leq b \Lequiv a=b \Lor a<b,$$ $$a<b \Lequiv a\neq b \Land a\leq b.$$
\item
\defined[uspořádání!úplné]{úplné uspořádání} (\defined[uspořádání!lineární]{lineární uspořádání})
je relace trichotonická (každé dva prvky jsou \defined[prvek (teorie množin)!srovnatelnost]{srovnatelné}),
slabě antisymetrická, transitivní a reflexivní.
\end{enumerate}%XX