\documentclass {exam}
\usepackage {xypic}
\pagestyle {headandfoot}
\lfoot {\oddeven {}{Page \thepage \space of \numpages }}
\cfoot {}
\rfoot {\oddeven {Page \thepage \space of \numpages }{}}
\pointsinmargin \boxedpoints \addpoints
\newcommand \solution {\par \textbf {Solution:}\enspace }
\begin {document}
\noindent \textbf{MATH 112}\hfill
\textbf{Week 4 homework}\hfill
\textbf{Due 2003 August 26}
\vskip 12pt plus 4pt minus 4pt
\begin {questions}
\question [3]
Give an example of a binary relation
that is both symmetric and antisymmetric.
\solution
You only need a single example to solve this problem,
but I'll give a general explanation.

Suppose that $\sim$ is such a relation and $x \sim y$ is true.
Then because $\sim$ is symmetric, $y \sim x$ is also true.
But because $\sim$ is antisymmetric, $x$ and $y$ must be equal.
So for any relation that's both symmetric and antisymmetric,
$x \sim y$ is only possible if $x = y$.

On the other hand, suppose that $\sim$ is a relation
such that $x \sim y$ only happens when $x = y$.
Then if $x \sim y$, we know that $x = y$,
so substituting this equality into the relation $x \sim y$,
we see that $y \sim x$.
Thus $\sim$ is symmetric.
On the other hand, if $x \sim y$ and $y \sim x$,
then certainly we know that $x = y$.
Thus $\sim$ is antisymmetric.

So to sum up, a relation $\sim$ is simultaneously symmetric and antisymmetric
if and only if $x \sim y$ implies $x = y$.
So now we need to find just one example of such a relation.
The easiest to think of is probably just $=$ itself!
The equality relation is both symmetric and antisymmetric.
Another good example is the empty relation, which is always false;
then symmetry and antisymmetry are requirements that never apply,
so they are always satisfied.
Both of these relations make sense on any set.
\question [4]
State the definition of \textbf{total order}, or \textbf{linear order}.
How many linear orders are there on an $n$-element set $A$?
\solution
A total order $\le$ on a set $A$
is a partial order on $A$
such that given any elements $x$ and $y$ of $A$,
either $x \le y$ or $y \le x$.

Now suppose that $|A| = n$.
To get a linear order on $A$,
first pick the element at the bottom;
this can be done in $n$ ways.
The next element can be chosen in $n - 1$ ways,
and so on;
until finally the last element must be at the top,
which is only $1$ possibility.
So the total number of linear orders
is $n(n - 1)(n - 2)\cdots(2)(1) = n!$.

I've mentioned this informally in class several times,
that $n!$ measures the number of ways to order $n$ items.
Now you see that all of the `ordered' stuff in the counting material
is about \textit{linear\/} orders.
Partial orders are more general.
\question [3]
Find an example of a set $X$
and binary relations $R$ and $S$ on $X$
such that $R$ and $S$ are symmetric but $R \circ S$ is not symmetric.
\solution
For the simplest example, let $X$ be the set $\{0,1,2\}$.
Then let $R$ hold for $(0,1)$ and $(1,0)$ but nothing else;
and let $S$ hold for $(1,2)$ and $(2,1)$ but nothing else.
Then $R \circ S$ holds only for $(2,0)$, \textit{not\/} for $(0,2)$.
So $R \circ S$ is not symmetric,
even though $R$ and $S$ are.
\question
The symmetric difference of two sets $A$ and $B$ is the
set $A \oplus B$ consisting of the elements of $A$ or
$B$ which are not in both $A$ and $B$. Define a relation $\sim$ on
sets so that $A \sim B$ if and only if $A \oplus B$ is the empty set.
\begin {parts}
\part [2]
Is $\sim$ reflexive?
\solution
The elements of $A$ or $A$ are simply the elements of $A$.
And the elements of $A$ and $A$ are again the elements of $A$.
Since nothing is in $A$ but not in $A$,
it follows that $A \oplus A$ is empty, so $A \sim A$.
Therefore yes, $\sim$ is reflexive.
\part [3]
Is $\sim$ symmetric, antisymmetric, both, or neither?
\solution
If $A \sim B$, then everything in $A \cup B$ is in $A \cap B$.
But $A \cup B = B \cup A$ and $A \cap B = B \cap A$.
Thus everything in $B \cup A$ is in $B \cap A$, so $B \sim A$.
Therefore, $\sim$ is symmetric.

Next, if $A \sim B$ and $B \sim A$,
then $A \cup B$ is a subset of $A \cap B$,
so $A \subseteq A \cup B \subseteq A \cap B \subseteq B$.
Also, anything in $B \cup A$ is a subset of $B \cap A$,
so $B \subseteq B \cup A \subseteq B \cap A \subseteq A$.
Since $A \subseteq B$ and $B \subseteq A$,
it follows that $A = B$.
Therefore, $\sim$ is also antisymmetric.
\part [3]
Is $\sim$ transitive?
\solution
Suppose that $A \sim B$ and $B \sim C$.
In other words, $A \cup B \subseteq A \cap B$
and $B \cup C \subseteq B \cap C$.
Now, $A \subseteq A \cup B \subseteq A \cap B \subseteq B
\subseteq B \cup C \subseteq B \cap C \subseteq C$,
so anything in $A$ is in $C$ as well.
On the other hand, $C \subseteq B \cup C \subseteq B \cap C \subseteq B
\subseteq A \cup B \subseteq A \cap B \subseteq A$,
so anything in $C$ is in $A$ as well.
Thus, anything in either $A$ or $C$ belongs to both $A$ and $C$,
so $A \sim C$.
Therefore, $\sim$ is transitive.
\part [2]
Is $\sim$ an equivalence relation, a partial order, both, or neither?
\solution
Since $\sim$ is reflexive, symmetric, and transitive,
this means that $\sim$ is an equivalence relation.
Also, since $\sim$ is reflexive, antisymmetric, and transitive,
this means that $\sim$ is a partial order as well.
\end {parts}
There is also a quicker way to solve this problem,
which is to realise that $A \oplus B$ is empty
if and only if $A$ and $B$ are equal.

To prove this, suppose first that $A \oplus B$ is empty.
Then if $x \in A$, certainly $x \in A \cup B$,
so by our assumption that $A \oplus B$ is empty,
we have $x \in A \cap B$, so $x \in B$.
A completely analogous argument
shows that if $x \in B$, then $x \in A$.
Thus $A$ and $B$ have precisely the same elements.

Conversely, if $A = B$,
then $A \cup B$ and $A \cap B$ are also both equal to $A = B$.
So $A \oplus B$ is empty.

Thus $\sim$ has secretly been the equality relation all along,
and that relation is refelexive, symmetric, antisymmetric, and transitive.
In particular, it's both an equivalence relation and a partial order.

On the other hand,
the only relation (on a given set)
that's both an equivalence relation \textit{and\/} a partial order
is the equality relation (on that set).
So the individual parts in this question
prove, altogether, that $\sim$ is the same relation as $=$.
\question
On the set $\mathbf{Z}$ of integers,
consider the relations $\equiv_{4}$ and $\equiv_{6}$,
respectively the relations for modular arithmetic modulo $4$ and modulo $6$.
Thinking of these relations as sets, find:
\begin {parts}
\part [3]
$\equiv_{4} \cup \equiv_{6}$.
\solution
This relation holds for $m$ and $n$
whenever $m$ and $n$ are equivalent either modulo $4$ \textit{or\/} modulo $6$.
In the first case, $\frac{1}{4}(m - n)$ is an integer $k$.
In the other case, $\frac{1}{6}(m - n)$ is an integer $l$.
In either case, $\frac{1}{2}(m - n)$ is an integer $m$.
Notice that $m = 2k$ in the first case and $m = 3l$ in the other case.
So $\equiv_{4} \cup \equiv_{6}$ holds for $(m,n)$
if $m$ and $n$ are equivalent modulo $2$
and \textit{furthermore}, the integer $\frac{1}{2}(m - n)$
is either even or a multiple of $3$.
\part [3]
$\equiv_{4} \cap \equiv_{6}$.
\solution
This relation holds for $m$ and $n$
whenever $m$ and $n$ are equivalent both modulo $4$ \textit{and\/} modulo $6$.
For the first reason, $\frac{1}{4}(m - n)$ is an integer $k$.
For the other reason, $\frac{1}{6}(m - n)$ is an integer $l$.
This is certainly true if $\frac{1}{12}(m - n)$ is an integer.
On the other hand, since $m := \frac{1}{2}(m - n)$
is both even (specifically $2k$) and a multiple of $3$ (specifically $3l$),
it follows that $m$ is a multiple of $6$.
Thus $\frac{1}{12}(m - n)$ must really be an integer.
Therefore, $\equiv_{4} \cap \equiv_{6}$ is simply $\equiv_{12}$.
\end {parts}
Can you describe these as equivalence modulo some other number?
\question
Let $R$ be the binary relation on the set of people
given by $R(a,b)$ iff $a$ is a parent of $b$.
Then we know that $R^{2} = R \circ R$ is the relation
`$a$ is a grandparent of $b$'.
Similarly describe:
\begin {parts}
\part [2]
$R^{3}$.
\solution
$R^{3} = R \circ R \circ R$ is the relation
`$a$ is a great-grandparent of $b$'.
\part [3]
the transitive closure of $R$.
\solution
This is $R$ or $R^{2}$ or $R^{3}$ or so on,
in other words `$a$ is an ancestor of $b$'.
\end {parts}
\question \relax [\textsl{Preorders.}]
A \textbf{preorder} on a set $X$
is a binary relation on $X$ that is both reflexive and transitive.
If $\ll$ is a preorder on $X$,
then define an equivalence relation $\equiv$ on $X$
by saying that $x \equiv y$ if both $x \ll y$ and $y \ll x$.
Then define a relation $\leq$ on $X/{\equiv}$
by saying that $[x] \leq [y]$ if $x \ll y$.
\begin {parts}
\part [2]
Show that $\leq$ is really well-defined.
That is, if $x \equiv x'$ and $y \equiv y'$,
then $x \ll y$ if and only if $x' \ll y'$.
Thus, whether $[x] \leq [y]$ or not
won't depend on which representatives you choose for the equivalence classes.
\solution
Suppose that $x \ll y$.
Since $x \equiv x'$, we know that $x' \ll x$.
Also, since $y \equiv y'$, we know that $y \ll y'$.
That is, $x' \ll x \ll y \ll y'$,
so by the transitivity of $\ll$, we get $x' \ll y'$.
Conversely, suppose that $x' \ll y'$.
Since $x \equiv x'$, we know that $x \ll x'$.
Also, since $y \equiv y'$, we know that $y' \ll y$.
That is, $x \ll x' \ll y' \ll y$,
so by the transitivity of $\ll$, we get $x \ll y$.
\part [3]
Show that $\leq$ is a partial order on $X/{\equiv}$.
\solution
Any element of $X/{\equiv}$
is given as the equivalence class of some element $x$ of $X$.
$x \ll x$ by the reflexivity of $\ll$, so $[x] \le [x]$.
Therefore, $\le$ is reflexive.

Next, if $[x] \le [y]$ and $[y] \le [x]$,
then $x \ll y$ and $y \ll x$.
Thus by the definitoin of $\equiv$, $x \equiv y$.
But this means that $[x] = [y]$.
Therefore, $\le$ is antisymmetric.

Finally, if $[x] \le [y]$ and $[y] \le [z]$,
then $x \ll y$ and $y \ll z$.
Then $x \ll z$ by the transitivity of $\ll$,
so $[x] \le [z]$.
Therefore, $\le$ is transitive.

Since $\le$ is reflexive, symmetric, and transitive,
it follows that $\le$ is a partial order.
\end {parts}
I forgot to ask you to prove that $\equiv$ really is an equivalence relation.
But that's true too.
\question [5]
Let $X$ be a set.
Show that $\subseteq$ is a partial order on the power set of $X$.
What condition must $X$ satisfy
for $\subseteq$ to be a total (or linear) order?
\solution
Let $A$ be a subset of $X$.
If $x \in A$, then of course $x \in A$.
Thus, $A \subseteq A$.
Therefore, $\subseteq$ is reflexive.

Next, let $A$ and $B$ be subsets of $X$,
and suppose that $A \subseteq B$ and $B \subseteq A$.
That is, if $x \in A$, then $x \in B$,
and if $x \in B$, then $x \in A$.
Thus $A = B$.
Therefore, $\subseteq$ is antisymmetric.

Finally, let $A$, $B$, and $C$ be subsets of $X$,
and suppose that $A \subseteq B$ and $B \subseteq C$.
That is, if $x \in A$, then $x \in B$,
and if $x \in B$, then $x \in C$.
Thus if $x \in A$, then $x \in C$, so $A \subseteq C$.
Therefore, $\subseteq$ is transitive.

Since $\subseteq$ is reflexive, antisymmetric, and transitive,
it follows that $\subseteq$ is a partial order.

For $\subseteq$ to be a total order,
it's necessary that $A \subseteq B$ or $B \subseteq A$ always be true.
But if $X$ has any two distinct elements $x$ and $y$,
then this will fail for $A := \{x\}$ and $B := \{y\}$.
Therefore we must have $|X| \le 1$.
On the other hand, if $|X| \le 1$,
so that $X = \emptyset$ or $X = \{x\}$ for some unique element $x$,
then $\subseteq$ is indeed a total order.
In the first case, there is only one subset of $X$, so nothing to prove.
In the second case, we need only $\emptyset \subseteq \{x\}$, which is true.
\question
Consider the poset (partially ordered set)
described by the following Hasse diagram:
$$ \xymatrix { A \ar @{-} [d] & B \ar @{-} [dl] \ar @{-} [d] \\
C \ar @{-} [d] & D \ar @{-} [dl] \ar @{-} [d] \\
E & F } $$
\begin {parts}
\part [2]
What are the maximal elements of the poset?
\solution
$F$ is not maximal because (for example) $F < D$.
$E$ is not maximal because (for example) $E < C$.
$D$ is not maximal because (for example) $D < B$.
$C$ is not maximal because (for example) $C < B$.
However, nothing is strictly greater than $B$, so $B$ is maximal.
Also, nothing is strictly greater than $A$, so $A$ is maximal.
\part [2]
What are the minimal elements of the poset?
\solution
$A$ is not minimal because (for example) $C < A$.
$B$ is not minimal because (for example) $D < B$.
$C$ is not minimal because (for example) $E < C$.
$D$ is not minimal because (for example) $E < D$.
However, nothing is strictly less than $E$, so $E$ is minimal.
Also, nothing is strictly less than $F$, so $F$ is minimal.
\part [2]
Which is true: $A \leq D$, $D \leq A$, both, or neither?
\solution
Even though $D$ appears below $A$ pictorially,
there is no line drawn betwen them.
Thus $D \leq A$ is false.
And of course $A \leq D$ is false.
Thus neither statement is true.
\end {parts}
\question [3]
Consider the recurrence equation $a_{n+2} = 4a_{n+1} - 4a_{n}$.
Show that $a_{n} = 2^{n}(1 + n)$ is a solution of this recurrence equation.
\solution
If $a_{n} = 2^{n}(1 + n)$,
then $a_{n+1} = 2^{n+1}(1 + (n + 1)) = 2^{n}2(2 + n) = 2^{n}(4 + 2n)$,
and $a_{n+2} = 2^{n+2}(1 + (n + 2)) = 2^{n}4(3 + n) = 2^{n}(12 + 4n)$.
Then $4a_{n+1} - 4a_{n}
= 2^{n}(16 + 8n) - 2^{n}(4 + 4n)
= 2^{n}(12 + 4n)
= a_{n+2}$.
And this is just what the recurence equation says.
\end {questions}
\end {document}
