\documentclass[12pt]{article}
\usepackage[margin=0.7in]{geometry}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\usepackage{fancyhdr}
% lastpage may not be part of your installation; it's a somewhat
% nonstandard package that determines the page number of the last page
% of your document, and allows you to refer to it with
% \pageref{LastPage}. If you don't have it, it can be worked around.
\usepackage{lastpage}
% Uncomment the following line and actually put your name into the
% second pair of braces. This will make LaTeX resolve \studentname
% throughout the document as whatever you put in the braces. Note that
% if you don't uncomment this line, your source will not compile!
\newcommand{\studentname}{}
\pagestyle{fancy}
\lhead{MATH 311-02}
\chead{Problem Set \#5}
% This next line will fail to compile unless you uncomment the
% \newcommand up above!
\rhead{\studentname}
\lfoot{}
% If you're not using lastpage, then comment this command out and use
% the simpler version which is commented out below.
\cfoot{Page \thepage\ of \pageref{LastPage}}
%\cfoot{Page \thepage}
\rfoot{\bf due March 25}
\begin{document}
\begin{enumerate}
\item \textbf{(9 points)} \emph{The following questions will explore
this slightly obscure relation property.}
\begin{definition}
A relation $R$ on a set $S$ is \emph{antireflexive} if and only
if, for all $a\in S$, $(a,a)\notin R$; in other words,
$a\not\mathrel Ra$ for all $a\in S$.
\end{definition}
\begin{enumerate}
\item \textbf{(2 points)} \emph{Demonstrate, either by example or
explanation, that there exist relations which are neither
reflexive nor antireflexive.}
If there is \emph{any} element $a$ of $S$ such that
$a\not\mathrel{R}a$, then $R$ is nonreflexive; likewise, if there
is \emph{any} $b\in S$ such that $b\mathrel{R}b$, then $R$ is not
antireflexive. There are several such relations on sets of 2 or
more elements; the simplest one is $R=\{(b,b)\}$ on the set
$S=\{a,b\}$.
\item \textbf{(7 points)} Prove that for a set $S$, if $R\subseteq
S\times S$ is an antireflexive, symmetric, and transitive
relation, then $R=\emptyset$.
\begin{proof}
We shall proceed by contradiction; suppose $R$ is antireflexive,
symmetric, and transitive, but $R\neq\emptyset$. Since $R$ is
not empty, there is some $(a,b)\in R$, i.e. there are some
$a,b\in S$ so that $a\mathrel{R}b$. By symmetry, it is also true
that $b\mathrel{R}a$. Then transitivity on the two true
statements $a\mathrel Rb$ and $b\mathrel Ra$ yields that
$a\mathrel Ra$, but by antireflexivity, $R$ must also satisfy
the contradictory condition $a\not\mathrel Ra$.
\end{proof}
\end{enumerate}
\item \textbf{(25 points)} \emph{The following proofs concern unions
and intersections of relations; if $R_1$ and $R_2$ are considered
as subsets of $S\times S$, we may take $R_1\cup R_2$ and $R_1\cap
R_2$ to represent the ordinary operations on these sets.}
\begin{enumerate}
\item \textbf{(5 points)} \emph{Prove or disprove that, for
relations $R_1$ and $R_2$ on $S$, if either $R_1$ or $R_2$ is
reflexive, then the relation $R_1\cup R_2$ is reflexive.}
\begin{proposition}
For relations $R_1$ and $R_2$ on the set $S$, if either $R_1$ or
$R_2$ is reflexive, then $R_1\cup R_2$ is reflexive.
\end{proposition}
\begin{proof}
Without loss of generality, we may consider the specific premise
that $R_1$ is reflexive, so that for every element $a$ of $S$,
$(a,a)\in R_1$. Since $R_1\subseteq (R_1\cup R_2)$, it thus
follows that for every element $a$ of $S$, $(a,a)\in(R_1\cup
R_2)$, so $R_1\cup R_2$ is reflexive.
\end{proof}
As a point of interest, the converse is \emph{not} true: $R_1\cup
R_2$ could be reflexive even if each of $R_1$ and $R_2$ are not
themselves reflexive. For instance, if $S=\{a,b\}$,
$R_1=\{(a,a)\}$, and $R_2=\{(b,b)\}$, then neither $R_1$ nor $R_2$
is reflexive, but $R_1\cup R_2$ is.
\item \textbf{(5 points)} \emph{Prove or disprove that, for
relations $R5_1$ and $R_2$ on $S$, if both $R_1$ and $R_2$ are
symmetric, then the relation $R_1\cup R_2$ is symmetric.}
\begin{proposition}
For relations $R_1$ and $R_2$ on the set $S$, if both $R_1$ and
$R_2$ are symmetric, then $R_1\cup R_2$ is symmetric.
\end{proposition}
\begin{proof}
Symmetry of $R_1\cup R_2$ is equivalent to the implication that
if $(a,b)\in(R_1\cup R_2)$, then $(b,a)\in(R_1\cup R_2)$. We may
show that an assertion is true by assuming its premise and
working to its conclusion; thus we may take as an overall
premise for our proof the facts that $R_1$ is symmetric, $R_2$
is symmetric, and that some $(a,b)\in(R_1\cup R_2)$; from this
we hope to prove that $(b,a)\in(R_1\cup R_2)$.
Since $(a,b)\in(R_1\cup R_2)$, either $(a,b)\in R_1$ or
$(a,b)\in R_2$. Without loss of generality we may consider the
case $(a,b)\in R_1$. Since $R_1$ is symmetric, it thus follows
that $(b,a)\in R_1$, and since $R_1\subseteq(R_1\cup R_2)$, it
follows that $(b,a)\in(R_1\cup R_2)$.
\end{proof}
\item \textbf{(5 points)} \emph{Prove or disprove that, for
relations $R_1$ and $R_2$ on $S$, if both $R_1$ and $R_2$ are
transitive, then the relation $R_1\cup R_2$ is transitive.}
We disprove the above statement by counterexample. Consider, for
example, the following relations on the real numbers:
$R_1=\{(a,b)\in\mathbb R\times\mathbb R:a**b\}$. Demonstrably $R_1$
and $R_2$ are each transitive, since both the ``less than'' and
``greater than'' relations are in fact transitive, but $R_1\cup
R_2=\{(a,b)\in\mathbb R\times\mathbb R:a\neq b\}$ is not
transitive (as a specific example, $(1,3)\in R_1\cup R_2$ and
$(3,1)\in R_1\cup R_2$, but $(1,1)\notin R_1\cup R_2$).
\item \textbf{(5 points)} \emph{Prove that for equivalence relations
$R_1$ and $R_2$ on $S$, $R_1\cap R_2$ is an equivalence relation
\emph{(note: this is the intersection, whereas the previous
questions discussed the union)}.}
We shall prove reflexivity, symmetry, and transitivity, mostly by
modifying our above proofs (hurrah for copy and paste!):
\begin{proposition}
For relations $R_1$ and $R_2$ on the set $S$, if both $R_1$ and
$R_2$ are equivalence relations, then $R_1\cup R_2$ is an
equivalence relation.
\end{proposition}
\begin{proof}[Proof of reflexivity]
Since both $R_1$ and $R_2$ are reflexive, it follows that for
every element $a$ of $S$, $(a,a)\in R_1$ and $(a,a)\in
R_2$. Thus, for every element $a$ of $S$, $(a,a)\in R_1\cap
R_2$, so $R_1\cap R_2$ is reflexive.
\end{proof}
\begin{proof}[Proof of symmetry]
Symmetry of $R_1\cap R_2$ is equivalent to the implication that
if $(a,b)\in(R_1\cap R_2)$, then $(b,a)\in(R_1\cap R_2)$. We may
show that an assertion is true by assuming its premise and
working to its conclusion; thus we may take as an overall
premise for our proof the facts that $R_1$ is symmetric, $R_2$
is symmetric, and that some $(a,b)\in(R_1\cap R_2)$; from this
we hope to prove that $(b,a)\in(R_1\cap R_2)$.
Since $(a,b)\in(R_1\cap R_2)$, both $(a,b)\in R_1$ and $(a,b)\in
R_2$. Since both $R_1$ and $R_2$ are symmetric, it thus follows
respectively that $(b,a)\in R_1$ and $(b,a)\in R_2$. Thus
$(b,a)\in(R_1\cup R_2)$.
\end{proof}
\begin{proof}[Proof of transitivity]
Transitivity of $R_1\cap R_2$ is equivalent to the implication
that if $(a,b)\in(R_1\cap R_2)$ and $(b,c)\in(R_1\cap R_2)$,
then $(a,c)\in(R_1\cap R_2)$. We may show that an assertion is
true by assuming its premise and working to its conclusion; thus
we may take as an overall premise for our proof the facts that
$R_1$ is transitive, $R_2$ is transitive, that some
$(a,b)\in(R_1\cap R_2)$ and $(b,c)\in(R_1\cap R_2)$; from this
we hope to prove that $(a,c)\in(R_1\cap R_2)$.
Since $(a,b)\in(R_1\cap R_2)$, both $(a,b)\in R_1$ and $(a,b)\in
R_2$; likewise from $(b,c)\in(R_1\cap R_2)$, both $(b,c)\in R_1$
and $(b,c)\in R_2$. Since both $R_1$ and $R_2$ are transitive,
it follows from the fact that $(a,b)\in R_1$ and $(b,c)\in R_1$
that $(a,c)\in R_1$ and from the fact that $(a,b)\in R_2$ and
$(b,c)\in R_2$ that $(a,c)\in R_2$. Thus $(a,c)\in(R_1\cup
R_2)$.
\end{proof}
\item \textbf{(5 points)} \emph{If $x\in S$ and $R_1$ and $R_2$ are
equivalence relations of $S$, what is the relationship between
the equivalence classes of $x$ with respect to $R_1$, $R_2$, and
$R_1\cap R_2$?}
Let us denote the above equivalence classes $[x]_{R_1}=\{s\in
S:(x,s)\in R_1\}$, $[x]_{R_2}=\{s\in S:(x,s)\in R_2\}$, and
$[x]_{R_1\cap R_2}=\{s\in S:(x,s)\in R_1\cap R_2\}$. Since the
condition $(x,s)\in R_1\cap R_2$ is satisfied if and only if
$(x,s)$ is an element of both $R_1$ and $R_2$ --- i.e., when $s\in
[x]_{R_1}$ and $s\in [x]_{R_2}$ --- it is fairly easy to see that
$[x]_{R_1\cap R_2}=[x]_{R_1}\cap [x]_{R_2}$.
\end{enumerate}
\item \textbf{(6 points)} \emph{Prove or disprove and salvage if
possible: for $[a],[b]\in\mathbb Z_n$ for a positive integer $n$,
if $[a]\cdot [b]=0$, then either $[a]=[0]$ or $[b]=[0]$.}
This is a clearly false statement in general: considering $\mathbb
Z_6$, we might note that $[2]\cdot[3]=[6]=[0]$, but that neither the
congruence class $[2]$ nor the congruence class $[3]$ is identical
to the congruence class $[0]$. However, this weaker version can
be proven:
\begin{proposition}
For $[a],[b]\in\mathbb Z_n$ for a prime positive integer $n$,
if $[a]\cdot [b]=[0]$, then either $[a]=[0]$ or $[b]=[0]$.
\end{proposition}
\begin{proof}
Definitionally, $[a]\cdot [b]=[ab]$, so given that $[ab]=[0]$, it
follows that $ab\equiv 0\pmod n$, or alternatively that
$n\mid(ab-0)$. From a result in question 1(b) of problem set \#3,
we can derive from prime $n$ that if $n\mid ab$ then either $n\mid
a$ or $n\mid b$. If $n\mid a$, then $a\equiv 0\pmod n$, so
$[a]=[0]$; likewise for $b$.
\end{proof}
\item \textbf{(4 point bonus)} \emph{Prove that for a positive integer
$n$, the perfect squares lie in at most
$\left\lceil\frac{n+1}2\right\rceil$ different congruence classes
modulo $n$.}
It is easiest to argue this in terms of two separate cases: when $n$
is even, there are no more than $\frac n2+1$ congruence classes
containing perfect squares, and when $n$ is odd, there are no more
than $\frac{n+1}2$ congruence classes containing perfect
squares. First, however, let us note that for any $k$, when
considerign the elements of $\mathbb Z_n$, it is the case that
$[k^2]=[k\cdot k]=[k]\cdot [k]$, and since there are only $n$
different values for $[k]$, it is easy to calculate the specific
classes which can contain squares by exhaustively considering each
$[k]\cdot[k]$. For instance, modulo 10, we might look at the
following 10 products of congruence classes:
\begin{align*}
[0]\cdot[0]&=[0]\\
[1]\cdot[1]&=[1]\\
[2]\cdot[2]&=[4]\\
[3]\cdot[3]&=[9]\\
[4]\cdot[4]=[16]&=[6]\\
[5]\cdot[5]=[25]&=[5]\\
[6]\cdot[6]=[36]&=[6]\\
[7]\cdot[7]=[49]&=[9]\\
[8]\cdot[8]=[64]&=[4]\\
[9]\cdot[9]=[81]&=[1]\\
\end{align*}
so, for instance, every square is congruent to 0, 1, 4, 5, 6, or 9 modulo 10.
The above example illuminates our overall proof strategy. Note that
each $[k^2]$ and $[(n-k)^2]$ lie in the same congruence class, which
is easy to show: $[(n-k)^2]=[n^2-2nk+k^2]=[k^2]$, since $n^2-2nk$ is
a multiple of $n$, so as a general rule we can guarantee that two
distinct congruence classes have the same square.
\begin{proposition}
For a positive integer $n$, the perfect squares lie in at most
$\left\lceil\frac{n+1}2\right\rceil$ different congruence classes
modulo $n$.
\end{proposition}
\begin{proof}
In the course of this proof, we shall use $[k]$ to represent the
congruence class of $k$ modulo $n$, and conventionally will
consider specifically the labels $\mathbb
Z_n=\{[0],[1],[2],\ldots,[n-1]\}$. For any integer $k$, as
demonstrated prior to this proof, if $k\in[\ell]$, then
$k^2\in[\ell^2]$, so the congruence classes containing perfect
squares are specifically $[0^2]$, $[1^2]$, \ldots, $[(n-1)^2]$. It
was seen prior to this proof that $[k^2]=[(n-k)^2]$, so we may be
certain that some of the above-listed congruence classes are in
fact identical. How many of them we can apply this rule to depends
on the parity of $n$:
\textbf{Case I: $n$ is even.} Let $n=2s$, where $s$ is a positive
integer. Then $[1^2]=[(2s-1)^2]$, $[2^2]=[(2s-2)^2]$, and so forth
up to $[(s-1)^2]=[(s+1)^2]$. We may thus guarantee that there are
at least $s-1$ identical pairs among the list $[0^2]$, $[1^2]$,
\ldots, $[(n-1)^2]$. Thus there are no more than
$n-(s-1)=s+1=\frac n2+1$ distinct congruence classes in this list.
\textbf{Case II: $n$ is odd.} Let $n=2s+1$, where $s$ is a
non-negative integer. Then $[1^2]=[(2s)^2]$, $[2^2]=[(2s-1)^2]$,
and so forth up to $[s^2]=[(s+1)^2]$. We may thus guarantee that
there are at least $s$ identical pairs among the list $[0^2]$,
$[1^2]$, \ldots, $[(n-1)^2]$. Thus there are no more than
$n-s=s+1=\frac{n+1}2$ distinct congruence classes in this list.
\end{proof}
In fact, when $n$ is prime, there are exactly
$\left\lceil\frac{n+1}2\right\rceil$ congruence classes containing
squares; these are called \emph{quadratic residues}. There are
simple rules (with rather advanced proofs) for determining which
numbers are quadratic residues; the entire theory is detailed
elsewhere under the name of \emph{quadratic reciprocity}.
\end{enumerate}
\vfill
\begin{center}
\fbox{
\begin{minipage}{6in}
Ha rossz kedvem van, matematiz\'alok, hogy j\'o kedvem
legyen. Ha j\'o kedvem van, matematiz\'alok, hogy megmaradjon a
j\'o kedvem. [When I'm in a bad mood, I do mathematics, so that
my mood becomes good. When I'm in a good mood, I do mathematics,
so that my mood stays good.] \hfill ---Alfr\'ed R\'enyi
\end{minipage}
}
\end{center}
\end{document}**