\documentclass[11pt, twoside]{article}

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\askaboutsolutions

\begin{document}
\psol{3}{September 19, 2000}{2:35pm in lecture, September 26, 2000}

\textbf{Be sure to clearly indicate your TA's name on the solutions
your turn in}.

-----------------------------------------------------------------------------\\

\textbf{Self-study:  More set theory}
Read: Velleman, Sections 1.3, 1.4, 2.3. \\
Self-study problems (not to be handed in): Velleman \S 1.3, Exercise 4, \S 1.4
Exercises 1, 3, 4, 5, 6, 8, \S 2.3 Exercises 2, 3, 5, 6\\

-----------------------------------------------------------------------------\\

\textbf{Reading:}
Velleman, Chapter 4 \\
Rosen, Sections 3.2, 3.3, 3.4, Chapter 6.\\

\medskip
\begin{problems}
\problem 
\textbf{Well-Ordering}
A set is {\bf well-ordered\/} if every nonempty subset of the set has
a least element.
Determine whether each of the following sets is well-ordered.
Explain your reasons.
\bparts
\ppart The set of integers.
\ppart The set of integers greater than $-100$.
\ppart The set of positive rationals.
\ppart The set of positive rationals with a denominator less than
$100$, and a positive numerator.
\eparts

\medskip
\solution{
\medskip
\textbf{Solutions:}
\renewcommand{\labelenumi}{\textbf{(\alph{enumi}\textbf)}}
\begin{enumerate}
\item 
No.  The set of integers is not well ordered.  Consider the subset
consisting of the entire set itself.  This set has no smallest member, since
there does not exist a smallest integer.
\item
Yes.  This set is well-ordered.  Observe that given a non-empty
 subset $A$, we can find its least element as follows.  First, if
 $-99 \in A$, then this must be the least element since we are
 dealing with all integers greater than $-100$.  If not, then we check
 if $-98$ is in the set $A$.  If it is, then it must be the least
 element.  If not, then we continue on to check for $-97$, and so on.
 Since $A$ is non-empty, if we continue with this procedure, we will
 find the smallest element of $A$.

\item
No.  The subset consisting of the entire set has no smallest element,
since, given what might be ``the smallest rational number,'' one could
always divide that 
by two to get an even smaller rational number.
\item
Yes.  Analogously to part (b), this set is well-ordered.  

We prove
this more formally by contradiction.  Suppose that the set is not well
ordered.  Then, there is a subset $A$ containing no least element.
Let $\alpha_1 \in A$.  If $A$ has no least element, then there is some
$\alpha_2 \in A$ with $\alpha_2 < \alpha_1$.  Again, since $\alpha_2$
cannot be the least element, there must be some $\alpha_3 \in A$ with
$\alpha_3 < \alpha_2$.  Repeating this process, we can come up with a
never ending sequence of elements: 
\[ \alpha_1 < \alpha_2 < \alpha_3 < \ldots \]

\noindent Now, it follows, by definition, 
that $\alpha_1$ can be written in the form $m_1/n_1$ where $m_1$ and
$n_1$ are positive integers, and $n_1 < 100$.  Similarly, $\alpha_2$
can be written as 
$m_2/n_2$, and in general, $\alpha_i$ can be written as $m_i / n_i$.  
Now, if $\alpha_{i+1} < \alpha_i$, then it must be the case that 
$m_{i+1} < m_i$ or $n_{i+1} > n_i$ -- for if it was the case that
$m_{i+1} \geq m_i$ {\em and} $n_{i+1} \leq n=i$, then it would be the
case that $\alpha_{i+1} \geq \alpha_i$.  Also, by definition, each of the
$n_i$ must be less than 100.  Thus at some point $i$, $n_{j+1}$ cannot
be greater than $n_j$, for all $j \geq i$.  From that point onward,
$m_{j+1}$ must be 
strictly less than $m_j$, $m_{j+2}$ must be strictly less than
$m_{j+1}$, and so on.  However, since each $m_j$ is an integer, at
some point this sequence of values $m_j$ will become negative.  This
contradicts our original assumption that the numerators are positive.  
\end{enumerate}
\renewcommand{\labelenumi}{\arabic{enumi}.}}


\problem \textbf{Structural Induction}

The set $SSS$ of ``super-symmetric strings'' is defined as follows:
\begin{enumerate}
\item
The length one strings consisting of individual letters of the
alphabet, $a$, $b$, $c$, $d$, $\ldots$, $z$, are in $SSS$. 
\item
If $\alpha$ and $\alpha'$ are two strings in $SSS$ then the string
$\alpha \alpha' \alpha$ is in $SSS$.
\item
$SSS$ contains nothing else.
\end{enumerate}
\bparts
\ppart
Which of the following are super-symmetric strings?\\
i.  a\\     
ii.  aaaba\\   
iii.  abcbacabcba\\
iv. $\lambda$, the empty string\\
v. abaabcbaaba\\

\solution{
\medskip
\textbf{Solutions:}\\
i. Yes.  This is stated in part 1 of the definition.\\
ii. No.  This string is not of the form $\alpha \alpha' \alpha$.\\
iii. Yes.  Formally, consider $\alpha'=aca$, $\alpha=bcb$.  Then we have
a string of the form $a \alpha \alpha' \alpha a$, which is in $SSS$
by parts 1 and 2 of the definition.\\
iv.  No.  By part 3 of the definition\\
v. Yes. Similar reasoning to part iii shows that the string $bcb$ is in the 
middle of the super-symmetric\\ 
string, with the string $a$ wrapped around it, and with the string
$aba$ wrapped around that.

}

\ppart
Prove by structural induction that in any super-symmetric string $\alpha$, 
exactly one letter appears an odd number of times.\\

%%%
%Fix this either to be more complete, or to use Structural Induction.
%Find out what structural induction is, too.
%%%

\solution{
\medskip
\textbf{Solution:}\\
\textbf{Proof:} Define $P(e)$: String $e$ has exactly one letter which appears an odd number of times.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall e \in SSS \ P(e)$.\\
1. (Base) $P(a)$\>\>\>\>The string $a$ has exactly one letter which appears an odd number of times.\\
2. (Base) $P(b)$\>\>\>\>Same for the string $b$\\
$\vdots$\\
26. (Base) $P(z)$\>\>\>\> Still has exactly one letter which appears once.\\
27. (Inductive Step) $\forall e, e' \in SSS \ P(e)\wedge P(e') \longrightarrow P(ee'e)$ \\
\>1. Fix $e,e' \in SSS$.\\
\>2. Assume $P(e) \wedge P(e')$.  That is, each of $e$ and $e'$ has exactly one letter which\\
\>\>appears and odd number of times.\\
\>3. By the inductive hypothesis, both $e$ and $e'$ have exactly one letter which appears an odd\\
\>\> number of times.  When we form the string $ee'e$, the letters in $e$ all get repeated, \\
\>\> and thus they all appear an even number of times.  By the IH, there is one letter in $e'$\\
\>\> which appears an odd number of times in $e'$.  Now, even if this letter is also present in\\
\>\>$e$, it will still appear an odd number of times in $ee'e$ (since
the sum of an odd number and an even number is odd).  Therefore, we
have shown $P(ee'e)$.\\ 
\>4. QED.\\
\end{tabbing}
}

\eparts

\problem  
\textbf{Induction and Recursive Algorithms}
\bparts
\ppart Rosen \S 3.4, Exercise 18\\
Devise a recursive algorithm to find the $n$th term of the sequence
defined by $a_0 = 1, a_1 = 2, a_2 = 3$, and $a_n = a_{n-1} + a_{n-2} + a_{n-3}$,
for $n=3,4,5,\ldots$.\\
\solution{


\medskip
\textbf{Solution:}\\


\textbf{procedure} \textit{sum-sequence} ($n$:nonnegative integers)\\
\textbf{if} (n$<$3) \textbf{then} \textit{sum-sequence}($n$):=$n+1$;\\
\textbf{else} \textit{sum-sequence}($n$):=\textit{sum-sequence}($n-1$)+
\textit{sum-sequence}($n-2$)+\textit{sum-sequence}($n-3$)\\
}
\eparts

\problem \textbf{Relations}
\bparts
\ppart Velleman \S 4.2, Exercise 3 parts a,b and c.\\
Suppose $A=\{1,2,3\}, B=\{4,5,6\}, R=\{(1,4), (1,5), (2,5), (3,6)\}$, and 
$S=\{(4,5), (4,6), (5,4), (6,6)\}.$  Note that $R$ is a relation from $A$ to $B$ and
$S$ is a relation from $B$ to $B$.  Find the following relations:\\
\medskip
a. $S\circ R$\\
b. $S\circ S$\\
c. $S^{-1}\circ R$ 

\solution{
Suppose $A=\{1,2,3\}, B=\{4,5,6\}, R=\{(1,4), (1,5), (2,5), (3,6)\}$, and 
$S=\{(4,5), (4,6), (5,4), (6,6)\}.$  Note that $R$ is a relation from $A$ to $B$ and
$S$ is a relation from $B$ to $B$.  Find the following relations:\\

\medskip
\textbf{Solutions:}\\
a. $S\circ R = \{(1,5), (1,6), (1,4), (2,4), (3,6)\}$\\
b. $S\circ S = \{(4,4), (4,6), (5,5), (5,6), (6,6)\}$\\
c. $S^{-1}\circ R = \{(1,5), (1,4), (2,4), (3,4), (3,6)\}$\\
%%%
%d.
%%% 
}
%%%
%\ppart Velleman \S 4.2, Exercise 7
%%%
\eparts

%%%
%\problem \textbf{Relations --- Ordering}
%Velleman \S 4.3, Exercise 9.
%%%

\problem \textbf{Relations --- Properties}
\bparts
\ppart Velleman \S 4.4, Exercise 1. %[[[Good finger exercise.]]]


\noindent In each case, say whether or not $R$ is a partial order on $A$.  If so, is it a total order?\\
a. $A=\{a,b,c\}, R=\{(a,a),(b,a),(b,b),(b,c),(c,c)\}.$\\
b. $A=\{$ the set of all words in English, $R = \{(x,y\}\in A \times
A\  \nand \ $the word $x$ comes before the word $y$ alphabetically$\}$.\\
c. $A=\reals, R=\{(x,y) \in \reals \times \reals \ \nand \ |x|\leq |y|\}$.\\
d. $A=\reals, R=\{(x,y) \in \reals \times \reals \ \nand \ |x| < |y|$
or $x=y\}$.\\
\medskip
\solution{
\textbf{Solutions:}\\
a. $R$ is reflexive, transitive, and antisymmetric.  Therefore, $R$ is a partial order on $A$.  However, it is not a total order on $A$ since neither the pair $(a,c)$ nor $(c,a)$ is in $R$.\\
b. $R$ is not reflexive (although it is transitive and antisymmetric), and thus it is not a partial order on $A$.\\
c. $R$ is reflexive and transitive. However, it is not antisymmetric. As a counterexample, \\
$|-3| \leq |3|, |3| \leq |-3|$, but $3 \neq -3$. \\
d. $R$ is reflexive, transitive, and antisymmetric.  Therefore, $R$ is a partial order on $A$. However, $R$ is not a total order on $A$. As a counterexample, if x = 5, y = -5, then none of the following holds: $x = y, |x| < |y|, |y| < |x|$.  
}


%%%
%\ppart Velleman \S 4.4, Exercise 5. %[[[Good]]]
%%%

\eparts

\problem \textbf{Relations --- Equivalence relations}
\bparts
\ppart Velleman \S 4.6, Exercise 3. \\
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Which of the following relations are equivalence relations?  For those that are equivalence\\
relations, what are the equivalence classes?\\
\>a. $R=\{(x,y) \in W \times W \ \nand \ $ the words $x$ and $y$ start with the same letter$\}$,\\
\>\>where $W=$ the set of all words in teh English language.\\
\>b. $S=\{(x,y) \in W \times W \ \nand \ $ the words $x$ and $y$ have at least one letter in\\
\>\>common$\}$, where $W=$ the set of all words in teh English language.\\
\>c. $R=\{(x,y) \in \reals \times \reals \ \nand \ x-y \in \rationals\}$.\\
\>d. $R=\{(x,y) \in \reals \times \reals \ \nand \ \exists n \in \integers$ such that $(y=x\cdot 10^n)\}$.\\
\end{tabbing}
\solution{
\textbf{Solutions:}\\
\renewcommand{\labelenumi}{\alph{enumi}.}
\begin{enumerate}

\item 
$R$ is an equivalence relation since it is reflexive, symmetric, and transitive.  The equivalence class of $x$ with respect to $R$ is the set $[x]_R = $ the set of words $y$, such that $y$ has the same first letter as $x$.

\item
 $S$ is reflexive and symmetric, but it is not transitive.  Therefore, $S$ is not an equivalence relation.  For example, let $w_1$ be the word ``scream,'' let $w_2$ be the word ``and,'' and let $w_3$ be the word ``shout.''  Then $w_3 S w_1$, and $w_1 S w_2$, but it is \textbf{not} the case that $w_3 S w_2$.

\item
$R$ is reflexive since, for any $x\in R$, $x-x=0$.  $R$ is symmetric because if $(x-y)$ is rational, then $(y-x)=-(x-y)$ is rational as well.  Finally, $R$ is also transitive.  To see this, consider $(x,y)\in R$ and $(y,z)\in R$.  We would like to know if $(x,z)$ is also in $R$.  We start by noting that $(x-y)\in \rationals$ and $(y-z)\in \rationals$ by definition of our relation $R$.  Now, we can express $(x-z) = (x-y)+(y-z)$.  Since the sum of any two rational numbers is another rational number, and we have written $(x-z)$ as such, we have shown that $(x,z)\in \rationals$.  Therefore, $R$ is transitive.  Since $R$ is also reflexive and symmetric, $R$ is an equivalence relations on $\reals$.\\
The equivalence class for x is $[x]_R = \{y\ |\ y$ can be written in the form $x + r$, for some rational number $r\}$

\item
$R$ is reflexive, since we can set $n=0$.  $R$ is symmetric because if $y=x*10^k$, for some $k\in \integers$, then $x=y*10^{-k}$, so if $(x,y)\in R$, then $(y,x)\in R$.  We can show that $R$ is transitive as follows: consider pairs $(x,y)\in R$ and $(y,z)\in R$.  $y=x*10^n$ and $z=y*10^m$, for $m,n\in \integers$.   Then, substituting, we have that $z=y*10^{m+n}$.  Since $m+n$ is also $\in \integers$, $(x,z)$ is $\in R$.\\
The equivalence class for x is $[x]_R = \{ y\ |\ y  = x*10^n$, for some $n\in \integers\}$
\end{enumerate}
\renewcommand{\labelenumi}{\arabic{enumi}.}
%%someone should check this... it's getting late and this just seems silly to me
}

\ppart Velleman \S 4.6, Exercise 5. \\
Given $T$, the set of all triangles, and $S=\{(s,t)\in T\times T$ $|$ the triangles $s$ and $t$ are similar$\}$, prove that $S$ is an equivalence relation.\\
\medskip
\medskip
\solution{
\textbf{Solution:}\\
\textbf{Proof:} To prove this, we need to show that $S$ is reflexive, symmetric, and transitive.  Here we go:\\
First of all, two triangles $s$ and $t$ are said to be \textit{similar} if they have three pairs of equal-degree vertices.\\
$S$ is reflexive because every triangle is similar to itself.  That is, every triangle $s$ has three angles of equivalent size to its own three angles.\\
$S$ is symmetric because if $s$ is similar to $t$, then $s$ and $t$ have vertices of the same size, so $t$ is similar to $s$ as well.\\
Finally, $S$ is transitive because if triangle $s$ is similar to triangle $t$, and triangle $t$ is similar to triangle $r$ then triangles $s$ and $t$ have three pairs of equal-degree vertices, and triangles $t$ and $r$ also have three pairs of equal-degree vertices.  $s$ and $r$ must share these three pairs of equal-degree vertices since triangles only have three vertices. $\qed$.
}

%%%
%\ppart Velleman \S 4.6, Exercise 12. 
%%%
\eparts

%%%
%\problem \textbf{Relations --- Topological sorting}
%\bparts
%\ppart Find two total orders that are topological sorts of the divisibility
%relation for the set of natural numbers 1-8:\\
%(i) One with as many as you can pairs out of numerical order.\\
%(ii) One with the FEWEST POSSIBLE pairs out of numerical order.\\
%\eparts
%%%

\end{problems}

\end{document}





