Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
1  
What Asaf wrote. –  Michael Greinecker Aug 27 '12 at 12:23

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
What if we define countable to mean "surjection from $\omega$"? –  Zhen Lin Aug 27 '12 at 12:38
2  
@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
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. –  Michael Greinecker Aug 27 '12 at 15:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.