The GATE Grind

GATE 2018 CS – Question 37

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 2 marks · Multiple choice

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?

  1. $Q$ and $S$ only
  2. $P$ and $S$ only
  3. $P$ and $R$ only
  4. $P$, $Q$ and $S$ only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $P$, $Q$ and $S$ only

Explanation

The rationals are countable. A function from $\{0,1\}$ to $N$ is a pair in $N\times N$, which is countable, and the finite subsets of $N$ form a countable set. The functions from $N$ to $\{0,1\}$ correspond to all subsets of $N$, which is uncountable.