Answer to Question #136814 in Discrete Mathematics for Promise Omiponle

Question

Show that a subset of a countable set is also countable

Answer 1

Remark. By a sequence , we mean a function $f$ defined on the set $J$ of all positive integer .

Solution:

Let $A$ be a countable set and $E$ be a subset of $A$ .

Claim: $E$ is countable

If $E$ is finite , then $E$ is obviously countable.

Suppose that $E$ is infinite set .

Arrange the elements $x$ of $A$ in sequence $\{ x_n\}$ of distinct elements. Construct a sequence $\{ n_k\}$ of positive integer as follows:

Let $n_1$ be the smallest positive integer such that $x_{n_1}\in E$ .Having chosen $n_1,n_2,.....n_{k-1}$ $(k=2,3,.......)$ ,let $n_k$ be the smallest positive integer grater than $n_{k-1}$ such that $x_{n_k}\in E$ .

Putting $f(k)=x_{n_k}$ $(k=1,2,3,......)$ we obtain a 1-1 correspondence between $E \ and \ J$ .

i,e, If $f(k_1)=f(k_2)$

$\implies x_{n_{k_1}}=x_{n_{k_2}}$

Hence $f$ is one one

Again for each $x_{n_k}$ there exist a positive integer $k$ form $J$

such that $f(k)=x_{n_k}$

Hence $f$ is onto.

Therefore $E$ is countable.