retagged by
21,666 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

75 votes
75 votes

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

edited by
15 votes
15 votes

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

15 votes
15 votes

 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

11 votes
11 votes
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
Answer:

Related questions

21 votes
21 votes
5 answers
1
Kathleen asked Oct 5, 2014
3,007 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,130 views
Let $G$ be a finite group on $84$ elements. The size of a largest possible proper subgroup of $G$ is _____