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.

  • $\begingroup$ 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. $\endgroup$
    – vxnture
    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\ $.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.