# Do we need the axiom of choice to well-order a set with countably many elements?

Say I index a countably-infinite set $A$ bijectively with the positive integers so that $$A=\{a_1, a_2, a_3,\dots\}$$ The indexing gave an order to the set. Was the choice axiom used?

-
No. The function that verifies that the set is countably infinite suffices. – Michael Greinecker Aug 27 '12 at 12:03
@MichaelGreinecker: Would you mind elaborating, please? I don't quite follow what you mean. – Acid2 Aug 27 '12 at 12:05
What Asaf wrote. – Michael Greinecker Aug 27 '12 at 12:23

No. There is no need for the axiom of choice. This is essentially by definition.

The definition of countability is to have an injection into $\omega$. Generally speaking if $A$ is a set, $\alpha$ is well-ordered and $f\colon A\to\alpha$ is an injection then $A$ can be well-ordered.

Proof. Fix a well-ordering of $\alpha$, $\prec$ and define $a<b\iff f(a)\prec f(b)$. Since $f$ is injective we can easily see this is an order-embedding and therefore $<$ is a well-ordering of $A$.

In the particular case of a countable set, we can write $A=\{a_n\mid n\in\mathbb N\}$ so we can define an order on $A$ as follows: $$a_m\prec a_n\iff m<n$$ Given a non-empty $B\subseteq A$ there is a least natural number $k$ such that $a_k\in B$, and therefore $a_k$ is the minimal element $\prec$ in $B$.

-
What if we define countable to mean "surjection from $\omega$"? – Zhen Lin Aug 27 '12 at 12:38
@ZhenLin: These two are of course equivalent. If $A$ is a set, $\alpha$ is well-ordered and $f\colon\alpha\to A$ is a surjective function, define $g\colon A\to\alpha$ by $g(a)=\min\{\beta\in\alpha\mid f(\beta)=a\}$. This is an injective function and we return to the previous case. – Asaf Karagila Aug 27 '12 at 12:40
@ZhenLin: The empty set will feel so proud for being uncountable. – Michael Greinecker Aug 27 '12 at 12:51
@MichaelGreinecker: Sometimes even nonempty finite sets don't get to be countable. I don't think authors who define "countable" as "equinumerous with $\mathbb N$" go as far as to consider finite sets to be uncountable, though. – Henning Makholm Aug 27 '12 at 15:13
@HenningMakholm: I'm aware that many peple use countable and countably infinite synonymously. But defining countable to be countably infinite or both finite and nonempty seems odd to me. – Michael Greinecker Aug 27 '12 at 15:16