Show that a subsct of countable set is countable

Accepted Solution

Answer:We can prove this theorem as follows:Step-by-step explanation:Let [tex]A\subseteq S[/tex] where [tex]S[/tex] is a countable set.  So we can arrange the elements of [tex]S[/tex] as  a sequence [tex]S=\{x_{n}\}_{n=1}^{\infty }[/tex] we have the following cases:1. A is finite. If A is finite clearly it is a countable set. 2. A is infinite. Define the sequence of positive integers [tex]\{n_i\}_{i=1}^{\infty}[/tex] as follows:[tex]n_{1}[/tex] is the less positive integer such that [tex]x_{n_{1}}\in A[/tex][tex]n_{i}[/tex] is the less positive integer grater than [tex]n_{i-1}[/tex] such that [tex]x_{n_{i}}\in A.[/tex].Now, observe that the correspondence [tex]f(i)=x_{n_i},\,\,(i=1,2,3,...)[/tex] is a one-to-one correspondence between the elements of [tex]A[/tex] and [tex]\mathbb{N}[/tex]. So, [tex]A[/tex] is   a countable set.