Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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

( \newcommand{\kernel}{\mathrm{null}\,}\)

Exercise 1.4.E.1

Prove that if A is countable but B is not, then BA is uncountable.
[Hint: If BA were countable, so would be
(BA)AB.(Why?)


Use Corollary 1.]

Exercise 1.4.E.2

Let f be a mapping, and ADf. 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 f1[f[A]], by (i). Verify that
f1[f[A]]=A

here; cf. Problem 7 in §§4-7.]

Exercise 1.4.E.3

Let a,b be real numbers (a<b). Define a map f on [0,1) by
f(x)=a+x(ba).


Show that f is one to one and onto the interval [a,b)={x|ax<b}. From Problem 2, deduce that [a,b) is uncountable. Hence, by Problem 1, so is(a,b)={x|a<x<b}.

Exercise 1.4.E.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 1.4.E.5

Show that every infinite set A contains a countably infinite set, i.e., an infinite sequence of distinct terms.
[Hint: Fix any a1A;A cannot consist of a1 alone, so there is another element
a2A{a1}.(Why?)


Again, A{a1,a2}, so there is an a3A{a1,a2}. (Why?) Continue thusly ad infinitum to obtain the required sequence {an}. Why are all an distinct? ]

Exercise 1.4.E.6

From Problem 5, prove that if A is infinite, there is a map f:AA 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.

Exercise 1.4.E.7

Conversely (cf. Problem 6), prove that if there is a map f:AA 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 a1A such that a1f[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 a1f[A], whereas amf[A](m>1). Then proceed inductively.]


1.4.E: Problems on Countable and Uncountable Sets (Exercises) is shared under a CC BY 1.0 license and was authored, remixed, and/or curated by LibreTexts.

Support Center

How can we help?