# Formal proof that $N$ is the smallest infinite set [duplicate]

I wish to write a formal proof of the following statement: For any infinite set $X$, there exists an injection $f:\mathbb{N}\to X$.

I'd like the proof to explicitly use the full axiom of choice (for every family of sets $\{S_\alpha\}$ there exists a family of elements $\{x_\alpha\}$ such that each $x_\alpha\in S_\alpha$). When this was asked before, none of the answers were explicit about where choice is invoked.

Motivation: I'm TAing a course in discrete math and was embarrassed to find that I can't prove this homework question.

## marked as duplicate by Asaf Karagila♦ axiom-of-choice StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 8 '15 at 0:34

• The axiom of choice comes in the difference between "no smaller infinite sets" and "every infinite set is larger". Both questions have been asked before, not just the one you linked to (which indeed doesn't use the axiom of choice). – Asaf Karagila Apr 8 '15 at 0:29
• There might be slightly better duplicates, but this one should work. Note that it proves the contrapositive of the statement. Something is finite if and only it doesn't have a countably infinite subset. Of course the two questions are easily isomorphic. – Asaf Karagila Apr 8 '15 at 0:35

A set $X$ is infinite if and only if there is an injection $\phi:X\to X$ that is not a surjection. In other words, $\phi$ misses out a nonempty subset $S_1$ of $X$. Let, $X_1:=X\setminus S_1$. $X_1$ must be infinite (because its bijectively related to $X$), hence there is a map $\phi_1:X_1\to X_1$ that is injective but not surjective, misses out nonempty $S_2\in X_1$, etc. (Induction will make the argument rigorous, and shows that $X_k\cap X_j=\emptyset$ for all $j\leq k$.) Axiom of choice helps "picking" $f(i):=x_i\in S_i$.

• No. Using this definition you don't need to use choice at all. A set is infinite if and only if it is not finite. – Asaf Karagila Apr 8 '15 at 0:34
• If I recall properly a definition, a set is finite if and only if it satisfies the pigeonhole principle, i.e., every injective map into itself must be surjective. – Oskar Limka Apr 8 '15 at 0:41
• Nope. You were taught with the axiom of choice in mind. A set is finite it is equinumerous with a proper initial segment of the natural numbers. We can prove that finite sets satisfy this principle, but the reverse implication is just slightly weaker than countable choice. – Asaf Karagila Apr 8 '15 at 0:43
• Certainly in this case. Choose one element $a$ not in the range of $\phi$, then let $a_n=\phi^n(a)$. You can show this is an injection from the natural numbers into your infinite set. No choice was used, since we only chose one injection and one element. – Asaf Karagila Apr 8 '15 at 0:47
• Ok. If one's happy to assume natural numbers (Axiom of Infinity?) before defining finite (and infinite), then one can take your definition as a starting point. But I thought the whole point was to define finite and infinite before introducing natural numbers. – Oskar Limka Apr 8 '15 at 0:50