retagged by
21,690 views
52 votes
52 votes

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?

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

6 Answers

3 votes
3 votes
  • When S is countably infinite, $2^{S}$ is uncountable. So, R is uncountable

     
  • $N^{2}$ is countable. (Consider it as the set of squares of all natural numbers?). So, Q is countable.

     
  • N is countable. Hence all it's finite subsets are countable, too. (Powersets would create a problem, not subsets) So, S is countable.

     
  • It is well known that rational numbers are countable, while real numbers aren't.
    P is countable.

 

Option D

edited by
1 votes
1 votes

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!!

edited by
Answer:

Related questions

21 votes
21 votes
5 answers
1
Kathleen asked Oct 5, 2014
3,014 views
Every subset of a countable set is countable.State whether the above statement is true or false with reason.
28 votes
28 votes
4 answers
2
gatecse asked Feb 14, 2018
12,137 views
Let $G$ be a finite group on $84$ elements. The size of a largest possible proper subgroup of $G$ is _____