GATE 2018 CS Q.27: solution and answer

GATE 2018 · CSQ.27 · 2 marks · MCQ

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The countable sets are $P$ , $Q$ and $S$ only, which is option (D).

Official answer: DSource: Official answer key, GATE 2018 CS (IIT Guwahati)

$P$ is countable: every rational can be written as $p / q$ with $p \in Z$ , $q \in N$ , so $P$ is the image of the countable set $Z \times N$ under $(p, q) \mapsto p / q$ . The image of a countable set is countable (and $P$ is infinite, since it contains $N$ ).
$Q$ is countable: a function $f : {0, 1} \to N$ is determined by the pair $(f (0), f (1))$ , so $Q$ is in bijection with $N \times N$ . A finite product of countable sets is countable, so $Q$ is countable.
$R$ is uncountable: a function $g : N \to {0, 1}$ is the indicator function of the subset ${n : g (n) = 1}$ of $N$ , and every subset arises this way exactly once. So $R$ is in bijection with the power set $2^{N}$ .
By Cantor's theorem, $∣ 2^{N} ∣ > ∣ N ∣$ (diagonal argument: for any list $A_{1}, A_{2}, \dots$ of subsets of $N$ , the set ${n : n \in / A_{n}}$ differs from every $A_{n}$ ). Hence $R$ is uncountable.
$S$ is countable: for each $n \in N$ let $S_{n}$ be the set of subsets of ${1, \dots, n}$ , which has $2^{n}$ elements, so it is finite. Every finite subset of $N$ is contained in ${1, \dots, n}$ for $n$ equal to its largest element (or any $n$ for the empty set), so $S = ⋃_{n \in N} S_{n}$ . A countable union of finite sets is countable, so $S$ is countable.
So $P$ , $Q$ and $S$ are countable and $R$ is not. The matching option is (D), $P$ , $Q$ and $S$ only.

KEY IDEA

A set is countable if it is the image of $N$ or of a countable product or union of countable sets. Functions on a finite domain, finite subsets and fractions of integers all stay countable. Functions from $N$ to ${0, 1}$ are the same as subsets of $N$ , and by Cantor's theorem there are uncountably many of those.

WATCH OUT FOR

Treating $S$ , the set of finite subsets of $N$ , as uncountable because it sounds like the power set $2^{N}$ . Only the infinite subsets make $2^{N}$ uncountable. Another slip is treating $R$ , the set of functions from $N$ to ${0, 1}$ , as countable because ${0, 1}$ is finite.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 8 Sets & relations questions, with notes

GATE 2018 CS Q.27: solution and answer

Answer and solution

More Sets & relations questions