In a math class I took the professor said that for every set $S$, exactly one of the following is true:
- $S$ is infinite
- $S$ is in bijection with the set $\{m\in\mathbb{N}\ |\ {m\leq{n}}\}$ for some $n\in\mathbb{N}$
- $S$ is the empty set
He said the proof is "a careful induction." But what exactly would this induction be? I'm not quite sure what we would be inducting on -- perhaps number of elements in the set? But then the logic of the proof seems circular . . .
Note: The definition of an infinite set $S$ that we were given in this class is that there exists an injective mapping $\ f: S \rightarrow S$ which is not surjective. The definition of a finite set we were given is a set that is not infinite.
E.g., for $\mathbb{N}$ we can use the mapping $f: n \mapsto n+1$. This mapping is injective since $m+1=n+1$ implies $m=n$, but it is not surjective since there is no natural number $n$ such that $f(n)=1$. Therefore, $\mathbb{N}$ is infinite.
Of course, there are various infinite cardinalities -- $\aleph_0$, $\aleph_1$, etc. -- but that's not what this question is about.