\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 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}