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

so are they countable?

---

What is the correct answer for the above question ?

---

i mark d

---

what i think is for countable sets there should be an enumeration method from 0,1 to N we can generate the functions in an order like in order of increasing sum of naturals numbers but from N to 0,1 we cannot as we can never reach till the end of N in the domain to find the corresponding mapping to {0,1}  during the enumeration as its an infinite set hence the answer MIGHT BE D as we know rational numbers are countable

---

D was the correct choice 1,2,4 are countable

---

How you people are taking both negative and positive rational number is countable.

For the positive rational number, you can enumerate it but how to do for both positive and negative rational number simultaneously.Question is asking for both positive and negative rational number.

---

dont u think for every positive rational number there will be a corresponding negative rational number which makes them also countable ?? there is a one to one correspondence right

---

Is set of Real numbers is countable?

---

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