GATE CSE 2018 | Question: 27

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

Comments

https://mafiadoc.com/homework-10-solutions-which-of-the-following-are-countable-_5a0331e71723dd63441df951.html

---

Any set A is countable, if and only if |A| <= |N|, or if we make a function mapping from the elements of set A to the elements of N, then we must get either a bijection or an injection.

Alternatively, if all the elements of a set A can possibly be listed in a sequence, then also A is countable.

P = Set of rational numbers.

Now, we know that a rational number is of the form p/q, I can make an enumerating sequence of the elements of P as :- We take the value of |p| + |q|, where both p and q aren’t 0 and then assign that value to the same value in the natural number set, for the element 0 in rational numbers, we just assign it to an arbritrary element, say 1. Now, we can observe that there exists an injection between my enumerating sequence of Q and N, hence P is countable.

Q = Set of functions from {0, 1} to N.

Let my function f be such that f = {(0, a), (1, b)} (many such functions are possible, here a, b belong to N) and I make a mapping of f to the value (a + b) in the natural number set – thence, there exists an injection from Q to N, hence Q is countable.

R = Set of functions from N to {0, 1}

Here, |R| = 2 ^ |N|, where |N| is the cardinality of the natural numbers’ set. Now according to Cantor’s theorem, for any set A, |A| < |P(A)|, where P(A) is the power set of A and |P(A)| = 2 ^ |A|. Thus, |R| > |N| and this violates the 1^st definition given above and hence R is uncountable.

S = Set of finite subsets of N.

Here a mapping can be created as follows :- Take any finite subset and assign it to that element of N equal to the minimum element of that subset. Thus, again an injection has been obtained and hence, S is countable.

---

Note that this is not proof : I am explaining the statement
(R) : The set of all subsets of natural numbers, also known as the power set of natural numbers (denoted as ℘(ℕ) or 2^ℕ), is uncountable
Suppose if we considered that 0 is false and 1 is true and try to make function then ,

M = { {} ,{1} .{2} ,{3} ,…………..{1,1} ,{1,2} …….}

The first element  of M set  is the All natural number is 0 , that means no element is in the set and this could a function 1 .

The Second element of M set is the All natural number of set is 0 except 1 that’s why it is in the set ,that means only 1 element is in the set and this could a function 2 .

so on this way it creating such powerset which had such set of function . This is Uncountable set.

Answer 1

P: Set of Rational numbers are countable. Rational numbers are of the form $\frac{p}{q}$ where $p, q$ are integers. Enumeration procedure, take $p+q$ and write down all possible values(positive and negative).

Q: Set of functions from $\left \{ {0,1} \right \}$ to $N$. There are $N^2$ such functions. Hence countable.

R: Set of functions from $N$ to $\left \{ {0,1} \right \}$. There are $2^N$ such functions. Important theorem $\Rightarrow$

If a set $S$ is countable, then $\mathbb{P}(S)$ i.e $2^S$ is uncountable. 

Hence, statement R is uncountable.

S: Set of finite subsets of $N$. They are countable. Important theorem $\Rightarrow$

Every subset of a countable set is either countable or finite.

Hence, Option (D).

Comments

Its a theorem  cantors diagonalization theorem

---

I can't understand statement S.

 

In S: Set of finite subsets of N,

I know the Theorem that “Every subset of a countable set is either countable or finite”

But here they have not asked to Count a partiqular subset , they have mentioned the SET of all Finite SUBSETS, Means we have to count "HOW MANY FINITE SUBSETS ARE POSSIBLE"?

How can we count that??

Am i understanding the Concept completely Wrong?

---

The set of finite subsets is called Power set which has cardinality 2^n

Answer 2

Set of Rational numbers is countable whether positive or negative.

Reference: https://www.homeschoolmath.net/teaching/rational-numbers-countable.php

Set of function from $\{0,1\}$ to $N$ is countable.

Reference: https://mafiadoc.com/homework-10-solutions-which-of-the-following-are-countable-_5a0331e71723dd63441df951.html

Set of finite subsets of $N$ is countable.

Reference: https://math.stackexchange.com/questions/908222/the-set-of-all-finite-subsets-of-the-natural-numbers-is-countable

But set of functions from $N$ to $\{0,1\}$ is not countable.

Ans: D

Answer 3

 A countable set is either a finite set or a countably infinite set.

Countably infinite definition. A set is countably infinite if its elements can be put in one-to-one correspondence with the set of natural numbers. ... For example, the set of integers { 0 , 1 , − 1 , 2 , − 2 , 3 , − 3 , … } is clearly infinite.

Now,

P) is countably infinite. We can represent $\frac{a}{b}$ as $\left ( a,b \right )$ ordered pair and also it maps one to one correspondence mapping

https://math.stackexchange.com/questions/333221/how-to-prove-that-the-set-of-rational-numbers-are-countable

https://www.homeschoolmath.net/teaching/rational-numbers-countable.php

Q) Natural numbers are countable. So, it's squares are also countable

https://math.stackexchange.com/questions/1423918/why-are-natural-numbers-countable

(but set of all subset of natural numbers are uncountable

http://mathonline.wikidot.com/the-set-of-all-subsets-of-natural-numbers-is-uncountable)

R) Power set of natural number i.e.$2^{N}$ is uncountable

http://www.ee.iitm.ac.in/~krishnaj/EE5110_files/notes/lecture3_cardinality.pdf

S)finite subset of natural number are countable

but set of all subset of natural numbers are uncountable

Comments

Answer is D) P,Q and S are countable but you're saying "set of all subset of natural numbers are uncountable" in the last line?

---

@Sambhrant Maurya yes that statement is true. Hence strings are countable and languages are not countable. It can be proved by diagonalization.

---

Sambhrant Maurya

yes bcoz set of all subsets of natural numbers is nothing but the power set which is uncountable.

Answer 4

Just for your query:

Difference between Q, and R,
Q : Function from {0,1} to N
So number of functions = |N|^|{0,1}| = N^2

R : Function from N to {0,1}
So number of functions = |{0,1}|^N = 2^N

Comments

no its uncountable infinity search for cantors diagnolisation method for its proof

---

https://proofwiki.org/wiki/Rational_Numbers_are_Countably_Infinite

Here is the nice proof.

---

Can you example of functions possible