$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 1.4.E: Problems on Countable and Uncountable Sets (Exercises)

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Exercise $$\PageIndex{1}$$

Prove that if $$A$$ is countable but $$B$$ is not, then $$B-A$$ is uncountable.
[Hint: If $$B-A$$ were countable, so would be
$(B-A) \cup A \supseteq B . \quad(\mathrm{Why?})$
Use Corollary $$1 . ]$$

Exercise $$\PageIndex{2}$$

Let $$f$$ be a mapping, and $$A \subseteq D_{f} .$$ Prove that
(i) if $$A$$ is countable, so is $$f[A]$$ ;
(ii) if $$f$$ is one to one and $$A$$ is uncountable, so is $$f[A]$$.
$$\left[\text { Hints: }\left(\text { i) If } A=\left\{u_{n}\right\}, \text { then }\right.\right.$$
$f[A]=\left\{f\left(u_{1}\right), f\left(u_{2}\right), \ldots, f\left(u_{n}\right), \ldots\right\}$
(ii) If $$f[A]$$ were countable, so would be $$f^{-1}[f[A]],$$ by (i). Verify that
$f^{-1}[f[A]]=A$
here; cf. Problem 7 in §§4-7.]

Exercise $$\PageIndex{3}$$

Let $$a, b$$ be real numbers $$(a<b) .$$ Define a map $$f$$ on $$[0,1)$$ by
$f(x)=a+x(b-a).$
Show that $$f$$ is one to one and onto the interval $$[a, b)=\{x | a \leq x<b\}$$. From Problem $$2,$$ deduce that $$[a, b)$$ is uncountable. Hence, by Problem $$1,$$ so $$i s(a, b)=\{x | a<x<b\}$$.

Exercise $$\PageIndex{4}$$

Show that between any real numbers $$a, b(a<b)$$ there are uncountably many irrationals, i.e., numbers that are not rational.
[Hint: By Corollary 3 and Problems 1 and $$3,$$ the set $$(a, b)-R$$ is uncountable. Explain in detail.

Exercise $$\PageIndex{5}$$

Show that every infinite set $$A$$ contains a countably infinite set, i.e., an infinite sequence of distinct terms.
[Hint: Fix any $$a_{1} \in A ; A$$ cannot consist of $$a_{1}$$ alone, so there is another element
$a_{2} \in A-\left\{a_{1}\right\} . \quad(\mathrm{Why} ?)$
Again, $$A \neq\left\{a_{1}, a_{2}\right\},$$ so there is an $$a_{3} \in A-\left\{a_{1}, a_{2}\right\} .$$ (Why?) Continue thusly ad infinitum to obtain the required sequence $$\left\{a_{n}\right\} .$$ Why are all $$a_{n}$$ distinct? $$]$$

Exercise $$\PageIndex{6}$$

From Problem $$5,$$ prove that if $$A$$ is infinite, there is a map $$f : A \rightarrow A$$ that is one to one but not onto $$A .$$
[Hint: With $$a_{n}$$ as in Problem $$5,$$ define $$f\left(a_{n}\right)=a_{n+1} .$$ If, however, $$x$$ is none of the $$a_{n},$$ put $$f(x)=x$$ . Observe that $$f(x)=a_{1}$$ is never true, so $$f$$ is not onto $$A .$$ Show, however, that $$f$$ is one to one.

Exercise $$\PageIndex{7}$$

Conversely (cf. Problem 6), prove that if there is a map $$f : A \rightarrow A$$ that is one to one but not onto $$A,$$ then $$A$$ contains an infinite sequence $$\left\{a_{n}\right\}$$ of distinct terms.
[Hint: As $$f$$ is not onto $$A,$$ there is $$a_{1} \in A$$ such that $$a_{1} \notin f[A] .$$ (Why?) Fix $$a_{1}$$ and define
$a_{2}=f\left(a_{1}\right), a_{3}=f\left(a_{2}\right), \ldots, a_{n+1}=f\left(a_{n}\right), \ldots \text { ad infinitum. }$
To prove distinctness, show that each $$a_{n}$$ is distinct from all $$a_{m}$$ with $$m>n .$$ For $$a_{1},$$ this is true since $$a_{1} \notin f[A],$$ whereas $$a_{m} \in f[A](m>1) .$$ Then proceed inductively.]