Countability and sequences
I am having some trouble understanding my textbook in this passage:
"In particular, we see that if a set is countably infinite, then it is the range of an infinite sequence (but not conversely)".
It then proceeds to prove the proposition:
"A non-empty set is countable if and only if it is the range of an infinite sequence".
This seems to me like a contradiction. Can anyone supply me with an example of a set that is the range of an infinite sequence, but is not countable? If so, how does this not contradict the proposition posed? My thought is that it depends on the index of your sequence. If the sequence is indexed by naturals numbers (and hence countable), then the proposition holds. If the sequence is indexed by an uncountable set, then it may not hold. Is this reasoning correct?
$\endgroup$ 22 Answers
$\begingroup$The term sequence here means specifically a function whose domain is $\Bbb N$ (or possibly $\Bbb Z^+$, depending on the author’s conventions), so uncountable index sets are not in question here; the author’s not conversely is making a different point.
Note that every finite set is the range of a function with domain $\Bbb N$, though of course the function cannot be injective (one-to-one). For instance, the function that sends $0$ to $a$, $1$ to $b$, and every natural number $n\ge 2$ to $c$ is an infinite sequence whose range is the finite set $\{a,b,c\}$. The sets that are ranges of infinite sequences are the sets that are either finite or countably infinite. Thus, every countably infinite set is the range of an infinite sequence, but not every infinite sequence has a countably infinite range: some have finite ranges. Finally, countable means finite or countably infinite, and the finite and countably infinite sets are precisely the sets that are ranges of infinite sequences, so the proposition is indeed correct.
$\endgroup$ 2 $\begingroup$In some contexts, "countable" means countably infinite. If that were the intended meaning here, there would be a contradiction. However, often "countable" means finite or countably infinite. That appears to be the meaning here, and with this convention there is no contradiction.
To see why the converse of the first statement is false, note that the sequence $(0,0,0,\ldots)$ has finite range.
$\endgroup$
