Prove that every infinite set has a countable subset (non constructive proof) 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 : \mathbb{N} \rightarrow X$ surjective. Therefore if $X$ is not a countable set then $\nexists f: \mathbb{N} \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: \mathbb{N} \rightarrow X$ surjective. Therefore, for every function that maps $\mathbb{N}$ to $X$ there'll be elements of $X$ that is not image of any $n \in \mathbb{N}$. Let's define a set of those elements:
$$
S:= \{x \in X | f(n) \neq x \text{ } \forall n \in \mathbb{N} \}
$$
Now we can build a surjective function:
$$
F:=f|_{f^{-1}(X\setminus S)} : f^{-1}(X \setminus S) \subset \mathbb{N} \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 $\overline{F}$ be that modified version of $F$ and $\overline{\mathbb{N}}$ be the modified version  $f^{-1}(X \setminus S)$. Now we have:
$$
\overline{\mathbb{N}} \subset f^{-1}(X \setminus S) \subset \mathbb{N} \rightarrow \overline{\mathbb{N}} \subset \mathbb{N} \\
\overline{F} : \overline{\mathbb{N}} \longrightarrow X \setminus S
$$
It's also a proven fact that every subset of a countable set is countable. Since $\mathbb{N}$ is countable, then $\overline{\mathbb{N}}$ is countable. By definition of countable set, we know that $\exists g: \mathbb{N} \rightarrow \overline{\mathbb{N}}$ bijective. Finally we can create a composition of functions to make a map from $\mathbb{N}$ to $X \setminus S$:
$$
h := \overline{F} \circ g : \mathbb{N} \rightarrow X \setminus S
$$
Since the composition of bijective functions is bijective, $h$ is also bijective and therefore $X\setminus S \subset X$ is countable.
 A: 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:\mathbb{N}\rightarrow 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:\left\{1,2,\dots,n\right\}\rightarrow 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 $\ \mathbb{N}\ $, and whose range is a subset of $\ X\ $.
