# 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.

• Are you assuming $f$ is injective? Because even in your definition, there is always a surjective function from $\mathbb{N}$ to any finite set, so countable could also mean finite. So for your proof to work you would have to assume that $f$ is injective, but this seems equivalent to saying $X$ has a countably (infinite) subset. Mar 31 '19 at 10:28

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\$$.