GATE CS 2018 Q27 — Sets, Relations and Functions

To determine which of the given sets are countable, we analyze each set individually:

• Set $P$ (Rational numbers): The set of all rational numbers $\mathbb{Q}$ is countably infinite. This is a standard result established by Cantor's diagonal argument. Thus, $P$ is countable.
• Set $Q$ (Functions from $\{0,1\}$ to $N$): Any function $f: \{0,1\} \to N$ is uniquely determined by the ordered pair $(f(0), f(1)) \in N \times N$. Since $N$ is countable, the Cartesian product $N \times N$ is also countable. Thus, $Q$ is countable.
• Set $R$ (Functions from $N$ to $\{0, 1\}$): The set of functions from $N$ to $\{0,1\}$ is in bijection with the power set of $N$, denoted as $\mathcal{P}(N)$. By Cantor's theorem, $|\mathcal{P}(N)| = 2^{\aleph_0}$, which is uncountable. Thus, $R$ is uncountable.
• Set $S$ (Finite subsets of $N$): Let $S_k$ be the set of all subsets of $N$ of size $k$. Each $S_k$ is countable because it can be mapped injectively to $N^k$, which is countable. The set of all finite subsets $S = \bigcup_{k=0}^{\infty} S_k$ is a countable union of countable sets, which is countable.

Therefore, only $P, Q,$ and $S$ are countable sets.