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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm having trouble finding a proof (without the need for cases) for this statement: If A is at most countable, then there is a sequence $(a_n)_n$ such that $ A = \{a_n : n \in \Bbb N \} $.

I know that there exists a surjection from the naturals onto A, but can we then define that surjection as a sequence?

I know this should be simple. But I just don't know how to write a nice, technically sound proof.


share|cite|improve this question
That surjection is a sequence. A sequence is nothing but a function with domain $\mathbb{N}$. For the sake of pedantry: Only at most cuntable, nonempty sets can be arranged as a sequence. – Michael Greinecker Sep 30 '12 at 18:40
A sequence is an application from $\mathbb{N}$ to something else. If you have a surjection, that surjection can be used as your sequence... – xavierm02 Sep 30 '12 at 18:40
Isn't a surjection from ${\Bbb N}$ to $A$ exactly the same thing as a sequence whose values are the whole of $A$? – user22805 Sep 30 '12 at 18:42
What definition have you learned for "at most countable"? – vesszabo Sep 30 '12 at 18:48
The definition I learned for at most countable is this: A is at most countable is A is finite or countable. – mkeachie Sep 30 '12 at 19:04
up vote 1 down vote accepted

By definition there must be a injection to the set of natural numbers. So there is a uniq natural number $k_{n}$ asigned to each element of the set. Taking this numbers from smallest to biggest $k_{1}<k_{2}<\cdots<k_{n}$ as index $n=k_{n}$ for $a_{n}$ you are done.

share|cite|improve this answer
You are not done yet, there are two small problems to face... For example, if $k_1=2011$, what is $a_1$?Also, if the set is finite, you don't get a sequence, because you only get finitely many indices... – N. S. Oct 6 '12 at 19:44
$a_{1}=f^{-1}(2011)$. If the set is finite you could asign the last element of the set to all naturals that are left. So sequence would have infinite equal elements $k_{n}$ for $n$ bigger then the cardinality of the set – Mykolas Oct 6 '12 at 19:50

Your Answer


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.