We say a set is countable if we can give the elements of the set in some step by step manner [each step (maps to a natural number) produces a result and hence the element produced in each step maps to a natural number]
$P$: Set of Rational numbers (positive and negative)
Let our rational numbers be of the form $\frac{p}{q}$. We output the rational numbers in steps such that we display all the rational numbers having a particular sum of $p$ and $q$ and then increase the sum value by $1$. i.e.
i=2
step=1
while(1)
{
for p = 1 to i-1
{
q=i-p
print (step : p/q)
print (step+1 : -(p/q))
step=step+2
}
i=i+1
}
So set in $P$ is countable.
------------------------------------------------------------------------------------------------------------------------------
$Q$: Set of functions from $\{0,1\}$ to $\mathbb{N}$
Let us consider possible functions from sets $A$ to $B$ where we assume that $A=\{0,1\}$ and set $B$ contains elements $\{0,1,..,i\}$ in pass $i$, such that in subsequent passes the size of $B$ increases by $1$ and in a pass we output all possible functions from $A$ to current $B$. i.e.
A ={0,1}
i=0
step =1
while(1)
{
B={0,1,...,i}
output the functions possible from A to B
in (i+1)^2 steps as there are (i+1)^2 functions
from A to B.
step=step+(i+1)^2
i=i+1
}
So set in $Q$ is countable.
------------------------------------------------------------------------------------------------------------------------------
$S$: Set of finite subsets of $\mathbb{N}$
Let us assume that in pass $i$ we consider the subset $A=\{0,1,…,i\}$ and we output all the possible subsets of $A$. i.e.
output the NULL set in step 1
i=0
step =2
while(1)
{
A={0,1,...,i}
output all possible subset of A except NULL set
i.e. 2^|A|-1 or 2^(i+1)-1 subsets of A in
2^(i+1)-1 steps.
step=step+2^(i+1)-1
i=i+1
}
Hence the set in $S$ is countable.
------------------------------------------------------------------------------------------------------------------------------
From these observations we see that option $(D)$ is the answer.
------------------------------------------------------------------------------------------------------------------------------
Now why is $R$ not countable? Let do some intuitive analysis similar to Cantor’s Diagonalization:
Let us assume that the set of functions from $\mathbb{N}$ to $\{0,1\}$ is countable. Thus we must have a listing methodology which lists all the functions possible in set. The figure below shows a such thing:
The matrix shows the values taken by function $f_i$ for the domain $\mathbb{N}$. By our hypothesis, this listing shall contain all possible functions. But take the diagonal marked in orange. Complement the bits in it. The string which we shall get does not corresponding to any row of the matrix above. So, we have found a function, which have not been listed by our methodology. So our assumption was wrong and the set in $R$ is not countable!!
