1
$\begingroup$

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?

  • 1
    What Asaf wrote.2012-08-27

1 Answers 1

5

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. 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 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$.

  • 1
    @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.2012-08-27