Let \(N\) be the set of natural numbers. Consider the following sets. P: Set…
2018
Let \(N\) be the set of natural numbers. Consider the following sets.
P: Set of Rational numbers (positive and negative)
Q: Set of functions from {0, 1} to \(N\)
R: Set of functions from \(N\) to {0, 1}
S: Set of finite subsets of \(N\).
Which of the sets above are countable?
- A.
Q and S only
- B.
P and S only
- C.
P and R only
- D.
P, Q and S only
Attempted by 276 students.
Show answer & explanation
Correct answer: D
Answer: P, Q and S are countable; R is uncountable.
P (rational numbers): The rationals can be expressed as pairs of integers (numerator, denominator). Since the integer pairs are countable, the rationals are countable.
Q (functions from {0,1} to N): Each function is determined by the pair (f(0),f(1)) in N×N. N×N is countable, so Q is countable.
R (functions from N to {0,1}): These are infinite binary sequences, in one-to-one correspondence with the power set of N. By Cantor's diagonal argument this set is uncountable.
S (finite subsets of N): For each k, the k-element subsets of N are countable. S is the union over all k∈N of these countable sets, so S is a countable union of countable sets and therefore countable.
Key conclusion: P, Q and S are countable; R is uncountable.
A video solution is available for this question — log in and enroll to watch it.