in Set Theory & Algebra retagged by
17,269 views
43 votes
43 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
in Set Theory & Algebra retagged by
by
17.3k views

4 Comments

try gateoverflow's previous year question bank!
0
0

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.

2
2

6 Answers

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

4 Comments

Its a theorem  cantors diagonalization theorem
0
0
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?
2
2
The set of finite subsets is called Power set which has cardinality 2^n
0
0
14 votes
14 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

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

3 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?
0
0

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

1
1

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

0
0
9 votes
9 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

4 Comments

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

Related questions