\documentclass[12pt,oneside]{amsart}
\usepackage{geometry}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
%\usepackage{pdfpages}
\usepackage{enumerate}
\usepackage[all]{xy}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage{appendix}
%\usepackage{caption}
\usepackage{subcaption}
\usepackage{color}
\usepackage{verbatim}
\usepackage{mathtools}
\usepackage{tikz-cd}
\usepackage[section]{placeins}
\usepackage{showkeys}
\usepackage{hyperref}
\usepackage{enumitem}
\usepackage{multicol}
\hypersetup{
  colorlinks=true,
  allcolors=blue,
}

%ENVIRONMENTS
\newtheorem{theorem}{Theorem}
\newtheorem*{theorem*}{Theorem}
\newtheorem{exercise}{Exercise}
\newtheorem*{exercise*}{Exercise}
\newtheorem*{solution}{Solution}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{remark}{Remark}
\newtheorem{conjecture}{Conjecture}
\newtheorem{example}{Example}
\newtheorem{proposition}{Proposition}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{note}{Note}

%OPERATORS
\DeclareMathOperator{\dist}{dist}

%SYMBOLS
\def\a{\alpha}
\def\b{\beta}
\def\m{\mu}
\def\n{\nu}
\def\u{\upsilon}
\def\l{\lambda}
\def\CC{\mathbb{C}}
\def\R{\mathbb{R}}
\def\Q{\mathbb{Q}}
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\T{\mathbb{T}}
\def\H{\mathbb{H}}
\def\S{\Sigma}
\def\s{\sigma}
\def\e{\epsilon}
\def\B{\mathcal{B}}
\def\O{\Omega}
\def\o{\omega}
\def\C{\mathcal{C}}
\def\U{\mathcal{U}}
\def\A{\mathcal{A}}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Homework 9 - Discrete Math Spring 2023}
\author{John Adamski}
\address{Department of Mathematics, Fordham University}
\email{adamski@fordham.edu}
%\address{Department of Mathematics, The City College of New York, CUNY}
%\email{jadamski@ccny.cuny.edu}
\urladdr{www.johnadamski.com}

%\begin{abstract}
%Great stuff!
%\end{abstract}

%\tableofcontents

\maketitle 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem*}\label{11.1.2}
  Let $A = \{1, 2, 3, 4, 5, 6\}$. Write out the relation $R$ that expresses $\mid$ (divides) on $A$. Then illustrate it with a diagram.
\end{theorem*}

\begin{proof}
  By definition,
  \begin{align*}
    R &= \{(x,y) \in A \times A \;:\; x\mid y\} \\
      &= \left\{\begin{array}{l}
        (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), \\
           (2, 2), (2, 4), (2, 6), \\
           (3, 3), (3, 6), \\
           (4, 4), \\
           (5, 5), \\
           (6, 6)
     \end{array}\right\}
  \end{align*}
  \begin{center}\includegraphics[width=.4\textwidth]{11-1-2}
  %\caption{caption}
  \end{center}
\end{proof}

\begin{theorem*}\label{11.1.10}
  Consider the subset $R = (\R\times\R) - \{(x,x) \;:\; x\in\R\} \subset \R\times\R$. What familiar relation on $\R$ is this? Explain.
\end{theorem*}
\begin{proof}
  We see that $R$ contains all ordered pairs of real numbers \textit{except} those with the first and second components/coordinates equal to each other. 
  In other words, $xRy$ if and only if $x\neq y$, i.e. $R$ is the relation $\neq$. 
\end{proof}

\begin{theorem*}\label{11.1.12}
  A subset $R$ of $\R^2$ is indicated by gray shading. State this familar relation on $\R$.
  \begin{center}\includegraphics[width=.25\textwidth]{11-1-12}
  %\caption{caption}
  \end{center}
\end{theorem*}
\begin{proof}
  Since $(x,y)\in R$ if and only if $x\geq y$, we see that $R$ is the relation $\geq$.
\end{proof}

\begin{theorem*}\label{11.1.14}
  A subset $R$ of $\Z^2$ is indicated by gray shading. State this familar relation on $\Z$.
  \begin{center}\includegraphics[width=.25\textwidth]{11-1-14}
  %\caption{caption}
  \end{center}
\end{theorem*}
\begin{proof}
  Since $(x,y)\in R$ if and only if $x< y$, we see that $R$ is the relation $<$.
\end{proof}

\begin{theorem*}\label{11.2.2}
  Consider the relation $R = \{(a,b),(a,c),(c,c),(b,b),(c,b),(b,c) \}$ on the set $A = \{a, b, c\}$. 
  Is $R$ reflexive? Symmetric? Transitive? If a property does not hold, say why.
\end{theorem*}
\begin{proof}The relation $R$ is not reflexive or symmetric, but it is transitive.
  \begin{itemize}%[itemsep=2ex]
    \item $R$ is not reflexive. In order to be reflexive, $R$ would have to contain $(a, a), (b,b)$ and $(c,c)$. But $R$ does not contain $(a,a)$.
    \item $R$ is not symmetric. Since $R$ contains $(a,b)$, in order to be symmetric $R$ would have to also contain $(b,a)$, but it does not.
    The same could be said about $(a,c)\in R$ and $(c,a)\notin R$.
    \item $R$ is transitive.
  \end{itemize}
\end{proof}

\begin{theorem*}\label{11.2.6}
  Consider the relation $R = \{(x,x) \;:\;x\in\Z \}$. 
  Is this $R$ reflexive? Symmetric? Transitive? 
  If a property does not hold, say why. What familiar relation is this?
\end{theorem*}
\begin{proof}
  This relation is reflexive, symmetric, and transitive. It is the familar relation $=$.
\end{proof}

\begin{theorem*}\label{11.2.8}
  Define a relation on $\Z$ as $xRy$ if $|x-y|<1$. 
  Is R reflexive? Symmetric? Transitive? If a property does not hold, say why. What familiar relation is this?
\end{theorem*}
\begin{proof}
  This relation is reflexive, symmetric, and transitive. It is the familar relation $=$.
\end{proof}

\begin{theorem*}\label{11.3.2}
  Let $A = \{a, b, c, d, e\}$. 
  Suppose $R$ is an equivalence relation on $A$. 
  Suppose $R$ has two equivalence classes. 
  Also $aRd, bRc$, and $eRd$. Write out $R$ as a set.
\end{theorem*}
\begin{proof}
  In the diagram below, the black arrows are the specified relations. 
  The red arrows are necessary in order for $R$ to be reflexive.
  The blue arrows are necessary in order for $R$ to be symmetric (they point in the opposite direction as the black arrows). 
  The purple arrows are necessary in order for $R$ to be transitive.
  \begin{center}\includegraphics[width=.4\textwidth]{11-3-2}
  %\caption{caption}
  \end{center}
  Thus,
  \begin{equation*}
    R = \left\{\begin{array}{l}
        (a,d), (b,c), (e,d), \\
        (a,a), (b,b), (c,c), (d,d), (e,e), \\
        (d,a), (c,b), (d,e), \\
        (a,e), (e,a)
     \end{array}\right\}
  \end{equation*}
\end{proof}

\begin{theorem*}\label{11.3.10}
  Suppose $R$ and $S$ are two equivalence relations on a set $A$.
  Prove that $R\cap S$ is also an equivalence relation.
\end{theorem*}
\begin{proof}
  Assume $R$ and $S$ are two equivalence relations on a set $A$.
  In order to show that $R\cap S$ is an equivalence relation, we must show that $R\cap S$ is reflexive, symmetric, and transitive.

  First we show that $R$ is reflexive. Since both $R$ and $S$ are equivalance relations, both $R$ and $S$ are reflexive. 
  Thus, for any $a\in A$, $(a,a)\in R$ and $(a,a)\in S$. 
  It follows that $(a,a)\in R\cap S$, and so $R\cap S$ is reflexive.

  Next we show that $R\cap S$ is symmetric. Since both $R$ and $S$ are equivalence relations, both $R$ and $S$ are symmetric.
  Assume $(a,b)\in R\cap S$. 
  Then, since $(a,b)\in R$ and $R$ is symmetric, $(b,a)\in R$. 
  Also, since $(a,b)\in S$ and $S$ is symmetric, we have $(b,a)\in S$.
  Thus, $(b,a)\in R \cap S$, and so $R\cap S$ is symmetric..

  Finally we show that $R \cap S$ is transitive. Since both $R$ and $S$ are equivalence relations, both $R$ and $S$ are transitive.
  Assume $(a,b), (b,c)\in R \cap S$.
  Then, since $(a,b), (b,c)\in R$ and $R$ is transitive, we have $(a,c)\in R$.
  Similarly, since $(a,b), (b,c)\in S$ and $S$ is transitive, we have $(a,c)\in S$.
  Thus, $(a,c)\in R \cap S$, and so $R\cap S$ is transitive.
\end{proof}

\begin{theorem*}\label{11.4.4}
  Suppose $P$ is a partition of a set $A$. 
  Define a relation $R$ on $A$ by declaring $xRy$ if and only if $x,y\in X$ for some $X\in P$. 
  Prove $R$ is an equivalence relation on $A$. 
  Then prove that $P$ is the set of equivalence classes of $R$.
\end{theorem*}
\begin{proof}
  To begin, let us show that $R$ is an equivalence relation on $A$. 

  First we show that $R$ is reflexive. Let $a$ be any element of $A$.
  Since $P$ is a partition on $A$, by definition $A$ is the union of all subsets in $P$.
  Therefore, $a$ belongs to some $X\in P$.
  Thus, it is true (though redundant) to say that $a,a\in X$ for some $X\in P$, and so $R$ is relexive.
  
  Next we show that $R$ is symmetric. Assume $a,b\in A$ and $aRb$.
  That is, $a,b\in X$ for some $X\in P$. This is clearly equivalent to the statement that $b,a \in X$ for some $X\in P$, and so $bRa$.
  This shows that $R$ is symmetric.
  
  Lastly we show that $R$ is transitive. Assume $aRb$ and $bRc$.
  Then, by definition, there exists some $X\in P$ such that $a,b\in X$ and some $Y\in P$ such that $b,c \in Y$.
  Since $P$ is a partition, by definition, if $X\neq Y$ then $X \cap Y = \emptyset$.
  Equivalently, if $X \cap Y \neq \emptyset$, then $X=Y$ (contrapositive).
  Since $b\in X \cap Y$, it follows that $X \cap Y \neq \emptyset$, and so $X=Y$. 
  Now we see that $a,b,c$ all belong to the same subset $X\in P$ and, in particular, $aRc$.
  This shows that $R$ is transitive and completes the proof that $R$ is an equivalence relation.

  To finish the proof, we must show that $P$ is the set of equivalence classes on $A$.
  By theorem 11.2 in \textit{Book of Proof} by Richard Hammock, the set $C = \{[a] \;:\; a\in A\}$ of equivalence classes of $R$ forms a partition of $A$.
  What remains is to show that this partition $C$ is equal to the partition $P$.
  We do this using definitions and logical equivalences.
  \begin{align*}
  	C &= \{[a] \;:\; a\in A\} \\
  	  &= \{ \{x\in A \;:\; xRa \} \;:\;a \in A\} \\
  	  &= \{ \{x\in A \;:\; x,a\in X, \mbox{ for some } X\in P \} \;:\;a \in A\} \\
  	  &= \{ \mbox{the subset in $P$ that contains $a$} \;:\;a \in A\} \\
  	  &= P
  \end{align*}
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{thebibliography}{99}

%\bibitem{}
%\newblock 
%\newblock 
   
%\end{thebibliography}

\end{document}