Countable vs Recursively Enumerable Sets

Question

I've been reading that recursively enumerable sets are countable (enumerable in the general sense), but not vice a versa, when there is no function for the enumeration. Could you describe exactly how this can be? If there is a method for counting all the elements, how can there be no function to do so?

Answer 1

There are uncountably many countable subsets of the natural numbers (since you can apply the diagonal argument to the set of countable sequences), but only countably many recursively enumerable ones (since they correspond to finite algorithms, which you can enumerate).

There’s no contradiction there. That you see a contradiction may be related to your imprecise use of “method” and “function”. A set is countable if there is a bijection between it and the natural numbers. The existence of a bijection doesn’t imply the existence of a finite algorithm that specifies the bijection.