Reading Quiz Section 8.1
1. A set A is countably infinite (or denumerable) if . Select all that apply.
(a) There exists a surjection from N onto A.
(b) There exists an injection from N into A.
(c) There exists a bijection between A and Q.
(d) There exists an injection from A into N and no injection from A into any finite set.
2. True or False: if A is a proper subset of B, then A has strictly smaller cardinality than B.
Practice Problems Section 8.1
1. Show that the set of perfect squares A = {n
2
: n ∈ N} is countably infinite.
2. Find an injective function f : N → (0, 1) .
3. Let a, b ∈ R with a < b. Find a bijective function g : (0, 1) → (a, b) and show that your
function is bijective. Hence conclude that any two finite-length open intervals in R have the
same cardinality.
4. Let B be a subset of A. Suppose B is countably infinite and let a ∈ A \ B. Show that B ∪ {a} is
countably infinite.
(Hint: let h : B → N be bijective: how might you construct k : B ∪ {a} → N bijective?)
5. Let A be a countably infinite set.
(a) Prove that the Cartesian product A × A is countably infinite.
(b) By induction, prove that A × · · · × A
| {z }
n times
is countably infinite, for all n ∈ N.
