17,269 views

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

try gateoverflow's previous year question bank!

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 1st 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.

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

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

Set of Rational numbers is countable whether positive or negative.

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

Set of finite subsets of $N$ is countable.

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

Ans: D

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

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

by

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.

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

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

no its uncountable infinity search for cantors diagnolisation method for its proof
Can you example of functions possible