# Math Help - Prove every subset of N is either finite or countable

1. ## Prove every subset of N is either finite or countable

Please critique my attempt at this proof below: if there is an alternative approach that is better or if there are gaps in the logic of my method, please point them out - thanks!

"Prove every subset of N is either finite or countable":
Proof : Consider a nonempty set of nonnegative integers $S$ such that $S \subseteq N$. Then there exists an injective function $f: S \longrightarrow N$ by definition. More specifically, define $f$ as:
$f(s_i) = i, i \in N$

This allows us to use $f$ to enumerate the elements of $S$ by their size: letting $s_1$ be the smallest element of $S$, $s_2$ be the smallest element of $S \backslash \{ s_1 \}$ and so forth inductively until we exhaust all the elements of $S$. Using $f$, we would have paired up $s_1$ with $1 \in N$, $s_2$ with $2 \in N$ and so forth.

If there exists an element $i_n$ of $N$ where $f^{-1}$ is undefined, as in, no element of $S$ maps to $i$, then $S \subset N$ and $card(S) < card(N)$, implying that $S$ is finite. More specifically, $S$ would have a finite cardinality of $i_n - 1$

Otherwise, if such an element $i_n$ does not exist, $f$ will not only be an injection but also a surjection, since for all elements $i \in N$, there exists an $s_i \in S$ such that $f(s_i) = i$. Since $f$ is both injective and surjective, it is a bijection, implying that $card(S) = card(N)$. So by definition, if there exists a bijection between a set and the natural numbers, that set is countably infinite in cardinality.

2. Yeah that's good.
Furthermore, using that $\mathbb{N}$ is a well-ordered set, your proof doesn't need the axiom of choice.

You could make it shorter considering "Prove that a non-finite subset of N is countable" instead of "Prove every subset of N is either finite or countable", but that changes almost nothing.