1
$\begingroup$

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.

Thanks

  • 2
    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.2012-09-30
  • 0
    A sequence is an application from $\mathbb{N}$ to something else. If you have a surjection, that surjection can be used as your sequence...2012-09-30
  • 2
    Isn't a surjection from ${\Bbb N}$ to $A$ exactly the same thing as a sequence whose values are the whole of $A$?2012-09-30
  • 0
    What definition have you learned for "at most countable"?2012-09-30
  • 0
    The definition I learned for at most countable is this: A is at most countable is A is finite or countable.2012-09-30
  • 0
    I know a sequence is just a function with domain N. But I just don't know how to properly define that surjection as a sequence.2012-09-30
  • 0
    Would this be an appropriate answer:2012-09-30
  • 0
    Assume that $ A $ is at most countable. Then there exists a surjection $ f : \Bbb N \to A $ by $ f(n) = a_n $ for each $ n \in \Bbb N $, such that $ a_n \in A $ for all $ n $. Then, $ A = \{a_n : n \in \Bbb N \} $.2012-09-30
  • 0
    @NeilReed: That's basically right. You might want to say something like, "There exists a surjection $f:\mathbb{N}\rightarrow A$. We *define* $a_n$ to be equal to $f(n)$, then $a_n$ is the desired sequence."2012-09-30
  • 0
    Thanks Kevin. I'm sorry if this seemed trivial.2012-09-30

1 Answers 1

1

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} as index $n=k_{n}$ for $a_{n}$ you are done.

  • 0
    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...2012-10-06
  • 0
    $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 set2012-10-06