# Thread: 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 $\displaystyle S$ such that $\displaystyle S \subseteq N$. Then there exists an injective function $\displaystyle f: S \longrightarrow N$ by definition. More specifically, define $\displaystyle f$ as:
$\displaystyle f(s_i) = i, i \in N$

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

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

Otherwise, if such an element $\displaystyle i_n$ does not exist, $\displaystyle f$ will not only be an injection but also a surjection, since for all elements $\displaystyle i \in N$, there exists an $\displaystyle s_i \in S$ such that $\displaystyle f(s_i) = i$. Since $\displaystyle f$ is both injective and surjective, it is a bijection, implying that $\displaystyle 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 $\displaystyle \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.

,

,

,

,

,

,

,

,

,

,

,

,

,

# prove that every subset of natural num is finite

Click on a term to search for related topics.