% relation-operation.tex

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \teal{\Large 5 Operations}
    \[
      R^{-1} \qquad R|_{X} \qquad R[X] \qquad R^{-1}[Y] \qquad R \circ S
    \]
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[逆 (Inverse)]
    The {\it inverse} of $R$ is the \purple{relation}
    \[
      R^{-1} = \set{(a, b) \mid (b, a) \in R}
    \]
  \end{definition}

  \pause
  \[
    R = \set{(x, y) \mid x = y} \subseteq \R \times \R \qquad
    R^{-1} = \pause R
  \]
  \pause
  \[
    R = \set{(x, y) \mid y = \sqrt{x}} \subseteq \R \times \R \qquad
    R^{-1} = \pause \set{(x, y) \mid y = x^{2} \land x > 0}
  \]
  \pause
  \[
    \le = \set{(x, y) \mid x \le y} \subseteq \R \times \R \qquad
    \le^{-1} \;= \pause \ge \;\triangleq \set{(x, y) \mid x \ge y}
  \]
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{theorem}
    \[
      (R^{-1})^{-1} = R
    \]
  \end{theorem}

  \pause
  \vspace{0.80cm}
  \red{对任意 $(a, b)$,}
  \setcounter{equation}{0}
  \begin{align}
    &(a, b) \in (R^{-1})^{-1} \\[6pt]
    \uncover<3->{\iff& (b, a) \in R^{-1} \\[6pt]}
    \uncover<4->{\iff& (a, b) \in R}
  \end{align}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{theorem}[关系的逆]
    \[
      R, S \;\text{均为关系}
    \]

    \[
      (R \cup S)^{-1} = R^{-1} \cup S^{-1}
    \]
    \[
      (R \cap S)^{-1} = R^{-1} \cap S^{-1}
    \]
    \[
      (R \setminus S)^{-1} = R^{-1} \setminus S^{-1}
    \]
  \end{theorem}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[左限制 (Left-Restriction)]
    Suppose $R \subseteq X \times Y$ and $S \subseteq X$.
    The {\it left-restriction} relation of $R$ \blue{to $S$} over $X$ and $Y$ is
    \[
      R|_{S} = \set{(x, y) \in R \mid \red{x \in S}}
    \]
  \end{definition}

  \pause
  \vspace{0.50cm}
  \begin{definition}[右限制 (Right-Restriction)]
    Suppose $R \subseteq X \times Y$ and $S \subseteq Y$.
    The {\it right-restriction} relation of $R$ \blue{to $S$} over $X$ and $Y$ is
    \[
      R|^{S} = \set{(x, y) \in R \mid \red{y \in S}}
    \]
  \end{definition}

  \pause
  \vspace{0.50cm}
  \begin{definition}[限制 (Restriction)]
    Suppose $R \subseteq X \times X$ and $S \subseteq X$.
    The {\it restriction} relation of $R$ \blue{to $S$} over $X$ is
    \[
      R|_{S} = \set{(x, y) \in R \mid \red{x \in S \land y \in S}}
    \]
  \end{definition}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \[
    R = \set{(x, y) \mid x^2 + y^2 = 1} \subseteq \R \times \R
  \]

  \pause
  \[
    R|_{\R^{+}} \qquad (\text{left restriction, restriction})
  \]
  \pause
  \[
    R|^{\R^{+}} \qquad (\text{right restriction})
  \]
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[像 (Image)]
    The {\it image} of $X$ \blue{under $R$} is the set
    \[
      R[X] = \set{\red{b \in \text{ran}(R)} \mid \exists a \in X.\; (a, b) \in R}
    \]
  \end{definition}

  \pause
  \[
    R[a] \triangleq R[\set{a}] = \set{b \mid (a, b) \in R}
  \]
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[逆像 (Inverse Image)]
    The {\it inverse image} of $Y$ \blue{under $R$} is the set
    \[
      R^{-1}[Y] = \set{\red{a \in \text{dom}(R)} \mid \exists b \in Y.\; (a, b) \in R}
    \]
  \end{definition}

  \pause
  \[
    R^{-1}[b] \triangleq R^{-1}[\set{b}] = \set{a \mid (a, b) \in R}
  \]
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \[
    R \subseteq A \times B \qquad X \subseteq A \qquad Y \subseteq B
  \]

  \pause
  \[
    R^{-1}[R[X]] \;\red{?}\; X
  \]

  \[
    R[R^{-1}[Y]] \;\red{?}\; Y
  \]

  \pause
  \vspace{0.60cm}
  \fig{width = 0.20\textwidth}{figs/be-careful}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{theorem}
    \[
      R[X_1 \cup X_2] = R[X_1] \cup R[X_2]
    \]
    \[
      R[X_1 \cap X_2] \subseteq R[X_1] \cap R[X_2]
    \]
    \[
      \teal{R[X_1 \setminus X_2] \supseteq R[X_1] \setminus R[X_2]}
    \]
  \end{theorem}

  \pause
  \vspace{0.30cm}
  \red{对任意 $b$,}
  \begin{align*}
    \onslide<3->{&b \in R[X_1 \cup X_2] \\[6pt]}
    \onslide<4->{\iff& \exists a \in X_1 \;\red{\cup}\; X_2.\; (a, b) \in R \\[6pt]}
    \onslide<5->{\iff& \exists a \in X_1.\; (a, b) \in R \lor \exists a \in X_2.\; (a, b) \in R \\[6pt]}
    \onslide<6->{\iff& b \in R[X_1] \lor b \in R[X_2] \\[6pt]}
    \onslide<7->{\iff& b \in R[X_{1}] \cup R[X_{2}]}
  \end{align*}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[复合 (Composition; $R \circ S$, $R ; S$)]
    The {\it composition} of relations $R \subseteq X \times \blue{Y}$
    and $S \subseteq \blue{Y} \times Z$ is the \purple{relation}
    \[
      R \circ S = \set{(a, c) \mid \exists b.\; (a, \blue{b}) \in S \land (\blue{b}, c) \in R}
    \]
  \end{definition}

  \pause
  \[
    R = \set{(1, 2), (3, 1)} \qquad S = \set{(1, 3), (2, 2), (2, 3)}
  \]

  \pause
  \[
    R \circ S = \pause \set{(1, 1), (2, 1)}
  \]
  \pause
  \[
    S \circ R = \pause \set{(1, 2), (1, 3), (3, 3)}
  \]
  \pause
  \[
    R^{(2)} \triangleq R \circ R = \pause \set{(3, 2)} \qquad
    \pause (R \circ R) \circ R = \pause \emptyset
  \]
  \pause
  \[
    S^{(2)} \triangleq S \circ S = \pause \set{(2, 2), (2, 3)} \qquad
    \pause (S \circ S) \circ S = \pause \set{(2, 2), (2, 3)}
  \]
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.60\textwidth}{figs/composition}

  \[
    |S \circ R| = \pause 7
  \]
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
% \begin{frame}{}
%   \[
%     R = \set{(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1,3), (2, 3)}
%   \]
%
%   \[
%     R \circ R = \pause \set{(0, 1), (0, 2), (0,3), (1, 1), (1, 2), (1, 3)}
%   \]
% \end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \[
    \le \circ \le \;\red{=}\; \pause \blue{\le}
  \]

  \pause
  \vspace{-0.60cm}
  \[
    \ge \circ \le \;\red{=}\; \pause \blue{\mathbb{R} \times \mathbb{R}}
  \]
  \pause
  \[
    \forall a, b \in \R.\; (a, b) \in \;\ge \circ \le
  \]
  \pause
  \[
    (a, \red{|a| + |b|}) \in \;\le \qquad (\red{|a| + |b|}, b) \in \;\ge
  \]
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{theorem}
    \[
      (R \circ S)^{-1} = S^{-1} \circ R^{-1}
    \]
  \end{theorem}

  \pause
  \vspace{0.50cm}
  \red{对任意 $(a, b)$,}
  \setcounter{equation}{0}
  \begin{align}
    &(a, b) \in (R \circ S)^{-1} \\[6pt]
    \uncover<3->{\iff& (b, a) \in R \circ S \\[6pt]}
    \uncover<4->{\iff& \exists c.\; (b, \blue{c}) \in S \land (\blue{c}, a) \in R \\[6pt]}
    \uncover<5->{\iff& \exists c.\; (\purple{c}, b) \in S^{-1} \land (a, \purple{c}) \in R^{-1} \\[6pt]}
    \uncover<6->{\iff& (a, b) \in S^{-1} \circ R^{-1}}
  \end{align}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{theorem}
    \[
      (R \circ S) \circ T = R \circ (S \circ T)
    \]
  \end{theorem}

  \pause
  \red{对任意 $(a, b)$,}
  \setcounter{equation}{0}
  \begin{align}
    &(a, b) \in (R \circ S) \circ T \\[6pt]
    \onslide<3->{\iff& \exists c.\; \Big((a, c) \in T \land (c, b) \in R \circ S\Big) \\[6pt]}
    \onslide<4->{\iff& \exists c.\; \Big((a, c) \in T \land \red{\big(}\exists d.\; (c, d) \in S \land (d, b) \in R\red{\big)}\Big) \\[6pt]}
    \onslide<5->{\red{\iff}& \exists d.\; \exists c.\; \Big((a, c) \in T \land (c, d) \in S \land (d, b) \in R\Big) \\[6pt]}
    \onslide<6->{\iff& \exists d.\; \Big(\red{\big(}\exists c.\; (a, c) \in T \land (c, d) \in S\red{\big)} \land (d, b) \in R\Big) \\[6pt]}
    \onslide<7->{\iff& \exists d.\; \Big((a, d) \in S \circ T \land (d, b) \in R\Big) \\[6pt]}
    \onslide<8->{\iff& (a, b) \in R \circ (S \circ T)}
  \end{align}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.70\textwidth}{figs/wulin-relation}

  \begin{center}
    {\large \blue{\bf 燕小六:} ``帮我照顾好我七\red{舅姥爷}和我外甥女''}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \blue{``舅姥爷'': 姥姥/外婆的兄弟}
  \end{center}

  \pause
  \[
    G = \set{(a,b) \mid a \text{ 是}\; b \text{ 的舅姥爷}}
  \]

  \pause
  \[
    B = \set{(a, b) \mid a \text{ is the brother of } b}
  \]
  \[
    M = \set{(a, b) \mid a \text{ is the mother of } b}
  \]

  \pause
  \[
    \blue{G = (M \circ M) \circ B}
  \]

  \pause
  \[
    G = \blue{(M \circ M) \circ B} = \red{M \circ (M \circ B)}
  \]

  \pause
  \vspace{0.30cm}
  \begin{center}
    \red{``舅姥爷'': 妈妈的舅舅}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{theorem}[关系的复合]
    \[
      (X \cup Y) \circ Z = (X \circ Z) \cup (Y \circ Z)
    \]

    \[
      (X \cap Y) \circ Z \subseteq (X \circ Z) \cap (Y \circ Z)
    \]
  \end{theorem}
\end{frame}
%%%%%%%%%%%%%%%