The Fourth Lesson of the Course
Commentary on Chapter 4 of D'Angelo-West Text
6feb11\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}