Please check my proof that subset of countable set is countable

153 Views Asked by At

enter image description hereSo, $ n_2 = \min ( (n \in \mathbb{N} |f(n) ) - f(n_1) ) $

So $ n_{i-1} = \min ( (n \in \mathbb{N} |f(n) ) - f(n_1) ) $

Define $g : \mathbb{N} \to A$

$g(1)= f(n_1)$

$g(i)=f(n_i)$

To check g is one - one fucntion

Assume $g(i)=g(j)$

$\implies f(n_i)=f(n_j)$

$\implies n_i=n_j$ (As f is one one)

$\implies i = j $ (I am not quite sure about this step )

To check f is ONTO

Consider $f(n_i) \in A$. Since $A \subseteq B$. So $f(n_i) \in B$

Since f in Onto. So $\exists a n \in \mathbb{N} $ such that $n_i \in N $ for some $i$.

Is this correct ? Thanks

1

There are 1 best solutions below

6
On BEST ANSWER

The proof is correct. The intuition is that if $B$ is countable, then one can enumerate the elements of $B$ using natural numbers: $$ b_0, b_1, \ldots, b_n, \ldots \in B.$$ Formally, there is a function $f: \mathbb{N} \to B$. You can think that $b_n = f(n)$, if you want to.

If $A$ is an infinite subset of $B$, then every element $a$ in $A$ will be equal to $f(n)$ for some unique $n$. Thus you can enumerate the elements in $A$, using the enumeration $f$ of $B$. This enumeration is the function $g$ that you have defined.

Note that the assumption that $A$ is infinite is required: otherwise the definition of $g$ wouldn't work.