Mathematics: CSIR Solved Problems on countable and uncountable sets and some other questions for practice.

Questions Asked in CSIR-NET on Countable and Uncountable Sets

1. Let $A=\{x^2:0<x<1 \}$ and $B=\{x^3:1<x<2 \}$. Which of the following statement is true?

1. there is one to one, onto function from $A$  to $B$.
2.  there is no one to one and onto function from $A$ to $B$ taking rationals to rationals
3.  there is no one to one from $A$ to $B$ which is onto.
4.  there is no onto function from $A$ to $B$ which is one to one.

Solution: $A=(0,1)$ and $B=(1,8)$. both are open subset of $\mathbb{R}$. So, 1st option is correct. Two open sets of real numbers are numerically equivalent to each other.

2.Let $X$ be a connected subset of real numbers. If every element of $X$ is irrational, then the cardinality of $X$ is

1.  infinite
2.  countably infinite
3.  $2$
4.  $1$

Solution: Between any two irrational number there must exists a rational number. So 4th option is correct.

3.Consider the following sets of function on $\mathbb{R}$

$W =$ The set of constant functions on $\mathbb{R}$

$X =$ The set of polynomial functions on $\mathbb{R}$

$Y =$ The set of continuous functions on $\mathbb{R}$

$Z =$ The set of all functions on $\mathbb{R}$

Which of these sets has the same cardinality as that of $\mathbb{R}$?

1. Only $W$
2.  Only $W$ and $X$
3.  Only $W,X$ and $Z$
4. Only $W, X, Y$ and $Z$

Solution: Cardinality of set of constant function is equal to $\mathbb{R}$. That is, Cardinality of $W$ is equals to $R$. we can define a map from $R^n\rightarrow \sum_{i=0}^{n} a_i X^{n-i}$ and you can easily check that this function is bijective, which means that set of n degree polynomial is equivalent to $R^n$  and cardinality of $R^n$ is equivalent to $R$.

now if we talk about set of all polynomial function on $R$ then that would be equivalent to $\cup_{i=1}^n R^i$ which is equivalent to power set of $\cup_{i=1}^n R =R$ whose cardinality is $c$

4. Which of the following sets of the functions are uncountable?

1. {$f|f:\mathbb{N}\rightarrow${$1,2$}}
2. {$f|f:$ {$1,2$}$\rightarrow$ $\mathbb{N}$}
3. {$f|f:$ {$1,2$}$\rightarrow$ $\mathbb{N}$, $f(1)\leq f(2)$}
4. {$f|f:\mathbb{N}\rightarrow${$1,2$}, $f(1)\leq f(2)$}

Solution:$f:\mathbb{N}\rightarrow${$1,2$}. This means that some subset of $N$ is mapped of $1$ and it's compliment is mapped to $2$. So that means there are as many function are possible as the subsets of $\mathbb{N}$. Which is uncountable. So 1st one is Uncountable.

2nd one is countable. Actually $1$ can be mapped to any natural number and $2$ an be mapped to any natural number. So this is basically.$\mathbb{N}\times \mathbb{N}$. So, It's countable. Since third one is special case of 2nd one. So it is also countable. In the 4th option, we are just restricting the value of $f(1)=2$. But even if we eliminate this case. by the similar logic discussed above, it will remain uncountable. So, 4th one is uncountable.

Some More questions For Practice: (these Questions are collected from Math.stackexchange.com)

5.Let $X$ be the set roots of unity in $\mathbb C$. Let $S(X)$ be the set of all sequences of elements in $X$. Which of the following subset of $S(X)$ is countable ?

1. The set $\ \ A \ \ $ of all $(x_n) \in S(X)$ such that $(x_n)$ is an eventually constant sequence .

2. The set $\ \ B \ \ $ of all $(x_n) \in S(X)$ such that $x_n = 1$, whenever n is prime number.

3. The set $\ \ C \ \ $ of all $(x_n) \in S(X)$ such that each $x_n$ is 26th root of unity .

4. The set $\ \ D \ \ $ of all $(x_n) \in S(X)$ such that $x_{2n} = 1$ for all n$\geq$ 1 .

Solution: Option 1 is countable since there exists, a finite number of roots of unity.

The set of all sequence $S(X)$ is uncountable. And by assigning $x_n=1$ to every prime number, we are eliminating countable cases of $S(X)$. (since prime numbers are countable.) So 2nd option is uncountable. For, second root of unity also, the sequence is similar to the binary sequence , which is uncountable.

3rd option, Just take any two roots of 26th roots of unity and form all possible sequence. (It's similar to binary sequence).

It will be uncountable. So third option is un-countable.

In the 4th option we are assigning 1 to even terms and nth roots of unity at odd places. but odd numbers are numerically equivalent to set of natural number so this case is similar to previous one. So,it is uncountable.

6.Is the set:

$S=\{\text{Sequences of functions } \mathbb N\to\mathbb R\}$

countable or uncountable?

Solution: Uncountable. It is equivalent to $\mathbb{R}$.

7.Which of the following sets are countable:

(a) $\mathbb{Z}^{[0,1]}$

(b) $[0,1]^{\mathbb{Z}}$

(c) $\mathbb{Z}^{\mathbb{Z}}$

(d) the set given by functions $f:\mathbb{Z}\to\mathbb{R}$ such that $f(n)\neq0$ only for finitely $n$ (otherwise zero),

(e) the set given by functions $f:\mathbb{Z}\to\mathbb{Z}$ such that $f(n)\neq0$ only for finitely $n$ (otherwise zero).

Solution:  $\mathbb{Z}^{[0,1]}$ denotes the set of functions from $\mathbb{Z}$ to $[0,1]$. $[0,1]$ is equivalent to $\mathbb{R}$ . So this is uncountable.

Similarly (b) is  also uncountable.

(c) see question no 13.

(d) is uncountable Since, we are taking intersection of $\mathbb{R}$ Finite times.

(e)Countable. Finite intersection of countable sets is countable.

8.Which of the following sets are finite? countably infinite? uncountable? 

(a) $\{1/n: n \in \mathbb{Z} \setminus \{ 0 \} \}$;

(b) $\mathbb{R} \setminus \mathbb{N}$

(c) $\{x \in \mathbb{N}: \lvert x-7\rvert > \lvert x \rvert \}$;

(d) $2\mathbb{Z} \times 3 \mathbb{Z}$

Solution: 

(a) Countable there exists a bijection from this set to Set of natural number. Function defined by $f(x)=1/x$

(b) Uncountable. (Irrational number)

(c) Solving equation we get: $2x<7$ Hence finite.

(d) Cartesian product of countable set is countable. Hence Countable.

9. Which of the following are countable, finite ,uncountable?

a) $[0,1] \cap \mathbb Q$

b) $P(\mathbb Q)$

c) $\mathbb R \setminus \mathbb Q$

d) $\{(a, b) \in \mathbb R\times\mathbb R | a, b \in\mathbb N\}$

Solution:

a) any intersection between two sets where one if countable must be countable

b) by definition, any power set of $\mathbb Z, \mathbb Q, \mathbb N$ is not countable

c) $\mathbb R\setminus \mathbb Q$ does not remove the irrational numbers from $\mathbb R$ hence it remains uncountable.

d) Countable. Since $\mathbb{N}\times \mathbb{N}$ is countable.

10.Determine whether the following sets are countable:

1. Collection of all finite subsets of $\mathbb N$
2. The collection of all functions from $\mathbb N$ to $\mathbb R$
3. Collection of all roots of polynomials in single variable over $\mathbb Z$

Solution: 

The collection of finite subsets of N=Union of subsets of N of order 1,2,3..
Subsets of N of order 1,2,3 etc. are all countable.
So The collection of finite subsets of N, being countable union of countable sets should be countable.

Second option is uncountable.

Countable. Since the set of Algebraic number is countable.

11. The numbers of the form $\sum_{k=1}^{\infty} \frac{a_j}{3^k}$ , where $a_j = 0$ or $a_j = 1$ or $a_j=2$ is countable or Uncountable?

If $A = \cap_i^n A_1$ is countably infinite, then atleat one $A_i$ is countable. (True /False)

Solution: This this the set of real number, written in the base of $3$. So It is uncountable.

2nd one is false since intersection of positive reals and negative reals is $\phi$ .

12. If $E$ is infinite and countable and $E=\bigcup_{i=1}^{\infty} E_i$ then which of the following is/are correct?

1. at least one $E_i$ is infinite

2. infinite number of $E_i$'s are infinite,

3. no $E_i$ need be infinite

4. if $E_i$'s are pairwise disjoint ,then at least one $E_i$ is infinite.

Solution: Third option is correct. since infinite union of {1},{2}..... gives set of natural number, which is countable infinite.

13.Suppose we have the following sets, and determine whether they are countably infinite or uncountable .

1. The set of all functions from $\mathbb{N}$ to $\mathbb{N}$.

2. The set of all non-increasing functions from $\mathbb{N}$ to $\mathbb{N}$.

3. The set of all non-decreasing functions from $\mathbb{N}$ to $\mathbb{N}$.

4. The set of all injective functions from $\mathbb{N}$ to $\mathbb{N}$ to $\mathbb{N}$.

5. The set of all surjective functions from $\mathbb{N}$ to $\mathbb{N}$.

6. The set of all bijection functions from $\mathbb{N}$ to $\mathbb{N}$.

Solution: 

1.See the question 4(1): the set defined here is subset of the set defined in 4(1). So, It's uncountable.

2. Define

$S_N:=\{f:\mathbb{N}\to\mathbb{N}\;|\; f \text{ is non-increasing and } f(1)\leq N\}$

Then, your set is

$S=\bigcup_{N=1}^\infty S_N$

Since a union of countable sets is countable, it suffices to show that each $S_N$ is countable. Now, argue by induction on $N$

3. It is uncountable. Since Set defined in option  2 is countable and 1 is uncountable so, It must be uncountable.

Alternatively,

There are uncountably many infinite sequences of $0$'s and $1$'s. Indeed there are continuum many. For any such sequence $a_1,a_2,a_3, \dots$, we define a function $f$ from $\mathbb{N}$ to $\mathbb{N}$ as follows.

Let $f(1)=a_1+1$. For any $k\gt 1$, let $f(k)=f(k-1)+a_k$. This function is non-decreasing, and two different sequences $a_1,a_2,\dots$ and $b_1,b_2,\dots$ give rise to different functions.

We have described an injection from the set of sequences of $0$'s and $1$'s to the set of non-decreasing functions from $\mathbb{N}$ to $\mathbb{N}$. So the second set has cardinality greater than or equal to the cardinality of the first.

4. The set of bijective function from $\mathbb{N}$ to $\mathbb{N}$ is uncountable and set defined in option  4,5 are superset of this case. So they all are uncountable.