This is related to subset of finite set
A countably infinite set S is a set that has a bijection M to Z+ ={1,2,3...}. The problem is to show that a subset of such a set is countable, that is that it can be bijectively mapped to Z+ or to [n]={1,2,3... n}.
It's not clear to me what can be taken as given axioms for this problem.
It is possible to describe an algorithm that constructs such a mapping: The superset S maps to Z+, so start with the element that maps to 1 under M. For the map we are constructing, map it to one. Iterate ( infinitely) over the elements of S. For the k-th element, map it to the successor (i.e. add one) of the image of the k-1 th element.
This sounds like induction.
Is it permissible to describe an algorithm and call that a proof? Does it matter that the algorithm might have an infinite number of steps?
Let $M:S \to \mathbb{Z}_+$ be a bijection. Let $U \subseteq S$ and notice that $M:U \to M(U)$ is a bijection. So, proving that $U$ is countable is equivalent to prove that $M(U)$ is countable.
So we just need to prove that "Every subset $T \subseteq \mathbb{Z}_+$ is countable".
If $T$ is finite then the result follows. So suppose it is not the case and let's enumerate $T$. Choose $x_1 \in T$ to be the least element of $T$ (using the well-ordering principle). Now, suppose that $x_1 < x_2 < \cdots < x_n$ are defined and write $T_n=\{x_1, \cdots, x_n\}$. Since $T_n \subseteq T$ and $T$ is not finite we have that $R_n=T \setminus T_n \neq \emptyset$. So we define $x_{n+1}$ to be the least element of $R_n$(again using the well-ordering principle). Then if we show that $T=\{x_1, \cdots, x_n, \cdots \}$ we are done. Suppose there is $x \in T$ such that $x \notin \{x_1, \cdots, x_n, \cdots \}$. Then $x \neq x_n$ for all $n$. Hence $x \in R_n$ for all $n$ and $x > x_n$ for all $n$. So $x$ is a positive integer greater then all elements of $\{x_1, \cdots, x_n, \cdots \} \subseteq \mathbb{Z}_+$ which implies that $\{x_1, \cdots, x_n, \cdots \}$ is limited. This is a contradiction because $X \subseteq \mathbb{Z}_+$ is finite $\iff X$ is limited (You can check this). Hence $T=\{x_1, \cdots, x_n, \cdots \}$ as we wnated.