% If you are working from this template to just write up your own
% solutions, I'm trying to keep it simple for you and there are only a
% few places you need to edit. On line 43 there's a place where the
% phrase "YOUR NAME HERE" appears; change it to your actual
% name. Several places below there are places where the phrase "YOUR
% ANSWER HERE" appears, and directly below (or replacing) those lines
% are good places to put your answers.
%
% One important thing you need to do, however (due to the complicated
% way I use a single form to produce both the question sheets and
% solution writeups) is to make sure that you keep the word 'solution'
% in your filename, or else your answers won't be printed at all.
\documentclass[12pt]{article}
 
\usepackage[margin=0.7in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{tikz}
\usepackage{substr}

\usepackage{hyperref}

\IfSubStringInString{\detokenize{solution}}{\jobname}{%
  % Solutions
  \newcommand\qfill{}
  \newcommand\qpage{}
  \newcommand\qonly[1]{}
  \newcommand\answer[1]{#1}
  \newcommand\question[1]{{\em #1}}
  \newcommand\rubric[1]{}
}
{%
  % Question sheets
  \newcommand\qfill{\vfill}
  \newcommand\qpage{\newpage}
  \newcommand\qonly[1]{#1}
  \newcommand\answer[1]{}
  \newcommand\question[1]{#1}
  \newcommand\rubric[1]{}
}

\pagestyle{fancy}
\lhead{MATH 311-01}
\chead{Problem Set \#9\answer{ solutions}}
\rhead{\answer{}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due April 6, 2017}}

\newtheorem{prop}{Proposition}

% The command below redefines \neg (the logical negation character)
% to be a big tilde, in line with the usage in the book. Comment it
% out if you prefer the more traditional negation symbol.
\renewcommand*{\neg}{\mathord{\sim}}

\begin{document}
\begin{enumerate}
\item \question{For the following investigations, consider relations
    $R$ and $R'$ on a set $S$ such that $R\subseteq R'\subseteq
    S\times S$.}

  \begin{enumerate}
  \item \question{If $R$ is reflexive, is it necessarily the case that
      $R'$ is reflexive? Prove your assertion if true; furnish a
      counterexample if not.}

    \answer{This will always be true.
      \begin{proof}
        Given that $R$ is a reflexive relation on $S$, we shall seek
        to prove that $R'$ is a reflexive relation on $S$; in other
        words, we wish to show that for any $x\in S$, it is true that
        $x\mathrel{R'}x$.

        By reflexivity of $R$, we know that for any $x\in S$, it is
        the case that $x\mathrel Rx$, or in other words that $(x,x)\in
        R$. Since $R\subseteq R'$, we thus know that $(x,x)\in R'$, so
        that $x\mathrel{R'}x$.
      \end{proof}
    }

  \item \question{If $R$ is symmetric, is it necessarily the case that
      $R'$ is symmetric? Prove your assertion if true; furnish a
      counterexample if not.}

    \answer{This is not necessarily true. As a very simple case,
      consider $S=\{1,2\}$, $R=\emptyset$, and $R'=\{(1,2)\}$. $R$ is
      a vacuously symmetric relation, and $R\subseteq R'$, but $R'$ is
      nonsymmetric since $(1,2)\in R'$ but $(2,1)\notin R'$.

      Other, less vacuous examples are also possible.}

  \item \question{If $R$ is transitive, is it necessarily the case that
      $R'$ is transitive? Prove your assertion if true; furnish a
      counterexample if not.}

    \answer{This is not necessarily true. As a very simple case,
      consider $S=\{1,2,3\}$, $R=\emptyset$, and
      $R'=\{(1,2),(2,3)\}$. $R$ is a vacuously symmetric relation, and
      $R\subseteq R'$, but $R'$ is nonsymmetric since $(1,2)\in R'$
      and $(2,3)\in R'$ but $(1,3)\notin R'$.

      Other, less vacuous examples are also possible.}
  \end{enumerate}

\item \question{Let $S=\{1,2,3,4\}$. Either by explicitly constructing
    the relation as a set of ordered pairs, or by specifying the
    circumstances under which two elements of $S$ are related, fully
    describe a relation satisfying each of the eight conditions below,
    and briefly explain why your relation satisfies the conditions.}
  \begin{enumerate}
  \item \question{A relation $R_1$ on $S$ which is non-reflexive,
      non-symmetric, and non-transitive.}

    \answer{A minimal explicit construction would be
      $R_1=\{(1,2),(2,3)\}$. This is nonreflexive since $(1,1)\notin
      R_1$, nonsymmetric since $(1,2)\in R_1$ but $(2,1)\notin R_1$, and
      nontransitive since both $(1,2)$ and $(2,3)$ are in $R_1$ but
      $(1,3)$ is not.

      A descriptive construction might be that, for instance, $x$ is
      related to $y$ when $y=x+1$; this has the same arguments for
      satisfying the properties as are given above.}

  \item \question{A relation $R_2$ on $S$ which is non-reflexive,
      non-symmetric, and transitive.}

    \answer{A minimal explicit construction would be
      $R_2=\{(1,2)\}$. This is nonreflexive since $(1,1)\notin R_2$,
      and nonsymmetric since $(1,2)\in R_2$ but $(2,1)\notin R_2$. It will
      be vacuously transitive, however: since there are no $a$, $b$,
      and $c$ suct that both $(a,b)$ and $(b,c)$ are in $R_2$, the
      premise of the transitivity condition is never met and the
      condition as a whole is vacuously true.

      A good descriptive construction, which works both for a relation
      on $S$ and a relation on sets of at least two numbers generally,
      is to establish that $x$ is related to $y$ when $x<y$ (or,
      alternatively, when $x>y$). This is well-known to be a
      transitive relation, but is also explicitly non-symmetric and
      non-reflexive.}

  \item \question{A relation $R_3$ on $S$ which is non-reflexive,
      symmetric, and non-transitive.}

    \answer{A minimal explicit construction would be
      $R_3=\{(1,2),(2,1),(2,3),(3,2)\}$. This is nonreflexive since
      $(1,1)\notin R_3$ and nontransitive since both $(1,2)$ and
      $(2,3)$ are in $R_3$ but $(1,3)$ is not. However, it is symmetric
      since for each $(a,b)\in R$, it is also the case that $(b,a)$ is
      an element of $R_3$.

      A possible descriptive construction might be that $x$ relates to
      $y$ if and only if $|x-y|=1$; the required difference means no
      $x$ is related to itself, while the absolute value on the
      difference measurement guarantees symmetry, and the case of $1$,
      $2$, and $3$ serves to illustrate non-transitivity.

      A common relation matching these criteria is the symmetric
      inequality, that $x$ relates to $y$ when $x\neq y$.}

  \item \question{A relation $R_4$ on $S$ which is non-reflexive,
      symmetric, and transitive.}

    \answer{Examples of this end up being necessarily very limited. In
      fact, if all four elements of $S$ \emph{appear} in a symmetric,
      transitive relation, then the relation is intrinsically
      reflexive. So only a relation in which at least one element of
      $S$ does not participate at all can fit into this category. The
      simplest such would be $R_4=\emptyset$, which is vacuously
      symmetric and transitive. If you desire a less vacuous example,
      something like $R_4=\{(1,1),(1,2),(2,1),(2,2),(3,3)\}$ will do,
      since it is straightforwardly shown to be symmetric,
      exhaustively shown to be transitive, and is nonreflexive since
      $(4,4)\notin R_4$.}

  \item \question{A relation $R_5$ on $S$ which is reflexive,
      non-symmetric, and non-transitive.}

    \answer{A minimal explicit construction would be
      $R_5=\{(1,1),(1,2),(2,2),(2,3),(3,3),(4,4)\}$. This is reflexive
      since every $(x,x)\in R_5$, nonsymmetric since $(1,2)\in R_5$ but
      $(2,1)\notin R_5$, and nontransitive since both $(1,2)$ and
      $(2,3)$ are in $R_5$ but $(1,3)$ is not.

      A descriptive construction might be that, for instance, $x$ is
      related to $y$ when $x\leq y\leq x+1$; this has the same
      arguments for satisfying the properties as are given above.}


  \item \question{A relation $R_6$ on $S$ which is reflexive,
      non-symmetric, and transitive.}

    \answer{A minimal explicit construction would be
      $R_6=\{(1,1),(1,2),(2,2),(3,3),(4,4)\}$. This is This is
      reflexive since every $(x,x)\in R_6$ and nonsymmetric since
      $(1,2)\in R_6$ but $(2,1)\notin R_6$. It will be transitive for
      near-vacuous reasons, however: since there are no distinct $a$,
      $b$, and $c$ suct that both $(a,b)$ and $(b,c)$ are in $R$, the
      premise of the transitivity condition is only met by expressions
      of the form $(a,a)$ and $(a,c)$, or $(a,c)$ and $(c,c)$, and in
      both cases the conclusion is identical to a premise.

      A good descriptive construction, which works both for a relation
      on $S$ and a relation on sets of at least two numbers generally,
      is to establish that $x$ is related to $y$ when $x\leq y$ (or,
      alternatively, when $x\leq y$). This is well-known to be a
      transitive relation, and the nonstrictness of the inequality
      makes it reflexive, but it is also explicitly non-symmetric.}

  \item \question{A relation $R_7$ on $S$ which is reflexive,
      symmetric, and non-transitive.}

    \answer{A minimal explicit construction would be
      $R_7=\{(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3),(4,4)\}$. This is
      reflexive since each $(x,x)\in R_7$ and nontransitive since both
      $(1,2)$ and $(2,3)$ are in $R_7$ but $(1,3)$ is not. However, it
      is symmetric since for each $(a,b)\in R_7$, it is also the case
      that $(b,a)$ is an element of $R_7$.

      A possible descriptive construction might be that $x$ relates to
      $y$ if and only if $|x-y|\leq 1$; since $x-x=0$ every
      $x$ is related to itself, while the absolute value on the
      difference measurement guarantees symmetry, and the case of $1$,
      $2$, and $3$ serves to illustrate non-transitivity.}

  \item \question{A relation $R_8$ on $S$ which is reflexive,
      symmetric, and transitive.}

    \answer{Any equivalence relation works here;
      $R_8=\{(1,1),(2,2),(3,3),(4,4)\}$ is the smallest such.}

  \end{enumerate}

  \answer{A point of potential interest: suppose we were to consider
    \emph{every} possible relation on this 4-element set. There are a lot
    of such relations, since there are $4^2=16$ relationships each of
    which could be present or absent, making $2^{16}=65536$ possible
    relations! Here's a list of how they divide into the eight possible
    classes, with references. If you like this breakdown, you'll love MATH
    387.
    \begin{center}
      \begin{tabular}{|c|c|c|r|p{3.5in}}\cline{1-4}
        Reflexive?&Symmetric?&Transitive?&Count&Notes\\\cline{1-4}
        Yes&Yes&Yes&15&Equivalencies of $\{1,2,3,4\}$; see \href{https://oeis.org/A000110}{OEIS A000110}.\\
        Yes&Yes&No&49&$2^6$ reflexive, symmetric relations in total; subtract out equivalences.\\
        Yes&No&Yes&340&Non-equivalent quasi-orderings of $\{1,2,3,4\}$; see \href{https://oeis.org/A000798}{OEIS A000798}.\\
        Yes&No&No&3692&$2^{12}$ reflexive relations in total; subtract out symmetric/transitive.\\
        No&Yes&Yes&37&Equivalencies of proper subsets of $\{1,2,3,4\}$; see \href{https://oeis.org/A000110}{OEIS A000110}.\\
        No&Yes&No&923&$2^{10}$ symmetric relations; subtract out reflexive/transitive.\\
        No&No&Yes&3602&See \href{https://oeis.org/A000110}{OEIS A000110} for transitive relations; subtract symmetric/reflexive\\
        No&No&No&56878&$2^{16}$ relations in total; subtract out reflexive/symmetric/transitive.\\\cline{1-4}
      \end{tabular}
    \end{center}
    So actually if we were to build a relation at random, say, by flipping
    a coin 16 times to determine if each of the 16 relationships hold,
    there's a very good likelihood (about 87\%) that the relation we get
    would not be reflexive, symmetric, or transitive.
  }

\item \question{Let $R$ be a relation on $\mathbb N$ such that $m$
    relates to $n$ if $m$ and $n$ have the same number of factors. In
    other, more technical words, we may explicitly define $R$ as:
    \[R=\bigl\{(m,n)\in\mathbb N\times\mathbb N:|\{d\in\mathbb N:d\mid
    m\}|=|\{d\in\mathbb N:d\mid n\}|\bigr\}\]
  }
  \begin{enumerate}
  \item \question{Prove that $R$ is an equivalence relation.}

    \answer{
      \begin{proof}
        
      \end{proof}
    }

  \item \question{Describe two of the equivalence classes of $R$.}

    \answer{An equivalence class consists of every natural number with
      some specific number of factors. In two cases these classes are
      very easily described: the set of all natural numbers with
      exactly one factor is the finite set $\{1\}$. The set of all
      natural numbers with exactly two factors are defenitionally the
      primes: $\{2,3,5,7,11,13,\ldots\}$.

      A few more exotic ones are the set of natural numbers with
      exactly three factors (the squares of primes):
      $\{4,9,25,49,121,\ldots\}$, or, more convolutedly, those with
      exactly four factors (which are either the products of two
      primes \emph{or} the cube of a prime):
      $\{6,8,10,14,15,21,22,26,27,\ldots\}$.}
  \end{enumerate}
\end{enumerate}

\end{document}
