What is an inductive proof that every set is either infinite, in bijection with a subset of $\mathbb{N}$, or empty?

Question

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.

Answer 1

First of all, re: definitions of infinite-ness: this is indeed not the usual definition. Usually, a set is finite iff it is in bijection with $\{1, 2, . . . , n\}$ for some $n$ (or empty). What you've described is Dedekind finiteness.

That said, here's an outline of the proof:

Suppose $A$ is not empty, or in bijection with any $\{1, 2, . . .n\}$. Then (exercise - show by induction that we never get "stuck") we can pick a sequence of elements $a_1, a_2, a_3, . . . , a_n, . . .$ ($n\in\mathbb{N}$) of distinct elements of $A$. Now consider the following function $f: A\rightarrow A$:

• $f(a_i)=a_{i+1}$.

• If $b\not=a_i$ for any $i$, then $f(b)=b$.

Exercise: use $f$ to show that $A$ is infinite.

Perhaps surprisingly, this proof implicitly uses the Axiom of Choice - specifically, in the construction of the sequence of $a_i$s. It is consistent with ZF ( = set theory without choice) that there is an infinite set which is not Dedekind-infinite.

---

How we are relying on the axiom of choice above? Well, we show by induction (this does not use Choice) that, in constructing the $a_i$s, we never "get stuck": that given any sequence $a_1, a_2, . . . , a_n$ of distinct elements of $A$, there is some $a_{n+1}\in A$ which is not equal to any of $a_1, a_2, . . . , a_n$. However, this just says that arbitrarily long finite strings of distinct elements of $A$ exist. Without the axiom of choice, we can't show that an infinitely long string of distinct elements exists. Basically, any time you want to continue some process "ad infinitum," and that process isn't completely well-defined (here we have many choices what e.g. $a_{17}$ should be), the axiom of choice is probably necessary.