Dgdrxrt

I've seen a constructive proof based on induction that is awesome. But when I tried to prove it, I used a different approach. Can someone please verify my work? Thank you and any critic is highly appreciated!

It's a proven fact that $X$ is a countable set if and only if $exists f : mathbbN rightarrow X$ surjective. Therefore if $X$ is not a countable set then $nexists f: mathbbN rightarrow X$.

Since $X$ is infinite, it can be a (1) countable infinite set of an (2) uncountable infinite set.

(1) is trivial, since $X subset X$, the theorem is proved for this case.

(2) $X$ is an uncountable infinite set. We can conclude by our previous statement that $nexists f: mathbbN rightarrow X$ surjective. Therefore, for every function that maps $mathbbN$ to $X$ there'll be elements of $X$ that is not image of any $n in mathbbN$. Let's define a set of those elements:
$$
S:= x in X
$$
Now we can build a surjective function:
$$
F:=f|_f^-1(Xsetminus S) : f^-1(X setminus S) subset mathbbN longrightarrow X setminus S
$$
And by axiom of choice we can change the domain of $F$ by selecting for every $x in X setminus S$ only one element of $f^-1(X setminus S)$. That'll make $F$ a bijective function. Let $overlineF$ be that modified version of $F$ and $overlinemathbbN$ be the modified version $f^-1(X setminus S)$. Now we have:
$$
overlinemathbbN subset f^-1(X setminus S) subset mathbbN rightarrow overlinemathbbN subset mathbbN \
overlineF : overlinemathbbN longrightarrow X setminus S
$$
It's also a proven fact that every subset of a countable set is countable. Since $mathbbN$ is countable, then $overlinemathbbN$ is countable. By definition of countable set, we know that $exists g: mathbbN rightarrow overlinemathbbN$ bijective. Finally we can create a composition of functions to make a map from $mathbbN$ to $X setminus S$:
$$
h := overlineF circ g : mathbbN rightarrow X setminus S
$$
Since the composition of bijective functions is bijective, $h$ is also bijective and therefore $Xsetminus S subset X$ is countable.

From your statement "every subset of a countable set is countable", I presume you're using the term "countable" to include all finite sets, including the empty set. But with that definition, both (1) and (2) are trivial, because $ emptyset subset X $. So, while I think your proof does work, it's kind of like using a sledgehammer to crack a nut.

A more interesting question is how to prove that any infinite set contains a countably infinite subset. In that case you would need to modify your proof to choose a function $ f:mathbbNrightarrow X $ with an infinite range, and, as vxnture points out in his comment, simply asserting the existence of such a function would amount to begging the question. Nevertheless, I don't think it would take much more to adapt your proof to the countably infinite case. The existence of an injective function $ f:left1,2,dots,nrightrightarrow X $ is relatively trivial, and so you should be able to use Zorn's lemma to prove the existence of an injective function whose domain is the whole of $ mathbbN $, and whose range is a subset of $ X $.