\documentclass[11pt, twoside]{article}

\input{macros-course}

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

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

\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 denominator less than $100$.
\eparts

\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$, ... $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
%[[[George:  You might want to make up some more interesting strings,
%replace some of my examples, etc.]]]

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

\problem  
\textbf{Induction and Recursive Algorithms}
\bparts
\ppart Rosen \S 3.4, Exercise 18, and prove correctness of your algorithm.
\eparts

\problem \textbf{Relations}
\bparts
\ppart Velleman \S 4.2, Exercise 3
\ppart Velleman \S 4.2, Exercise 7
\eparts

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

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

\problem \textbf{Relations --- Equivalence relations}
\bparts
\ppart Velleman \S 4.6, Exercise 3. 
\ppart Velleman \S 4.6, Exercise 5. 
\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}





