Dark Mode

17,269 views

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?

- $Q$ and $S$ only
- $P$ and $S$ only
- $P$ and $R$ only
- $P, Q$ and $S$ only

2

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.

2

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

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?

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

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.

Set of finite subsets of $N$ is countable.

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

Ans: D

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

0

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

1