\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}