Question

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. P, Q and S only
• B. P and S only
• C. P and R only
• D. Q and S only

Answer 1

The correct option is A P, Q and S only

$P:$
Set of rational number $\to$ countable
$Q:$
Set of functions from {0, 1} to $N\to N$
0 can be assigned in N ways
1 can be assigned in N ways
There are $N\times N$ functions, cross product of countable set in countable.
$R:$
Set of functions from N to {0, 1}

Each of thus boxes can be assigned to 0 or 1 so each such function is a binary number with infinite number of bits.
Example: 0000 ..... is the binary number corresponding to 0 is assigned to all boxes and so on.
Since each such binary number represents a subset of $N$ (the set of natural numbers) by, characteristic function method, therefore, the set of such function is same as power set of $N$ which is uncountable due to Cantor's theorem which says that power set of a countably infinite set is always uncountably infinite.
$S:$ Set of finite subsets of $N\to$ countably infinite since we are counting only finite subsets. So P, Q and S are countable.