1.4.E: Problems on Countable and Uncountable Sets (Exercises)
( \newcommand{\kernel}{\mathrm{null}\,}\)
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)∪A⊇B.(Why?)
Use Corollary 1.]
Let f be a mapping, and A⊆Df. 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].
[ Hints: ( i) If A={un}, then
f[A]={f(u1),f(u2),…,f(un),…}
(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.]
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≤x<b}. From Problem 2, deduce that [a,b) is uncountable. Hence, by Problem 1, so is(a,b)={x|a<x<b}.
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.
Show that every infinite set A contains a countably infinite set, i.e., an infinite sequence of distinct terms.
[Hint: Fix any a1∈A;A cannot consist of a1 alone, so there is another element
a2∈A−{a1}.(Why?)
Again, A≠{a1,a2}, so there is an a3∈A−{a1,a2}. (Why?) Continue thusly ad infinitum to obtain the required sequence {an}. Why are all an distinct? ]
From Problem 5, prove that if A is infinite, there is a map f:A→A that is one to one but not onto A.
[Hint: With an as in Problem 5, define f(an)=an+1. If, however, x is none of the an, put f(x)=x. Observe that f(x)=a1 is never true, so f is not onto A. Show, however, that f is one to one.
Conversely (cf. Problem 6), prove that if there is a map f:A→A that is one to one but not onto A, then A contains an infinite sequence {an} of distinct terms.
[Hint: As f is not onto A, there is a1∈A such that a1∉f[A]. (Why?) Fix a1 and define
a2=f(a1),a3=f(a2),…,an+1=f(an),… ad infinitum.
To prove distinctness, show that each an is distinct from all am with m>n. For a1, this is true since a1∉f[A], whereas am∈f[A](m>1). Then proceed inductively.]