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

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.

• What's your definition of finite? Infinite? – BigbearZzz Aug 30 '16 at 21:05
• It really depends on the assumptions you make, and the definition of "infinite". – tomasz Aug 30 '16 at 21:13
• The definition of an infinite set we learned in the class above mentioned is a set for which there exists an injection mapping the set into itself which is not surjective, i.e., it is one-to-one not onto. Will add this definition into the question, but come on, does this question really deserve a vote down? Please let me know if there are other definitions of infinite that conflict with this one. – Rasputin Aug 30 '16 at 21:34
• Now that the OP has added which definition of "infinite" they're using, I disagree with the vote to close. – Noah Schweber Aug 30 '16 at 21:52
• I edited "an injective mapping... that is not injective" to "an injective mapping that is not surjective." – DanielWainfleet Aug 30 '16 at 22:23

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.

• Let me cough and suggest you re-read that very last sentence. :-) – Asaf Karagila Aug 30 '16 at 21:54
• @AsafKaragila I mean, it's true . . . :P – Noah Schweber Aug 30 '16 at 21:56
• That's better now. :-) – Asaf Karagila Aug 30 '16 at 21:57