This takes work if you are willing to avoid choice. There is a theorem which says that a countable union of at most countable sets is at most countable. The proof of this results depends on choice. Instead there is a weaker result.

Theorem:Let be a sequence such that is at most countable. And let be a sequence such that enumerates i.e. is a surjection. Then is at most countable (i.e. is at most countable).

Proof:Define the function as . The function is onto and so is at most countable since the image of a countable set is at most countable (here we are using the result that is countable).

Let be the set of all finite subsequences of . We prove a stronger result.

Theorem:is countable.

Proof:Let represent all functions . Define by where . Then . Therefore by above if we can produce then would be countable. Let beanybijection - we know one such exists. Define in following way. Define to be the set of all one-element sequences i.e. is the function defined by . Define recursively at a point by first letting and then to be the element sequence whose first elements are the terms of the sequence and the element is . It remains to show that is an enumeration of for . Of course we avoided since that is the empty sequence (empty sequence) and does not alter the cardinality in question. Therefore, is at most countable. There is just one last step and that is to find such a set which contains all these to complete the proof.