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 above sets are countable? A. Q and S only B. P and S only C. P and R only D. P, Q and S only

GATE 2018 · Discrete Mathematics · Countable/Uncountable Set · medium

Answer: P, Q and S are countable while R is uncountable, so the answer is D (P, Q and S only).

1. P, Q and S are countable: P (rationals) is countably infinite. Q = functions {0,1} -> N is in bijection with N x N (the pair (f(0), f(1))), which is countable. S = finite subsets of N is the union over k = 0,1,2,... of the size-k subsets; each layer is countable and a countable union of countable sets is countable, so S is countable.
2. R is uncountable: R = functions N -> {0,1} corresponds to infinite binary sequences, equivalently to subsets of N. By Cantor's diagonal argument 2^|N| is strictly larger than |N|, so R is uncountable and must be excluded. Hence exactly P, Q and S are countable, which is option D.