hw2.tex

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

%% Page setup
\geometry{
    margin=2cm,
    includehead,
    % includefoot,
    headsep=\baselineskip,
}
\pagestyle{fancy}
\fancyfoot{}
\MakeDoubleHeader% {<l1>}{<l2>}{<r1>}{<r2>}
    {\TextHomeworkEng~\#2}
    {Binary Relations}
    {\TextDiscreteMathEng}
    {\IconFall~Fall 2024}

%% Add custom setup below

%% Macros from physics
\usepackage{physics}

%% Math enquote
\newcommand{\mathenquote}[1]{\text{\enquote{$#1$\kern.3ex}}}

%% Jaccard index
\newcommand{\Jac}{%
    \mathrm{Jac}}

%% Colors for the prime factorization
\colorlet{my-green}{green!60!black}
\colorlet{my-blue}{blue!60!black}

%% Definitions
\declaretheorem[numbered=unless unique]{definition}

%% Algorithms
\usepackage[ruled,linesnumbered,vlined]{algorithm2e}


\begin{document}
\selectlanguage{english}

\setlength{\epigraphwidth}{0.4\textwidth}
\epigraph{\textpzc{In der Mathematik ist die Kunst Fragen zu stellen wertvoller als Probleme zu lösen}}{--- Georg Cantor}

\begin{tasks}
    %% Task: Check properties of relations.
    \item For each given relation $R_i \subseteq {M_i}^2$, determine whether it is \textit{reflexive, irreflexive, coreflexive, symmetric, antisymmetric, asymmetric, transitive, left/right Euclidean, connex}.
    Provide a counterexample for each non-complying property (\eg \enquote{transitivity does not hold for $x,y,z = (3,1,2)$}).
    Organize your answer in a table (\eg columns \--- relations, rows \--- properties).

    \newcommand{\myindex}{\arabic{subtasksi}}

    \begin{multicols}{2}
    \begin{subtasks}
        \item $M_{\myindex} = \Real$ \\
        $x \rel[R_{\myindex}] y \iff \abs{x - y} \leq 1$

        \item $M_{\myindex} = \powerset{\Set{a,b,c}}$ \\
        $R_{\myindex} = \mathenquote{\subseteq}$

        \item $M_{\myindex} = \Set{a,b,c,d}$\quad
        $\relmatrix{R_{\myindex}} = \begin{bsmallmatrix}
            0 & 1 & 0 & 1 \\
            0 & 0 & 0 & 1 \\
            1 & 1 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
        \end{bsmallmatrix}$

        \item $M_{\myindex} = \Set{\text{\enquote{rock}}, \text{\enquote{scissors}}, \text{\enquote{paper}}}$ \\
        $R_{\myindex} = \Set{\Pair{x,y} \given x \text{ beats } y}$

        % \item $M_{\myindex} = \Natural$ \\
        % $R_{\myindex} = \Set{\Pair{x,y} \given x \equiv y \pmod{7}}$

        % \item $M_{\myindex} = \Set{1,2,3,4}$ \\
        % $R_{\myindex} = \Set{\Pair{1,3}, \Pair{1,4}, \Pair{2,3}, \Pair{2,4}, \Pair{3,1}, \Pair{3,4}}$

        % \item $R_{\relindex} = \Set{\Pair{1,1}, \Pair{2,2}, \Pair{3,3}}$

        % \item $R_{\relindex} = \Set{\Pair{3,1}, \Pair{3,2}, \Pair{1,2}}$

        % \item $R_{\relindex} = \Set{\Pair{x,y} \given x < y}$

        % \item $\relmatrix{R_{\relindex}} = \begin{bsmallmatrix}
        %     1 & 0 & 1 \\
        %     1 & 1 & 0 \\
        %     0 & 0 & 1 \\
        % \end{bsmallmatrix}$

        % \item $R_{\relindex} = \Set{\Pair{1,3}, \Pair{2,3}, \Pair{3,1}, \Pair{1,2}}$

        % \item $R_{\relindex} = \Set{\Pair{3,2}, \Pair{2,2}, \Pair{2,3}, \Pair{3,3}}$

        % \item $R_{\relindex} = \Set{\Pair{x,y} \given x^2 + (-y)^3 \congruent[3] 2}$

        % \item $\relmatrix{R_{\relindex}} = \begin{bsmallmatrix}
        %     0 & 0 & 0 \\
        %     0 & 0 & 0 \\
        %     1 & 1 & 0 \\
        % \end{bsmallmatrix}$
    \end{subtasks}
    \end{multicols}


    %% Task: Prove some statements about relation properties.
    \item Prove (rigorously) or disprove (by providing a counterexample) the following statements about arbitrary homogeneous relations $R \subseteq M^2$ and $S \subseteq M^2$:

    \begin{multicols}{2}
    \begin{subtasks}
        \item If $R$ and $S$ are \textit{reflexive}, then $R \intersection S$ is so.
        \item If $R$ and $S$ are \textit{symmetric}, then $R \intersection S$ is so.
        \item If $R$ and $S$ are \textit{transitive}, then $R \intersection S$ is so.
        \item If $R$ and $S$ are \textit{reflexive}, then $R \union S$ is so.
        \item If $R$ and $S$ are \textit{symmetric}, then $R \union S$ is so.
        \item If $R$ and $S$ are \textit{transitive}, then $R \union S$ is so.
    \end{subtasks}
    \end{multicols}


    %% Task: Explore the equinumerosity relation and quotient set.
    \item An equinumerosity relation $\sim$ over sets is defined as follows: $A \sim B \iff \card{A} =\nobreak \card{B}$.

    \begin{subtasks}
        \item Show that $\sim$ is an equivalence relation over finite sets.
        \item Show that $\sim$ is an equivalence relation over infinite sets\footnote{For infinite sets, $\card{A} = \card{B}$ means there is a bijection between $A$ and $B$.}.
        \item Find the quotient set of $\powerset{\Set{a,b,c,d}}$ by $\sim$.
    \end{subtasks}


    %% Task: Explore the Jaccard index.
    \item Let $R_{\theta}$ be a relation of $\theta$-similarity (clearly, $\theta \in [0; 1] \subseteq \Real$) of finite non-empty sets defined as follows: a set~$A$ is said to be \textit{$\theta$-similar} to~$B$ \textit{iff} the Jaccard index $\Jac(A,B) = \frac{\card{A \intersection B}}{\card{A \union B}}$ for these sets is at least~$\theta$, \ie $\Pair{A, B} \in R_{\theta} \iff \Jac(A,B) \geq \theta$.

    \begin{subtasks}
        \item Determine whether $\theta$-similarity is a tolerance relation\footnote{A tolerance relation is a \textit{reflexive} and \textit{symmetric} relation.}.
        \item Determine whether $\theta$-similarity is an equivalence relation.
        \item Draw the graph of a relation $R_{\theta} \subseteq \Set{A_i}^2$, where $\theta = 0.25$, $A_1 = \Set{1,2,5,6}$, $A_2 = \Set{2,3,4,5,7,9}$, $A_3 = \Set{1,4,5,6}$, $A_4 = \Set{3,7,9}$, $A_5 = \Set{1,5,6,8,9}$.
    \end{subtasks}


    % % Task: Explore the characteristic function.
    % \item The characteristic function~$f_S$ of a set~$S$ is defined as follows:
    % \[
    %     f_S(x) = \begin{cases}
    %         1 &\text{if } x \in S \\
    %         0 &\text{if } x \notin S
    %     \end{cases}
    % \]

    % Let~$A$~and~$B$ be finite sets.
    % Show that for all $x \in \universalset$:

    % \begin{subtasks}
    %     \item $f_{\,\overline{A}} (x) = 1 - f_A(x)$
    %     \item $f_{A \intersection B} (x) = f_A(x) \cdot f_B(x)$
    %     \item $f_{A \union B} (x) = f_A(x) + f_B(x) - f_A(x) \cdot f_B(x)$
    %     \item $f_{A \xor B} (x) = f_A(x) + f_B(x) - 2 f_A(x) \cdot f_B(x)$
    % \end{subtasks}


    % Task: Explore the Boolean product of matrices.
    \item Any binary relation $R \subseteq M^2$ can be represented as a zero-one matrix~$\relmatrix{R} = [r_{ij}]$, where the element~$r_{ij}$ is equal to~1 if $\Pair{m_i, m_j} \in R$ and 0~otherwise.
    Boolean product of two square matrices $A = [a_{ij}]$ and $B = [b_{ij}]$ is a matrix $C = A \odot B = [c_{ij}]$ defined as follows: $c_{ij} = \biglornolim_{k} (a_{ik} \land b_{kj})$.
    A~composition of relations $R$ and~$S$ is a relation $S \circ R$ defined as follows: $\Pair{a,b} \in S \circ R \iff \exists c : \Pair{a,c} \in R \land \Pair{c,b} \in S$.
    Show that the matrix representation of the composition of relations $R$ and~$S$ is equal to the Boolean product of the corresponding matrices, \ie $\relmatrix{S \circ R} = \relmatrix{R} \odot \relmatrix{S}$.


    % Task: Find the error in the "proof".
    \item Find the error in the \enquote{proof} of the following \enquote{theorem}.

    \smallskip
    \enquote{\textit{Theorem}}: Let $R$ be a relation on a set $A$ that is symmetric and transitive. Then $R$ is reflexive.

    \smallskip
    \enquote{\textit{Proof}}: Let $a \in A$. Take an element $b \in A$ such that $\Pair{a, b} \in R$. Because $R$ is symmetric, we also have $\Pair{b, a} \in R$. Now using the transitive property, we can conclude that $\Pair{a, a} \in R$ because $\Pair{a, b} \in R$ and $\Pair{b, a} \in R$.


    % Task: Explore the closures.
    \item Give an example of a relation $R$ on the set $\Set{a, b, c}$ such that the symmetric closure of the reflexive closure of the
    transitive closure of~$R$ is not transitive.


    % Task: Explore the equivalence classes.
    \item  Let R be the relation on the set of all colorings of the $2 \times 2$ checkerboard where each of the four squares is colored either \textit{red} or \textit{blue} so that $\Pair{C_1, C_2}$, where $C_1$ and~$C_2$ are $2 \times 2$ checkerboards with each of their four squares colored blue or red, belongs to~$R$ if and only if $C_2$ can be obtained from~$C_1$ either by rotating the checkerboard or by rotating it and then reflecting it.
    \begin{subtasks}
        \item Show that $R$ is an equivalence relation.
        \item What are the equivalence classes of $R$?
    \end{subtasks}


    % Task: Explore the inverse of a composition.
    \item Consider two relations $R \subseteq A \times B$ and $S \subseteq B \times C$.
    Prove that $(S \circ R)^{-1} = R^{-1} \circ S^{-1}$.


    % Task: Composition of injections and surjections.
    \item Prove or disprove the following statements about the functions $f$ and $g$:

    \begin{subtasks}
        \item If $f$ and $g$ are injections, then $g \circ f$ is also an injection.

        \item If $f$ and $g$ are surjections, then $g \circ f$ is also a surjection.

        \item If $f$ and $f \circ g$ are injections, then $g$ is also an injection.

        \item If $f$ and $f \circ g$ are surjections, then $g$ is also a surjection.
    \end{subtasks}


    %% Task: Explore the divisibility relation.
    \item Let $H = \Set{1, 2, 4, 5, 10, 12, 20}$.
    Consider a divisibility relation $R \subseteq H^2$ defined as follows: $x \rel y \iff y \divby x$.

    \begin{subtasks}
        \item Sort $R$ (as a set of pairs) lexicographically\footnote{Lexicographic order for pairs: $\Pair{a,b} \preceq \Pair{a',b'} \iff (a < a') \lor ((a = a') \land (b \leq b'))$. For example, $\Pair{1,2} \preceq \Pair{1,3} \preceq \Pair{2,1}$.}.

        \item Show that $R$ is a partial order.

        \item Determine whether $R$ is a linear (total) order.

        \item Draw the Hasse diagram for a graded poset $\Triple{H, R, \rho}$, where $\rho \colon H \to \NaturalZero$ is a grading function which maps a number $n \in H$ to the sum of all exponents appearing in its prime factorization, \eg $\rho(20) = \rho(2^{\mathcolor{my-green}{2}} \cdot 5^{\textcolor{my-blue}{1}}) = \mathcolor{my-green}{2} + \textcolor{my-blue}{1} = 3$, so the number 20 would have the 3rd rank (bottom-up).

        \item Find the minimal, minimum (least), maximal and maximum (greatest) elements in the poset~$\Pair{H, R}$.
        If there are multiple or none, explain why.

        \item Perform a topological sort\Href{https://en.wikipedia.org/wiki/Topological_sorting} of the poset $\Pair{H, R}$.
    \end{subtasks}


    % Task: Explore the transitive closure.
    \item Prove that the transitive closure $R^{+}$ is in fact transitive.

    \begin{definition}
        $R^{+} = \bigunionclap{n \in \NaturalPlus} R^n$ is a \textit{transitive closure} of $R \subseteq M^2$, where
        \begin{terms}
            \item $R^{k+1} = R^k \circ R$ is a compositional (functional) power\footnote{Note: this \emph{is not a Cartesian power}, despite of the same notation~$R^n$. Another possible notation for compositional power~is~$R^{\circ n}$, but it is too wild to use it here.},
            \item $R^1 = R$,
            \item $S \circ R = \Set{\Pair{x,y} \given \exists z : (x \rel[R] z) \land (z \rel[S] y)}$ is a composition (relative product) of relations $R$ and $S$.
        \end{terms}
    \end{definition}


    % Task: Refinement relation over partitions is a lattice.
    \item Given a set $S$ and two partitions $P_1$ and $P_2$ of~$S$, we define the relation $P_1 \preceq P_2$ as follows: partition~$P_1$ is considered a \textit{refinement} of the partition~$P_2$ if every set in~$P_1$ is a subset of one of the sets in~$P_2$.
    Show that the set of all partitions of a set~$S$ with the refinement relation~$\preceq$ is a lattice.


    % Task: Well-founded relation.
    \item A poset $\Pair{R, \preceq}$ is \emph{well-founded} if there is no infinite decreasing sequence of elements in the poset, that is, elements $x_1, x_2, \dots, x_n$ such that $\dots \prec x_n \prec \dots \prec x_2 \prec x_1$.
    Determine whether the set of strings of lowercase English letters with lexicographic order is well-founded.


    % \item \dots
\end{tasks}

\end{document}