Ways of enumerating a countable set

Question

My questions are about enumerating countable sets.

Say we have a countable set $X$.

1. How many ways are there of enumerating X?
2. It seems to me, just based on the examples i've seen in maths so far, that most of the time, it doesn't matter too much how you enumerate a set if it's countable, when you're trying to later do something with the set. Are there any situations in mathematics when the actual enumeration might matter?

The only situation I can think of that is sortof related to this has to do with decidability and effective procedures in logic. Say we have a set of expressions $A$ in some language $L$, and say we have an effective procedure that, given any expression $\epsilon$, produces the answer "yes" iff $\epsilon \in A$. If we want to create a listing of $A$, we can enumerate all expressions in our language. Say this enumeration is $\epsilon_{1}, \epsilon_{2}, \cdots$. Spend one minute testing $\epsilon_{1}$. Then spend 1 minute testing $\epsilon_{2}.$ Go back to testing $\epsilon_{1}$ again for a minute. Then $\epsilon_{2}$, then $\epsilon_{3}$, then back to $\epsilon_{1}$, (etc)...Whenever our procedure outputs "yes" for an expression, put it in our list. In this way, anything in $A$ will eventually appear in our list. (this is in Enderton's "mathematical intro to logic)

Thanks for any help/examples!

Sincerely,

Vien

Answer 1

If $X$ is countably infinite, there are $2^\omega=\mathfrak{c}$ bijections from $\omega$ to $X$ and hence $2^\omega$ different enumerations of $X$.

There are times when you want an enumeration that has some specific property. For instance, suppose that you want to enumerate all finite strings over some finite alphabet of symbols. There are countably infinitely many such strings, but you might want specifically an enumeration $\{\sigma_n:n\in\Bbb N\}$ such that if $\sigma_m$ is shorter than $\sigma_n$, then $m<n$. In other words, the empty string must be $\sigma_0$; if there are $k$ symbols, $\sigma_1$ through $\sigma_k$ must be the one-symbol strings in some order; and so on.

Answer 2

If $X$ is countable then there exists a bijection $f\colon\Bbb N\to X$. Now given any permutation of $\Bbb N$, $\pi$ we have $f\circ\pi\colon\Bbb N\to X$ is a different bijection.

Since there are $2^{\aleph_0}$ permutations of $\Bbb N$ there are $2^{\aleph_0}$ ways to enumerate a countable set.

If you want to allow longer order types, then there are $\aleph_1$ countable ordinals, each having $2^{\aleph_0}$ permutations, so we have $2^{\aleph_0}\cdot\aleph_1$ ways to well-order a countable set. If we assume the axiom of choice still amounts to $2^{\aleph_0}$.

Now as for your second question, mostly we don't care. It is true. But sometimes we do. In the context of recursive sets, we can talk about recursive enumerations, but there are only $\aleph_0$ of those. Usually we want to argue that the set of "good enumerations" is non-empty, then we don't care which of the good enumerations we have chosen. Sometimes, however, this set is a singleton and sometimes empty.