The Fourth Lesson of the Course

Commentary on Chapter 4 of D'Angelo-West Text

\begin{document} \maketitle \section{Introduction} Chapter 4 of our textbook is concerned with the vocabulary of \textit{Functions} and \textit{Cardinality of Sets}. While there is one very important theorem, the Cantor-Bernstein-Schroeder Theorem, or CBST for short, most of the ideas here are an extension of \textit{ set theory} to \textit{ functions } and to \textit{counting infinite sets}. The former concept is familiar to you from your calculus courses. The latter is simple, once you apply the CBST. The proof of the CBST is appended, but you are not responsible for knowing the proof for the next hourly. To understand this commentary without studying the textbook is not advisable. However, you can read the commenatry first, and then the textbook to see what I consider important. \section{Summary of the topics } \subsection{How to write a natural, a rational, and a real number} Since $\mathbb{N,Q,R}$ are fundamental we need ways of writing their members. Mostly we use the decimal system today. This works well for whole numbers, integers and (some) rational numbers. But for numbers with repeating decimals (rational numbers) and non-repeating but infinite decimal expansions, we use certain conventions. For instance, it is incorrect to say that $\pi = 3.14 $ or even $\pi = 3.14159 $ but $\pi = 3.14159... $ is OK because your reader recognizes that you mean the ratio of the circumference to the diameter of every circle.
Question 1. What is the decimal expansion of $3/7$ ?
Decimal representations are also said to be \textit{to base 10}, written $ \frac{3}{4} =_{10} 0.75 $. For certain purposes one uses bases different that 10. Most commonly, we use \begin{itemize} \item base 2 or \textit{ binary } \item base 8 or \textit{ octal } \item base 16 or \textit{ hexadecimal } \item base 64 if you're a historian of mathematics \item base 7 if you want to teach elementary school arithmetic. \end{itemize} To distinguish the base, we write $ 7_{10} = 111_2$. Often it makes more sense to use letter abbreviations for a common base. Positional numeration has the advantage that we only need a small number of \textit{digit} symbols, and then teach our children positional arithmetic. So for hexadecimal, we need six additional digits, written $A_{hex} = 10_{dec}, B, C, D, E, F$. Thus $2011_{dec} = 7DB_{hex}$. Of course I used Google to do that bit of arithmetic. Do you know how to do this without googling the answer? Now, either you learned how to convert between bases already or not. It is not a deep subject, and belongs to the theory of arithmetic. The text is unusually obtuse here, so we'll just see if you know how to do some simple things.
Question 2. What is $ A \times B = $ in hexadecimal?
Note, "Google says so" is not a justification, though you can use Google to check your answer. The only reason for playing with different bases is to truly understand the theory of positional representations. To train teachers to teach decimal arithmetic effectively, you make them do arithmetic in base 7 (and base 17 if you're sadistic.) Computer engineers, on the other hand, have no choice but to learn arithmetic in binary and hexadecimal. Octal has become obsolete. \subsection{Injection, surjections, bijection and all that} Ever since N. Bourbaki (google it if you want to know what I am talking about) wrote modern mathematics in French, we use the synonyms \begin{itemize} \item \textit{injective} for one-to-one \item \textit{surjective} for onto \item \textit{bijective } for one-to-one-and-onto. \end{itemize} To remind you of the definitions and show off the power of precise notation we recall these definitions: \begin{eqnarray*} \mbox{A function: } f:X \rightarrow Y & \mbox{ iff } & (\forall x \in X)(\exists !\ y \in Y )(y=f(x)) \\ \mbox{injective: } & \mbox{ iff } & (\forall a,b \in X)(f(a)=f(b) \implies a = b ) \\ \mbox{surjective: } & \mbox{ iff } & (\forall y \in Y)(\exists x \in X)( y=f(x))\\ \mbox{bijective: } & \mbox{ iff } & (\forall y \in Y)(\exists !\ x \in X)(y=f(x))\\ \mbox{inverse of point: } f^{-1}(y) & = & \{ x\in X | f(x) = y \} \\ \mbox{inverse of a subset: } f^{-1}(B) & = & \{ x \in X | f(x) \in B \} \\ \mbox{image of a subset: } f(A) & = & \{ y \in Y | (\exists x\in X)(y = f(x))\} \\ \end{eqnarray*}
Question 3. Write the right-hand sides of the seven definitions above in good English, without symbols.
Some consenques of these definitions for $f : X \rightarrow Y $ are \begin{eqnarray*} f \mbox{ is injective } & \mbox{ iff } & f^{-1}: f(X) \rightarrow X \mbox{ is a function}\\ f \mbox{ is surjective } & \mbox{ iff } & f(X) = Y \\ f \mbox{ is bijective } & \mbox{ iff } & f^{-1}: Y \rightarrow X \mbox{ is a function}\\ \end{eqnarray*} Write the proof for these three theorems into your Journal. You may see them again on a test. \section{Bijections are good for counting} If you ask a philosopher just what the number 42 means (and I don't mean Douglas Adams .... google Hitchhiker's Guide to the Galaxy), you'll get the answer that "42 is the term for all sets of exactly 42 elements." The mathematician is more precise. The set $ \Delta_{42} := \{1,2,...,42 \}$ has, by all agreement, 42 whole numbers in it. And a set of forty-two apples: $ A = \{a_1, a_2, ..., a_{42} \}$ has just that many apples because we can set up a bijection between $f: \Delta_{42} \rightarrow A $. By the way, the names of the apples demonstrates the bijection in terms of their subscripts. For example, $f(3)=a_3$. \subsection{Infinite sets} Note the texbook's example of a bijections $ f: \mathbb{N} \rightarrow \mathbb{Z}$. Why is \begin{eqnarray*} f(n) & = & \frac{n}{2} \mbox{ for even } n \\ \mbox{ and } & = & - \frac{n-1}{2} \mbox{ for odd } n \\ \end{eqnarray*} a bijection? If you understood this, then you can answer the following too. For notational reasons, let's write $f' = f^{-1}$. No derivatives intended.
Question 4. For the function just defined, write an explicit formula for $f'(z)$ where $z \in \mathbb{Z}$
\textbf{Theorem:} The fact that you can write down an explicit \textit{ inverse} to a function proves that the function is is a bijection. \textbf{Definition:} A set which is in one-to-one-and-onto (bijective) correspondence with $\mathbb{N}$ is called \textit{countably infinite}.
Question 5. Show that the even whole numbers are also countably infinite.
The example above shows that $\mathbb{Z}$ is coutably infinite, or just "countable" for short. This theorem should not only be memorized, but also be in your Journal. What is surprising is that the set of rational numbers, $\mathbb{Q}$ is also countable but that the reals $\mathbb{R}$ is not. The reals are said to be \textit{ uncountably infinite}. So, you know that there are far more irrational numbers than rational ones, which shows that democratic equality between rational and irrational numbers is not practiced among the real numbers. The proof of this theorem is a part of Math 348 and you must learn it. Be sure you understand this proof and it is in your Journal \end{document}