# Is the set of ordered tuples of integers countable?

By ordered tuples, I mean say [1, 2, 2, 3] or [-9, 3, 5]. I have a hunch that it is because one can order them...

-
You might take a look at my answer to another question, which is similar, but simpler. It might help give you some intuition for a starting place for your problem. – Carl Morris Oct 1 '12 at 2:05

Yes, that set is certainly countable (assuming you mean tuples with a finite number of entries). But the fact that you can order them is nothing to do with this. Indeed, you can order the real numbers, but there are uncountably many real numbers.

To show that the set of ordered tuples is countable, you can use the lemma that any union of countably many countable sets is also countable. Then apply this lemma inductively to show that the number of tuples with $n$ entries is countable for all $n$. Lastly, apply the lemma one more time to show that the number of tuples with any number of entries is countable.

Update

As per @Ralph's excellent comment on my answer, I missed an important step in my original argument. To show that a countable union of countable sets is countable requires either the axiom of countable choice, or it requires us to actually have surjections from $\Bbb N$ (or some other known countable set) to each of the sets of which the union is comprised.

To remedy this, I offer the following argument.

Lemma

Let $f$ be a surjection from ${\Bbb Z}^+$ to some set of sets $S$, and for each $n\in {\Bbb Z}^+$, let $g_n$ be a surjection from ${\Bbb Z}^+$ to $f(n)$. Then $h$ is a surjection from ${\Bbb Z}^+$ to $\displaystyle \bigcup_{n\in{\Bbb Z}^+} f(n)$ where $h$ is defined as follows, for positive integers $m,n$ with $m\leq n$. $$h\left(\frac{(n-1)(n-2)}{2}+m\right) = g_m(n+1-m)$$ Note that by choosing different values of $m,n$, we can make the argument to $h$ on the left hand side equal any positive integer, and the value on the right be any element of any of the $f(m)$. So the image of $h$ is the union of all of the $f(m)$, as required.

Now, suppose that there is a surjection $h_k$ from ${\Bbb Z}^+$ to the set of tuples of $k$ integers. This is true for $k=1$, since we can write $h_1(1)=[0], h_1(2)=[-1], h_1(3)=[1], h_1(4)=[-2], h_1(5)=[2]$ and so on. That is, the odd numbers map to non-negative integers in increasing order and the even numbers map to negative integers in decreating order.

Use the lemma above, where $f(n)$ is the set of tuples of $k+1$ integers whose last entry is $h_1(n)$, and let $g_n(m)$ be the tuple whose first $k$ entries are the entries of $h_k(m)$. This gives a new surjection $h_{k+1}$ from ${\Bbb Z}^+$ to the set of tuples of $k+1$ integers. The principle of mathematical induction then gives us the existence of such a surjection $h_k$ for all $k\in{\Bbb Z}^+$.

Lastly, use the lemma one more time, where $f(n)$ is the set of tuples of $n$ integers and $g_n(m) = h_n(m)$. This gives us a surjection from ${\Bbb Z}^+$ to the set of ALL tuples of finitely many integers; thus proving that the latter is countable.

-
Hmm, what about tuples with infinite numbers of entries? – David Faux Oct 1 '12 at 0:00
No, if you allow an infinite number of entries, then the total number of tuples is not countable. To prove this, you can apply an argument very similar to the diagonalisation argument that proves that $\Bbb R$ is uncountable. – user22805 Oct 1 '12 at 0:08
@David: The statement "the countable union of countable sets is a countable set" used in your answer isn't provable in ZF (it needs in addition the axiom of countable choice or some variant thereof). Is the answer to the original question also affirmative in ZF alone ? – Ralph Oct 1 '12 at 0:18
@Ralph Good point. I guess that means that my answer is incomplete (but still true, in the sense that the set of such tuples is certainly countable). Since at each step of the induction, we can actually choose a suitable surjection from $\Bbb N$ to the set of tuples of length $n$, we end up with a countable union of sets, along with suitable surjections from $\Bbb N$ to such sets; that is, we've already made the "countable choice". So, you're right, my argument contains a gap. I should probably post a fuller and more careful argument. – user22805 Oct 1 '12 at 0:24

I think a big generalization of Cantor's proof that the rationals have the same cardinality as the integers would do it.

For each integer $n$, generate the $n$-tuples of integers with entries at most $n$ in absolute value. Restrict them to be ordered if you want.This can be done since there are at most $(2n+1)^n$ of them.

Keep on doing this. You will eventually get any specified tuple when $n$ is at least the max of the tuple's length and its max absolute value.

-

There is a wide variety of algorithms for enumerating all (finite) ordered tuples of integers.

Here's a fairly simple-to-explain way to enumerate all finite, nonempty tuples of natural numbers:

We can interpret any finite sequence of 0's and 1's that begins with a 1 as a tuple of natural numbers in the following way: each 1 denotes the start of an entry, and the number of 0's following the 1 is the number that goes into that entry. For example,

1 0 0 0 1 0 1 1 0 0 0 1

encodes the tuple $(3, 1, 0, 3, 0)$.

Of course, we can also interpret such sequences as being the binary representation of a natural number. Thus, this gives us a bijection between the positive natural numbers and the set of finite, non-empty ordered tuples of natural numbers.

-

Another method uses prime factorization. The only complications are handling negative entries and the tuples being increasing.

Define $sign(k)$ to be $0$ if $k \ge 0$, and $1$ if $k < 0$. For a tuple $T = (a_i)_{i=1}^n$, set $map(T) = \prod_{i=1}^n p_i^{2|a_i|+sign(a_i)}$.

This is a 1-1 mapping if the tuples are unordered. To make it a 1-1 mapping if the tuples are non-decreasing, use $map(T) = 2^{2|a_1|+sign(a_1)}\prod_{i=2}^n p_i^{a_i-a_{i-1}}$.

If the tuples are strictly increasing, rather than non-decreasing, use $a_i-a_{i-1}-1$ instead of $a_i-a_{i-1}$.

In all these cases, use prime factorization to recover the exponents of the primes and then get the tuple entries.

Making the mapping 1-1 avoids the use of the Cantor–Bernstein–Schroeder theorem.

-