\documentclass{article}  
\usepackage{latexsym} 
\begin{document}
\section*{Extra questions for Chapter 1}

These questions are supposed to be relatively challenging. If you can do them,
you are in good shape.

\begin{enumerate}
\item  Find two maps $f, g : {\bf N} \rightarrow {\bf N}$ 
such that $f \circ g = \mbox{Id}_{\bf N}$ but
$f \circ g \not = g \circ f.$
\item Suppose that $A$ is a set and that $h : A \rightarrow A$
is a map. For each natural number $n,$ let $h^n$ be the composition
of $n$ copies of $h.$
\begin{enumerate}
\item[(a)] Show that if $A$ is finite, then there are distinct natural numbers
$a,b$ such that $f^a = f^b$.
\item[(b)] Consider maps from $\bf N$ to $\bf N.$ Find and describe a function 
$g: {\bf N} \rightarrow {\bf N}$ such that if $a$ and $b$ are distinct
natural numbers, then $g^a \not = g^b.$
\item[(c)] Show that you can do part [b] if $\bf N$ is replaced by any infinite set.
\end{enumerate}
\item  Let $\Sigma = \{ a, b, c, \ldots, z\}$ be the set
of lower case leters of the Roman alphabet. Let $\Sigma^*$ denote
the set of all words (strings of finite length) using this alphabet.
Thus {\em biscuit, boooom, uqweiuqe} and the empty word are all elements
of $\Sigma^*.$ Two words are equal if and only if they are the same length,
and the letters in corresponding positions are the same.
\begin{enumerate}
\item[(a)] How many elements of $\Sigma^*$ have length $n$ where $n$ is a natural
number or $0.?$
\item[(b)] How many elements of $\Sigma^*$ have the property that no letter
occurs more than once in the word?
\item[(c)] How many elements of $\Sigma^*$ of length $n$ have the property that
no letter is juxtaposed to itself in the word?
\item[(d)] Impose the dictionary ordering on $\Sigma^*,$ so
\[a<b<c< \cdots < x < y < z\] 
is an ordering of the words of length 1. We compare two words
as follows: the first is less than the second if they have the
same first $i$ letters, and the $i+1$st letter of the first word
is less than the $i+1$st letter of the second word. In order
to compare words of different lengths, we deem every word
to have an invisible
extra last letter which is less than all the visible lower case letters.
Thus $somethin < something$ because the invisible letter is less than $g.$
Similarly $\emptyset < empty$ because $\emptyset$ is a word
of length 0 followed by the invisible letter, but $empty$ is a word
of length 5, and the invisible letter is less than $e.$ Finds an
infinite strictly descending chain of words 
\[ w_1 > w_2> w_3 > w_4 > \ldots \]
using this ordering on $\Sigma^*.$
\item[(e)] Modify the ordering of part [d] as follows. Forget all the stuff about
invisible end-of-word symbols and go back to the naive view. First:
say the first word is less than the second word if the first
word is of shorter length than the second. Second: if two words
have the same length, compare them using the ordering of part [d].
Now show that using this new ordering on $\Sigma^*$, there are
no infinite strictly descending sequences.
\end{enumerate}
\item Find two sets $A, B$ such that both
$A \in B$ and $A \subseteq B.$
\item Most of the time, logical quantifiers get used casually, 
mixed in with
less formal symbols, to express statements about mathematics
(or some less interesting aspect of life). In this question
you must take each assertion and try to write it clearly and
economically using quantifiers.

For example, the sad line from a song which is (roughly)
{\it Into each life, some rain must fall,
and today some rain is falling in mine}
becomes

Let $L$ be the set of all lives, let $R$ be the set of all falling rain,
and let $G$ be the set of my lives (a singleton set in some theologies).
We have that
$\forall l \in L \exists s \subseteq R$ such that $s$ occurs in $l,$
and today $\exists t \subseteq R$ such that $t$ occurs in $m$
where $m \in G.$
Feel free to use logical connectives.
You should do the best you can with:
\begin{enumerate}
\item[(a)] All men are equal, but some are more equal than others.
\item[(b)] All I want for Christmas are my two front teeth.
\item[(c)] There is one born every minute.
\item[(d)]  No man is an island.
\item[(e)] If some trains are late then all trains are late.
\item[(f)] There is no business like show business.
\item[(g)]  You can fool some of the people all of the time, and fool
all of the people some of the time, but you cannot fool all of the
people all of the time.
\end{enumerate}
\item Let $A$ be a set and let
$S = \{ X \ |\ X \subseteq A\}.$ Suppose $|A| = n \in {\bf N}$ (this means
that the set $A$ contains exactly $n$ elements. In this question
it  may help to look at some small sets $A$ in order to help you
to work out what is going on. As well as giving a formula as the 
answer to each of the four parts, you should attempt to prove that
your answer is correct.
\begin{enumerate} 
\item[(a)]  Determine $|S|.$
\item[(b)]  How many pairs $(X_1, X_2)$ are there with $X_1, X_2 \in S$
and $X_1 \subseteq X_2 ?$
\item[(c)]  How many triples $(X_1, X_2, X_3)$ are there with
$X_1, X_2, X_3 \in S$
and $X_1 \subseteq X_2 \subseteq X_3 ?$
\item[(d)]  How many $r-$tuples $(X_1, \ldots , X_r)$ are there with
$X_1, \ldots, X_r \in S$ and $X_i \subseteq X_{i+1}$ for all natural
Numbers $i$ in the range $1 \le i < r?$
\end{enumerate}
\end{enumerate}
\end{document}
