Question 37

Evaluate each set:

• P: Set of rational numbers $\mathbb{Q}$. $\mathbb{Q}$ can be placed in one-to-one correspondence with a subset of $\mathbb{Z} \times \mathbb{Z}$, which is countably infinite. Hence, P is countable.
• Q: Set of functions from $\{0, 1\}$ to $\mathbb{N}$. A function $f: \{0, 1\} \to \mathbb{N}$ is uniquely defined by $(f(0), f(1)) \in \mathbb{N} \times \mathbb{N}$. Since the Cartesian product of two countable sets is countable, Q is countable.
• R: Set of functions from $\mathbb{N}$ to $\{0, 1\}$. This is the set of all infinite binary sequences, which has cardinality $2^{\aleph_0} = \mathfrak{c}$ (uncountable by Cantor's diagonal argument). Hence, R is uncountable.
• S: Set of finite subsets of $\mathbb{N}$. The collection of finite subsets is $\bigcup_{k=0}^{\infty} \{A \subset \mathbb{N} \mid |A| = k\}$, a countable union of countable sets, which is countable. Hence, S is countable.

Sets P, Q, and S are countable, matching option D.