cheat2.tex

\documentclass[a4paper,10pt]{article}
\usepackage{mypreamble}

%% Page setup
\geometry{
    margin=2cm,
    includehead,
    includefoot,
    headsep=8pt,
    footskip=16pt,
}
\pagestyle{fancy}
\MakeSingleHeader% {<l>}{<r>}
    {\TextCheatsheetEng: Binary Relations}%
    {\TextDiscreteMathEng, \IconFall~Fall 2024}
\fancyfoot{}
\fancyfoot[L]{\tiny Build time: \DTMnow}
\fancyfoot[R]{\tiny Source code can be found at \url{https://github.com/Lipen/discrete-math-course}}
% \fancyfoot[C]{\thepage\ of \zpageref{LastPage}}

%% Add custom setup below

% \titlespacing{\type}{left}{above}{below}[right]
\titlespacing{\section}{0pt}{*1}{*0.5}
\titlespacing{\subsection}{0pt}{*1}{*0.5}

\setlength{\tabcolsep}{0pt}


\begin{document}

\setcounter{section}{1}
\section{Binary Relations Cheatsheet}

\subsection{Терминология и обозначения}

\begin{terms}
    \item $A \times B = \Set{\Pair{a,b} \given a \in A,~ b \in B}$ \--- \textbf{декартово произведение} множеств $A$ и $B$.
    \hfill\href{https://en.wikipedia.org/wiki/Cartesian_product}{Cartesian product}

    \item $A^2 = A \times A$ \--- \textbf{декартов квадрат} множества $A$.
    \hfill\href{https://en.wikipedia.org/wiki/Cartesian_product\#n-ary_Cartesian_power}{Cartesian square}

    \item $R \subseteq A \times B$ \--- \textbf{бинарное отношение} $R$, определённое на паре множеств $A$ и $B$.
    \hfill\href{https://en.wikipedia.org/wiki/Binary_relation}{Binary relation}

    \item $R \subseteq A^2$ \--- (гомогенное) бинарное отношение на множестве $A$.
    \hfill\href{https://en.wikipedia.org/wiki/Homogeneous_relation}{Homogeneous relation (endorelation)}

    \item $a \rel b$ \--- элементы $a$ и $b$ \textbf{находятся в отношении} $R$, т.е. $\Pair{a,b} \in R$.
    \hfill\href{https://en.wikipedia.org/wiki/Ordered_pair}{Ordered pair}

    \item $\emptyrel{A} = \emptyset$ \--- \textbf{пустое} отношение.
    \hfill\href{https://en.wikipedia.org/wiki/Homogeneous_relation#Particular_homogeneous_relations}{Empty relation}

    \item $\idrel{A} = \Set{\Pair{x,x} \given x \in A}$ \--- \textbf{тождественное (диагональное)} отношение.
    \hfill\href{https://en.wikipedia.org/wiki/Homogeneous_relation#Particular_homogeneous_relations}{Identity relation}

    \item $\universalrel{A} = A^2 = \Set{\Pair{x,y} \given x,y \in A}$ \--- \textbf{полное (универсальное)} отношение.
    \hfill\href{https://en.wikipedia.org/wiki/Homogeneous_relation#Particular_homogeneous_relations}{Universal relation}

    % \item $$
\end{terms}


\subsection{Операции над отношениями}

\begin{terms}
    \item $R \union S = \Set{\Pair{a,b} \given (a \rel[R] b) \lor (a \rel[S] b)}$ \--- \textbf{объединение} отношений $R$ и $S$.
    \hfill\href{https://en.wikipedia.org/wiki/Binary_relation#Union}{Union of relations}

    \item $R \intersection S = \Set{\Pair{a,b} \given (a \rel[R] b) \land (a \rel[S] b)}$ \--- \textbf{пересечение} отношений $R$ и $S$.
    \hfill\href{https://en.wikipedia.org/wiki/Binary_relation#Intersection}{Intersection of relations}

    \item $R^{-1} = \Set{\Pair{b,a} \given \Pair{a,b} \in R} \subseteq B \times A$ \--- отношение, \textbf{обратное} к $R \subseteq A \times B$.
    \hfill\href{https://en.wikipedia.org/wiki/Converse_relation}{Converse relation}

    \item $\overline{R} = \Set{\Pair{a,b} \given \Pair{a,b} \notin R}$ \--- \textbf{дополнение} отношения $R$.
    \hfill\href{https://en.wikipedia.org/wiki/Complement_(set_theory)\#Complementary_relation}{Complementary relation}

    \item $R \relcomp S = S \circ R = \Set{\Pair{x,y} \given \exists z : (x \rel[R] z) \land (z \rel[S] y)}$ \--- \textbf{композиция} отношений $R$ и $S$.
    \hfill\href{https://en.wikipedia.org/wiki/Composition_of_relations}{Composition of relations}
    \begin{terms}
        \item Если $R \subseteq A \times B$ и $S \subseteq B \times C$, то $R \relcomp S \subseteq A \times C$.
    \end{terms}

    \item $R^{\circ i+1} = R \circ R^{\circ i}$ \--- \textbf{\enquote{композитная} (функциональная) степень} отношения $R$.
    \hfill\href{https://en.wikipedia.org/wiki/Function_composition#Functional_powers}{Functional power}

    При этом $R^{\circ 1} = R$, $R^{\circ 0} = \idrel{A}$.
    Чаще используется нотация~$R^{i}$, совпадающая с нотацией \textit{Декартовой степени}.

    \item $R[M] = \Set{y \given \exists x \in M : x \rel y}$ \--- \textbf{применение} отношения $R$ ко множеству $M$.

    \item \textbf{Замыкание отношения} $R$ относительно свойства $P$ \--- минимальное (по включению) надмножество~$R$, обладающее свойством~$P$.
    \hfill\href{https://en.wikipedia.org/wiki/Closure_(mathematics)#Binary_relation_closures}{Closure}

    \begin{terms}
        \item $R^{=} = R^{r} = R \union \idrel{A}$ \--- \textbf{рефлексивное замыкание} отношения $R \subseteq A^2$.
        \hfill\href{https://en.wikipedia.org/wiki/Reflexive_closure}{Reflexive closure}

        \item $R^{\sim} = R^{s} = R \union R^{-1}$ \--- \textbf{симметричное замыкание} отношения~$R$.
        \hfill\href{https://en.wikipedia.org/wiki/Symmetric_closure}{Symmetric closure}

        \item $R^{+} = R^{t} = \bigunionclap{n \in \NaturalPlus} R^n$ \--- \textbf{транзитивное замыкание} отношения $R$, где $R^1 = R$, $R^{k+1} = R^k \circ R$.
        \hfill\href{https://en.wikipedia.org/wiki/Transitive_closure}{Transitive closure}

        \item $R^{\equiv} = ((R^{r})^{s})^{t}$ \--- \textbf{рефлексивное симметричное транзитивное замыкание} отношения~$R$. Минимальное отношение эквивалентности, содержащее~$R$.
        \hfill\href{https://en.wikipedia.org/wiki/Reflexive_symmetric_transitive_closure}{Reflexive symmetric transitive closure}
    \end{terms}

    \item \textbf{Сокращение отношения} $R$ \--- минимальное отношение, \textit{замыкание} которого совпадает с \textit{замыканием}~$R$.

    \begin{terms}
        \item \textbf{Рефлексивное сокращение} $R^{\neq} = R \setminus \idrel{A}$ \--- минимальное отношение, рефлексивное замыкание которого совпадает с рефлексивным замыканием~$R$, то есть $(R^{\neq})^{=} = R^{=}$.
        \hfill\href{https://en.wikipedia.org/wiki/Reflexive_reduction}{Reflexive reduction}

        \item \textbf{Симметричное сокращение} $R^{\nsim}$ \--- минимальное отношение, симметричное замыкание которого совпадает с симметричным замыканием~$R$, то есть $(R^{\nsim})^{\sim} = R^{\sim}$.

        \item \textbf{Транзитивное сокращение} $R^{-}$ \--- минимальное отношение, транзитивное замыкание которого совпадает с транзитивным замыканием~$R$, то есть $(R^{-})^{+} = R^{+}$.
        \hfill\href{https://en.wikipedia.org/wiki/Transitive_reduction}{Transitive reduction}

        Транзитивное сокращение $R^{-}$ отношения $R$ без циклов (в том числе, без петель) можно найти, используя его транзитивное замыкание: $R^{-}_{\text{DAG}} = R \setminus (R \circ R^{+}) = R \setminus \bigunionclap{n \geq 2} R^n$.

        Для нахождения транзитивного сокращения отношения без циклов, но с петлями, необходимо запомнить существующие петли, убрать их, осуществить транзитивное сокращение (см. выше), а затем вернуть исходные петли: $R^{-}_{\text{loop-DAG}} = (R^{\neq})^{-} \union \Set{(x,x) \given x \rel x}$.
    \end{terms}
\end{terms}


%% Ensure page break
\newpage


\subsection{Некоторые свойства гомогенных бинарных отношений}

Возможные свойства гомогенного бинарного отношения $R \subseteq M^2$:
\hfill\href{https://en.wikipedia.org/wiki/Homogeneous_relation#Properties}{Properties of homogeneous relations}

\begin{tabular}{@{\hspace{.5em}} l @{\hspace{1em}} L @{\hspace{.5em}}}
    \toprule
    \thead{Свойство} & \thead{\text{Формальное определение}} \\
    \midrule
%
    Рефлексивность
    \hfill\href{https://en.wikipedia.org/wiki/Reflexive_relation}{Reflexive}
    & \forall x \in M : x \rel x \\
%
    Иррефлексивность
    \hfill\href{https://en.wikipedia.org/wiki/Irreflexive_relation}{Irreflexive}
    & \forall x \in M : \neg (x \rel x) \\
%
    Корефлексивность
    \hfill\href{https://en.wikipedia.org/wiki/Coreflexive_relation}{Coreflexive}
    & \forall x,y \in M : (x \rel y) \implies (x = y) \\
%
    Симметричность
    \hfill\href{https://en.wikipedia.org/wiki/Symmetric_relation}{Symmetric}
    & \forall x,y \in M : (x \rel y) \implies (y \rel x) \\
%
    Антисимметричность
    \hfill\href{https://en.wikipedia.org/wiki/Antisymmetric_relation}{Antisymmetric}
    & \forall x,y \in M : (x \rel y) \land (y \rel x) \implies (x = y) \\
%
    Асимметричность
    \hfill\href{https://en.wikipedia.org/wiki/Asymmetric_relation}{Asymmetric}
    & \forall x,y \in M : (x \rel y) \implies \neg (y \rel x) \\
%
    Транзитивность
    \hfill\href{https://en.wikipedia.org/wiki/Transitive_relation}{Transitive}
    & \forall x,y,z \in M : (x \rel y) \land (y \rel z) \implies (x \rel z) \\
%
    Антитранзитивность
    \hfill\href{https://en.wikipedia.org/wiki/Antitransitive}{Antitransitive}
    & \forall x,y,z \in M : (x \rel y) \land (y \rel z) \implies \neg (x \rel z)) \\
%
    Евклидовость (правая)~
    \hfill\href{https://en.wikipedia.org/wiki/Euclidean_relation}{Right Euclidean}
    & \forall x,y,z \in M : (x \rel y) \land (x \rel z) \implies (y \rel z) \\
%
    Евклидовость (левая)
    \hfill\href{https://en.wikipedia.org/wiki/Euclidean_relation}{Left Euclidean}
    & \forall x,y,z \in M : (y \rel x) \land (z \rel x) \implies (y \rel z) \\
%
    Связность
    \hfill\href{https://en.wikipedia.org/wiki/Connected_relation}{Semiconnex}
    & \forall x,y \in M : (x \neq y) \implies (x \rel y) \lor (y \rel x) \\
%
    Сильная связность~
    \hfill\href{https://en.wikipedia.org/wiki/Connected_relation}{Connex}
    & \forall x,y \in M : (x \rel y) \lor (y \rel x) \\
%
    Плотность
    \hfill\href{https://en.wikipedia.org/wiki/Dense_relation}{Dense}
    & \forall x,y \in M : (x \rel y) \implies \exists z \in M : (x \rel z) \land (z \rel y) \\
%
    \bottomrule
\end{tabular}


\subsection{Отношения эквивалентности}

\begin{terms}
    \item \textbf{Отношение толерантности} \--- \textit{рефлексивное} и \textit{симметричное}.
    \hfill\href{https://en.wikipedia.org/wiki/Tolerance_relation}{Tolerance relation}

    \item \textbf{Отношение эквивалентности} \--- \textit{рефлексивное}, \textit{симметричное} и \textit{транзитивное}.
    \hfill\href{https://en.wikipedia.org/wiki/Equivalence_relation}{Equivalence relation}

    \item $\equivclass{x} = \Set{y \in A \given x \rel y}$ \--- \textbf{класс эквивалентности} элемента $x \in A$.
    \hfill\href{https://en.wikipedia.org/wiki/Equivalence_class}{Equivalence class}

    \item $\quotient[R]{A} = \equivclass{A} = \Set{\equivclass{x} \given x \in A}$ \--- \textbf{разбиение} множества $A$ \textbf{на классы эквивалентности}.
    \hfill\href{https://en.wikipedia.org/wiki/Quotient_set}{Quotient set}
\end{terms}


\subsection{Отношения порядка%
\texorpdfstring{\hfill\normalfont\href{https://en.wikipedia.org/wiki/Order_theory}{Order theory}}{}}

\begin{terms}
    \item \textbf{Предпорядок} (\textbf{квазипорядок}) \--- \emph{рефлексивное} и \emph{транзитивное} отношение.
    \hfill\href{https://en.wikipedia.org/wiki/Preorder}{Preorder}
    % Memetic stuff:
    % https://begriffs.com/posts/2013-12-17-the-weird-forest-of-big-oh-asymptotics.html

    \item \textbf{Частичный порядок} \--- \emph{рефлексивное}, \emph{антисимметричное} и \emph{транзитивное} отношение.
    \hfill\href{https://en.wikipedia.org/wiki/Partial_order}{Partial order}

    \item \textbf{Линейный (полный) порядок} \--- \emph{сильно-связный} частичный порядок.
    \hfill\href{https://en.wikipedia.org/wiki/Linear_order}{Linear (total) order}

    \item \textbf{Строгий частичный порядок} \--- \emph{иррефл.}, \emph{антисимм.} и \emph{транзитивное} отношение.
    \hfill\href{https://en.wikipedia.org/wiki/Partially_ordered_set#Strict_partial_order}{Strict partial order}

    \item \textbf{Строгий линейный (полный) порядок} \--- \emph{связный} строгий частичный порядок.
    \hfill\href{https://en.wikipedia.org/wiki/Total_order#Strict_total_order}{Strict total order}

    \item \textbf{Частично упорядоченное множество} \--- упорядоченная пара $\Pair{M,R}$, где $M$ \--- произвольное множество, $R \subseteq M^2$ \--- отношение \textit{частичного порядка} на $M$.
    \hfill\href{https://en.wikipedia.org/wiki/Partially_ordered_set}{Partially ordered set (Poset)}

    \item Элемент упорядоченного множества $\Pair{M, R}$ называется \textbf{максимальным}, если он \textit{не меньше других} элементов, то есть \textit{не существует элемента больше}.
    Дуально, элемент называется \textbf{минимальным}, если он \textit{не больше других}, то есть \textit{нет элемента меньше}.
    \hfill\href{https://en.wikipedia.org/wiki/Maximal_and_minimal_elements}{Maximal and minimal elements}

    $\begin{WithArrows}[format=lClClCl, jot=0pt]
        a \in M \text{ is \textbf{maximal}}
        & \iff & \forall b \neq a : \neg (a \rel b)
        & ~\equiv~ & \nexists b \neq a : (a \rel b)
        & ~\equiv~ & \forall b \in M : (a \rel b) \implies (a = b)
        \\
        a \in M \text{ is \textbf{minimal}}
        & \iff & \forall b \neq a : \neg (b \rel a)
        & ~\equiv~ & \nexists b \neq a : (b \rel a)
        & ~\equiv~ & \forall b \in M : (b \rel a) \implies (b = a)
    \end{WithArrows}$

    \item Элемент упорядоченного множества $\Pair{M, R}$ называется \textbf{наибольшим}, если он \textit{больше всех} элементов.
    Дуально,~элемент называется \textbf{наименьшим}, если он \textit{меньше всех} элементов.
    \hfill\href{https://en.wikipedia.org/wiki/Greatest_element_and_least_element}{Greatest and least elements}

    $\begin{WithArrows}[format=lCl, jot=0pt]
        a \in M \text{ is \textbf{maximum} (\textbf{greatest})}
        & \iff & \forall b : (b \rel a)
        \\
        a \in M \text{ is \textbf{minimum} (\textbf{least})}
        & \iff & \forall b : (a \rel b)
    \end{WithArrows}$

    \item $(x \lessdot y) \iff (x < y) \land \nexists z: ((x < z) \land (z < y))$ \--- \textbf{отношение покрытия} ($y$ \enquote{\textit{покрывает}} $x$).
    \hfill\href{https://en.wikipedia.org/wiki/Covering_relation}{Covering relation}
    \begin{terms}
        % \item \enquote{$\leq$} \--- некоторый \textit{частичный порядок}
        \item \enquote{$<$} \--- индуцированный \textit{строгий частичный порядок}: $(x < y) \iff (x \leq y) \land (x \neq y)$
    \end{terms}

    \item \textbf{Диаграмма Хассе} \--- визуализация частично упорядоченного множества $\Pair{M, R}$ в виде графа \textit{транзитивного сокращения}~$R^{-}$.
    Вершины такого графа \--- элементы множества~$M$, а рёбра (изображаются по возможности направленными вверх) соответствуют \textit{отношению покрытия}.
    \hfill\href{https://en.wikipedia.org/wiki/Hasse_diagram}{Hasse diagram}
    % Fun stuff:
    % http://blog.ezyang.com/2010/12/hussling-haskell-types-into-hasse-diagrams/
\end{terms}

\begin{center}
\begin{tabular}{@{} c @{}}
% \begin{adjustbox}{cframe=red}
\begin{tikzpicture}[
    mynode/.style={
        inner sep=2pt,
    },
    rel/.style={
        -,
        % ->,>={Latex[round,open]},
    },
]
    \def\vgap{7.3mm}
    \def\n{4}
    \foreach \i [evaluate=\i as \ni using {int(\i)}, evaluate=\i as \j using {\i-1}] in {1,...,\n}{
        \node[mynode] (n\ni) at (0,\j*\vgap) {\ni};
    }
    \node[mynode] (top) at (0,\n*\vgap) {$\cdots$};
    \foreach \i [evaluate=\i as \ni using {int(\i)}, evaluate=\i as \nj using {int(\i-1)}] in {2,...,\n}{
        \draw[rel] (n\nj) -- (n\ni);
    }
    \draw[rel] (n\n) -- (top);
    \node (label) at (current bounding box.south) [below] {$\Pair{\NaturalPlus, \leq}$};
\end{tikzpicture}%
\hspace{2em}%
\begin{tikzpicture}[
    mynode/.style={
        inner sep=2pt,
    },
    rel/.style={
        ->,>={Latex[round,open]},
    },
    frontline/.style={
        preaction={draw=white,-,line width=4pt},
    },
]
    \def\hgap{12mm}
    \def\vgap{10mm}
    \node[mynode] (empty) at (0,0)            {$\emptyset$};
    \node[mynode] (a)     at (-\hgap,\vgap)   {$\Set{a}$};
    \node[mynode] (b)     at (0,\vgap)        {$\Set{b}$};
    \node[mynode] (c)     at (\hgap,\vgap)    {$\Set{c}$};
    \node[mynode] (ab)    at (-\hgap,2*\vgap) {$\Set{a,b}$};
    \node[mynode] (ac)    at (0,2*\vgap)      {$\Set{a,c}$};
    \node[mynode] (bc)    at (\hgap,2*\vgap)  {$\Set{b,c}$};
    \node[mynode] (abc)   at (0,3*\vgap)      {$\Set{a,b,c}$};
    \draw[rel] (empty) -- (a);
    \draw[rel] (empty) -- (b);
    \draw[rel] (empty) -- (c);
    \draw[rel] (a) -- (ab);
    \draw[rel] (a) -- (ac);
    \draw[rel] (c) -- (ac);
    \draw[rel] (c) -- (bc);
    \draw[rel,frontline] (b) -- (ab);
    \draw[rel,frontline] (b) -- (bc);
    \draw[rel] (ab) -- (abc);
    \draw[rel] (ac) -- (abc);
    \draw[rel] (bc) -- (abc);
    \node (label) at (current bounding box.south) [below] {$\Pair{\powerset{\Set{a,b,c}}, \subseteq}$};
\end{tikzpicture}%
\hspace{2em}%
\begin{tikzpicture}[
    rel/.style={
        -,
        preaction={draw=white,-,line width=4pt},
    },
    reldot/.style={rel, dotted},
    node distance=2mm,
]
    \matrix (m) [
        matrix of math nodes,
        row sep=4mm,
        column sep=3mm,
        nodes={inner sep=2pt},
    ] {
        |(n8)| 8 & |(n12)| 12 & |(n20)| 20 & |(p3)| \dots \\
        |(n4)| 4 & |(n6)| 6 & |(n10)| 10 & |(p2)| \dots \\
        |(n2)| 2 & |(n3)| 3 & |(n5)| 5 & |(p1)| \dots \\
    };
    \node (zero) [above=of m] {0};
    \node (one) [below=of m] {1};

    \draw[rel] (one) -- (n2);
    \draw[rel] (one) -- (n3);
    \draw[rel] (one) -- (n5);
    \draw[rel] (one) -- (p1);

    \draw[rel] (n2) -- (n4);
    \draw[rel] (n2) -- (n6);
    \draw[rel] (n2) -- (n10);
    \draw[reldot] (n2) -- (p2);
    \draw[rel] (n3) -- (n6);
    \draw[reldot] (n3) -- (p2);
    \draw[rel] (n5) -- (n10);
    \draw[reldot] (n5) -- (p2);
    \draw[reldot] (p1) -- (p2);

    \draw[rel] (n4) -- (n8);
    \draw[rel] (n4) -- (n12);
    \draw[rel] (n4) -- (n20);
    \draw[reldot] (n4) -- (p3);
    \draw[rel] (n6) -- (n12);
    \draw[reldot] (n6) -- (p3);
    \draw[rel] (n10) -- (n20);
    \draw[reldot] (n10) -- (p3);
    \draw[reldot] (p2) -- (p3);

    \draw[reldot] (n8)  -- (zero);
    \draw[reldot] (n12) -- (zero);
    \draw[reldot] (n20) -- (zero);
    \draw[reldot] (p3)  -- (zero);

    \node (label) at (current bounding box.south) [below] {$\Pair{\NaturalZero, \divides}$ (\href{https://en.wikipedia.org/wiki/Divisor#Definition}{Divisibility})};
\end{tikzpicture}%
\end{tabular}
\end{center}

% Фундированность
% \hfill\href{https://en.wikipedia.org/wiki/Well-founded_relation}{Well-founded}
% & \mathrlap{\text{Each non-empty } S \subset M : S \text{ contains a minimal element w.r.t. } R} \\
% %
% Вполне-упорядоченность
% \hfill\href{https://en.wikipedia.org/wiki/Well-order}{Well-ordering}
% & \mathrlap{\text{Each non-empty } S \subset M \text{ contains the smallest element w.r.t. } R} \\
% %
% ? & \text{Each non-empty } S \subset M : S \text{ contains a minimal element w.r.t. } R & \href{https://en.wikipedia.org/wiki/Well-founded_relation}{Well-founded} \\
% Вполне упорядоченное & \text{Each non-empty } S \subset M \text{ contains the smallest element w.r.t. } R & \href{https://en.wikipedia.org/wiki/Well-order}{Well-ordering} \\


%% Ensure page break
\newpage


\subsection{Некоторые свойства гетерогенных бинарных отношений}

Возможные свойства гетерогенного бинарного отношения $R \subseteq X \times Y$:
\hfill\href{https://en.wikipedia.org/wiki/Binary_relation#Special_types_of_binary_relations}{Special types of binary relations}

\begin{tabular}{@{\hspace{.5em}} l @{\hspace{1em}} L @{\hspace{.5em}}}
    \toprule
    \thead{Отношение} & \thead{\text{Формальное определение}} \\
    \midrule
%
    Injective (left-unique)
    & \forall x,z \in X ~\forall y \in Y : (x \rel y) \land (z \rel y) \implies (x = z) \\
 %
    Functional (right-unique)
    & \forall x \in X ~\forall y,z \in Y : (x \rel y) \land (x \rel z) \implies (y = z) \\
%
    One-to-One
    & \text{Injective and Functional} \\
%
    One-to-Many
    & \text{Injective and not Functional} \\
%
    Many-to-One
    & \text{Not Injective and Functional} \\
%
    Many-to-Many
    & \text{Not Injective and not Functional} \\
%
    Serial (left-total)
    & \forall x \in X : \exists y \in Y : (x \rel y) \\
%
    Surjective (right-total)
    & \forall y \in Y : \exists x \in X : (x \rel y) \\
%
    \bottomrule
\end{tabular}

\subsection{Функции как отношения}

\begin{terms}
    \item \textbf{Частичная функция} $f : X \pto Y$ \--- Functional бинарное отношение.
    \hfill\href{https://en.wikipedia.org/wiki/Partial_function}{Partial function}

    \item \textbf{Функция} $f : X \to Y$ \--- Functional и Serial бинарное отношение.
    \hfill\href{https://en.wikipedia.org/wiki/Function_(mathematics)}{Function}
\end{terms}


%% Ensure page break
\newpage


%% Ensure page break
% \vspace{5cm}
% \newpage


\subsection{Матричное представление отношений}

Любое бинарное отношение $R \subseteq A \times B$, определённое на паре множеств $A = \Set{a_1, \dotsc, a_n}$ и $B = \Set{b_1, \dotsc, b_m}$ может быть представлено в виде матрицы $\relmatrix{R}$ размера $n \times m$, элементы которой \--- 0 или 1:
\hfill\href{https://en.wikipedia.org/wiki/Logical_matrix}{Logical matrix}
\[
    \relmatrix{R} = \begin{bmatrix} r_{i,j} \end{bmatrix}
    \qquad
    % ,\text{ где }
    r_{i,j} = \begin{cases*}
        1 & если $\Pair{a_i,b_j} \in R \iff a_i \rel b_j$ \\
        0 & если $\Pair{a_i,b_j} \notin R \iff a_i \nrel b_j$
    \end{cases*}
\]

% Пусть $A$ \--- множество. Матрица тождественного отношения $\idrel{A}$ \--- единичная матрица; матрица полного отношения~$\universalrel{A}$ полностью составлена из 1:

% \[
%     \relmatrix{\idrel{A}} = \begin{bmatrix}
%         1 & 0 & \dots & 0 \\
%         0 & 1 & \dots & 0 \\
%         \hdotsfor[2]{4} \\
%         0 & 0 & \dots & 1
%     \end{bmatrix}
%     \qquad
%     \relmatrix{\universalrel{A}} = \begin{bmatrix}
%         1 & 1 & \dots & 1 \\
%         1 & 1 & \dots & 1 \\
%         \hdotsfor[2]{4} \\
%         1 & 1 & \dots & 1 \\
%     \end{bmatrix}
% \]

\newenvironment{mygridscope}[1]{% {<n>}
    \let\oldn\n
    \def\n{#1}

    \newcommand\drawcell[2][]{% [<style>]{<pos>}
        \draw[cell, ##1] (##2) rectangle +(1,1); }
    \newcommand\drawcells[1]{% {<cell-macro>}
        \foreach \i in {1,...,\n} {
            \foreach \j in {1,...,\n} {
                ##1
            }
        }
    }
    \newcommand\drawgrid[1][]{% [<style>]
        \draw[grid, ##1] (0,0) grid (\n,\n); }
    \newcommand\drawleftlabels[2][]{% [<style>]{<label-macro>}
        \foreach \i in {1,...,\n} {
            \node[leftlabel,##1] at (\i,0) {##2};
        }
    }
    \newcommand\drawtoplabels[2][]{% [<style>]{<label-macro>}
        \foreach \i in {1,...,\n} {
            \node[toplabel,##1] at (0,\i) {##2};
        }
    }

    \begin{scope}[yshift=\n cm, rotate=-90]
    \begin{scope}[xshift=-0.5cm, yshift=-0.5cm]
    \begin{scope}[mygrid]
}{
    \end{scope}
    \end{scope}
    \end{scope}
    \let\n\oldn
}

\newcommand\drawlabelnorth[1]{% {<label>}
    \node[above,align=center] at (current bounding box.north) {#1};
}
\newcommand\drawlabelsouth[1]{% {<label>}
    \node[below,align=center] at (current bounding box.south) {#1};
}

% myrotate/.style={rotate=#1, nodes={rotate=#1}}
\tikzstyle{mymatrixstyle}=[
    scale=0.5,
    font=\small,
    mygrid/.style={
        % rotate=-45,
        % myrotate=-45,
    },
    % baseline={([yshift=-0.6ex]current bounding box.center)},
    cell/.style={ % Style for each cell
        draw=none,
        fill=none,
        % fill opacity=0.2,
        xshift=-0.5cm,
        yshift=-0.5cm,
    },
    grid/.style={ % Style for the actual grid
        xshift=0.5cm,
        yshift=0.5cm,
    },
    mylabel/.style={
        % overlay,
    },
    leftlabel/.style={
        mylabel,
    },
    toplabel/.style={
        mylabel,
    },
]
\tikzstyle{mymatrixlegendstyle}=[
    mymatrixstyle,
    baseline={([yshift=-0.6ex]base)},
]

\def\matrixsize{4}

Пусть $R \subseteq M^2$ \--- гомогенное бинарное отношение, определённое на множестве $M = \Set{m_1, \dotsc, m_{\matrixsize}}$.
Примеры матриц отношений, обладающих некоторыми свойствами:

\begin{table}[!h]
\centering
\begin{tabular}[t]{ c *{2}{@{\hspace{1cm}} c} }
    \begin{tikzpicture}[mymatrixstyle]
        \begin{mygridscope}{\matrixsize}
            \drawcells{
                \ifthenelse{\i = \j}{
                    \drawcell[fill=blue!20]{\i,\j}
                    \node at (\i,\j) {1};
                }{
                    \node at (\i,\j) {$\cdot$};
                }
            }
            \drawgrid
            \drawleftlabels{$m_{\i}$}
            \drawtoplabels{$m_{\i}$}
        \end{mygridscope}
        \drawlabelnorth{Reflexive \\ $\forall x \in M : x \rel x$}
    \end{tikzpicture}
&
    \begin{tikzpicture}[mymatrixstyle]
        \begin{mygridscope}{\matrixsize}
            \drawcells{
                \ifthenelse{\i = \j}{
                    \drawcell[fill=blue!20]{\i,\j}
                    \node at (\i,\j) {0};
                }{
                    \node at (\i,\j) {$\cdot$};
                }
            }
            \drawgrid
            \drawleftlabels{$m_{\i}$}
            \drawtoplabels{$m_{\i}$}
        \end{mygridscope}
        \drawlabelnorth{Irreflexive \\ $\forall x \in M : \neg (x \rel x)$}
    \end{tikzpicture}
&
    \begin{tikzpicture}[mymatrixstyle]
        \begin{mygridscope}{\matrixsize}
            \drawcells{
                \ifthenelse{\i = \j}{
                    \drawcell[fill=blue!20]{\i,\j}
                    \node at (\i,\j) {$\cdot$};
                }{
                    \drawcell[fill=red!20]{\i,\j}
                    \node at (\i,\j) {0};
                }
            }
            \drawgrid
            \drawleftlabels{$m_{\i}$}
            \drawtoplabels{$m_{\i}$}
        \end{mygridscope}
        \drawlabelnorth{Coreflexive \\ $\mathclap{\forall x,y \in M : (x \rel y) \implies (x = y)}$}
    \end{tikzpicture}
\\[8pt]
    \begin{tikzpicture}[mymatrixstyle]
        \begin{mygridscope}{\matrixsize}
            \drawcells{
                \ifthenelse{\i = \j}{
                    \drawcell[fill=blue!20]{\i,\j}
                    \node at (\i,\j) {$\cdot$};
                }{\ifthenelse{\i > \j}{
                    \pgfmathsetmacro{\v}{random(0,1)}
                    \ifthenelse{\v = 1}{
                        \drawcell[fill=green!20]{\i,\j}
                        \drawcell[fill=green!20]{\j,\i}
                    }{
                        \drawcell[fill=red!20]{\i,\j}
                        \drawcell[fill=red!20]{\j,\i}
                    }
                    \node at (\i,\j) {$\v$};
                    \node at (\j,\i) {$\v$};
                }{}}
            }
            \drawgrid
            \drawleftlabels{$m_{\i}$}
            \drawtoplabels{$m_{\i}$}
        \end{mygridscope}
        \drawlabelnorth{Symmetric \\ $\forall x,y \in M :$ \\ $(x \rel y) \implies (y \rel x)$}
    \end{tikzpicture}
&
    \begin{tikzpicture}[mymatrixstyle]
        \begin{mygridscope}{\matrixsize}
            \drawcells{
                \ifthenelse{\i = \j}{
                    \drawcell[fill=blue!20]{\i,\j}
                    \node (\i-\j) at (\i,\j) {$\cdot$};
                }{\ifthenelse{\i > \j}{
                    \pgfmathsetmacro{\v}{random(0,1)}
                    \ifthenelse{\v = 1}{
                        \drawcell[fill=green!20]{\i,\j}
                        \drawcell[fill=red!20]{\j,\i}
                        \node (\i-\j) at (\i,\j) {1};
                        \node (\j-\i) at (\j,\i) {0};
                    }{
                        \drawcell[fill=red!20]{\i,\j}
                        \node (\i-\j) at (\i,\j) {0};
                        \node (\j-\i) at (\j,\i) {$\cdot$};
                    }
                }{}}
            }
            \drawgrid
            \drawleftlabels{$m_{\i}$}
            \drawtoplabels{$m_{\i}$}
        \end{mygridscope}
        \drawlabelnorth{Antisymmetric \\ $\forall x,y \in M :$ \\ $\mathclap{(x \rel y) \land (y \rel x) \implies (x = y)}$}
    \end{tikzpicture}
&
    \begin{tikzpicture}[mymatrixstyle]
        \begin{mygridscope}{\matrixsize}
            \drawcells{
                \ifthenelse{\i = \j}{
                    \drawcell[fill=blue!20]{\i,\j}
                    \node at (\i,\j) {0};
                }{\ifthenelse{\i > \j}{
                    \pgfmathsetmacro{\v}{random(0,1)}
                    \ifthenelse{\v = 1}{
                        \drawcell[fill=green!20]{\i,\j}
                        \drawcell[fill=red!20]{\j,\i}
                        \node at (\i,\j) {1};
                        \node at (\j,\i) {0};
                    }{
                        \drawcell[fill=red!20]{\i,\j}
                        \node at (\i,\j) {0};
                        \node at (\j,\i) {$\cdot$};
                    }
                }{}}
            }
            \drawgrid
            \drawleftlabels{$m_{\i}$}
            \drawtoplabels{$m_{\i}$}
        \end{mygridscope}
        \drawlabelnorth{Asymmetric \\ $\forall x,y \in M :$ \\ $(x \rel y) \implies \neg (y \rel x)$}
    \end{tikzpicture}
\end{tabular}
\end{table}

\textbf{Легенда:}

\begingroup
\setcellgapes[t]{4pt}
\makegapedcells
\begin{tabular}{ r @{~---~} l }
    \begin{tikzpicture}[mymatrixlegendstyle]
        \coordinate (base) at (0,0.5);
        \begin{mygridscope}{1}
            \drawcell[fill=green!20]{1,1}
            \node at (1,1) {1};
            \drawgrid
            \drawleftlabels{$m_{i}$}
            \drawtoplabels{$m_{j}$}
        \end{mygridscope}
    \end{tikzpicture}
    & $m_i$ и $m_j$ находятся в отношении $R$, т.е. $m_i \rel m_j$
\\
    \begin{tikzpicture}[mymatrixlegendstyle]
        \coordinate (base) at (0,0.5);
        \begin{mygridscope}{1}
            \drawcell[fill=red!20]{1,1}
            \node at (1,1) {0};
            \drawgrid
            \drawleftlabels{$m_i$}
            \drawtoplabels{$m_j$}
        \end{mygridscope}
    \end{tikzpicture}
    & $m_i$ и $m_j$ не находятся в отношении $R$, т.е. $m_i \nrel m_j$
\\
    \begin{tikzpicture}[mymatrixlegendstyle]
        \coordinate (base) at (0,0.5);
        \begin{mygridscope}{1}
            \node at (1,1) {$\cdot$};
            \drawgrid
            \drawleftlabels{$m_i$}
            \drawtoplabels{$m_j$}
        \end{mygridscope}
    \end{tikzpicture}
    & $m_i$ и $m_j$ могут находиться в отношении $R$, а могут и не находиться
\end{tabular}
\endgroup


% \subsection{Графовое представление отношений}

% Любое бинарное отношение $R \subseteq A \times B$, определённое на паре множеств $A$ и $B$ может быть представлено в виде ориентированного графа $G = \Pair{V,E}$, где $V = A \union B$ \--- множество вершин, $E = R$ \--- множество направленных рёбер.

% \vspace{5mm}
% % \begin{adjustbox}{cframe=red}
% \begin{tikzpicture}[>=stealth]
%     \node[draw,circle] (v3) at (0,0) {3};
%     \node[draw,circle] (v1) [above right of=v3] {1};
%     \node[draw,circle] (v2) [below right of=v3] {2};
%     \node[draw,circle] (v4) [right of=v2] {4};
%     \node[draw,circle] (v5) [right of=v1] {5};

%     \path[->]
%         (v1) edge[out=-45, in=-135] (v5)
%         (v5) edge[out=135, in=45] (v1)
%         (v2) edge[out=-45, in=-135] (v4)
%         (v4) edge[out=135, in=45] (v2)
%         (v3) edge[out=120, in=60, looseness=4] (v3)
%     ;

%     \drawlabelnorth{$A = \Set{1,\dotsc,5},\quad R \subseteq A^2$ \\ $a \rel b \iff a + b \equiv 1 \pmod{5}$}
% \end{tikzpicture}
% % \end{adjustbox}


% \subsection{Функциональные отношения}

% ...


\end{document}