Methods For Listing Countable Sets

Question

The most famous (non trivial) example of listing a countable set is the argument showing that the rational numbers are countable: $$ \begin{array}{cccc} \frac11 & \frac12 & \frac13 & \cdots \\ \frac21 & \frac22 & \frac23 & \cdots \\ \vdots & \vdots & \vdots & \cdots \end{array} $$ But there are other countable sets that are much harder to draw out in this way. Since we know that the union of countably many countable sets is itself countable, I wonder if there are any other ways to draw out an argument for their countability.

In particular, I am trying to list all polynomials with where each term has a coefficient of 1.

If I try a similar approach to the above I quickly run into problems. If each row indicates how many terms in the polynomial there are then: $$ \begin{array}{cccc} x^0 & x^1 & x^2 & \cdots \\ x^0+x^1 & x^0+x^2 & x^0+x^3 \\ \end{array} $$ we clearly have a problem since this cannot help with showing all combinations of binomials like $x^1+x^2$, listing them this way will always give $x^0$ as the first term.

So, all in all my question is:

What are some other ways to list countable sets?

Answer 1

I know this is not necessarily an answer to your question (other methods for listing countable sets), but here is a way to label the set of polynomials you described. You might find this approach useful.

Consider the polynomial $$a_n x^n + a_{n-1}x^{n-1} + \ldots + a_1 x^1 + a_0 x^0$$ where all the $a_n$ are 0 or 1. Write down the binary number $a_{n}a_{n-1}\ldots a_1a_0$. If you convert it to a decimal number, you have a way to label all the polynomials you described.

Example: the polynomial $x^3+x^2+x^1+x^0$ is the 7th polynomial, because 1111 is 7 in binary.

Edit: Now that I think about it, using the binary representation of positive integers, might be a useful approach to make a listing of a countable set.

Answer 2

What we usually do not find the exact formula for the listing but use a different set that you already listed to create the new list.

Let $A$ be a set you want to list(let's assume that you can list it). Let $B$ be a set you already listed, let $(a_n)_{n\in\Bbb N}$ be the listing for $B$ and $g$ be a bijective function from $B$ to $A$, then define the list for $B$ like the following: $b_n=g(a_n)$.

---

For example, let $A=\Bbb C$(all 3 tuples of natural numbers), and let $B=\Bbb N^2$, now define $g(z)=(\Re(z),\Im(z))$ and $a_n$ be the listing of cantor.

Then the listing of $\Bbb C$ will be $g(a_n)$.

I know that this is a simple example, this is the most I could think about in the moment without defining new listing.

---

Added:

Also, note that most of the times you won't find a list at all, you will know that $a_n$ exists by some different methods, and then you can use $a_n$ to show that there exists a listing for $A$ without finding him exactly, only finding it in terms of $a_n$