# Finite Cartesian Product of Countable sets is countable?

Is the finite Cartesian Product of Countable sets countable?

If possible, could you give a bijection that would work for any example?

Any help would be appreciated.

• see math.stackexchange.com/questions/127695/… search for more on MSE – Mirko Dec 12 '15 at 16:10
• Index each set with the natural numbers. Separate the elements of the product into equivalence classes based on the sum of the relevant indices; each class will be finite. Go through the classes starting with the smallest sum, and order within each class (for example by first index, second index etc.) . That provides an order for the elements of the product, and thus a bijection from the product to the natural numbers (though the inverse is a little complicated to write down) – Henry Dec 12 '15 at 16:19
• If $X_1,\cdots,X_n$ are countable sets, then we can enumerate elements $x_1^i,x_2^i,\dots$ of $X_i$. $(x_{a_1}^1,\cdots,x_{a_n}^n) \rightarrow 2^{a_1} 3^{a_2}\cdots p_n^{a_n}$, where $p_n$ is $n^{\text{th}}$ prime, gives an injection from $X_1\times \cdots \times X_n$ into $\mathbb{N}$ – user160738 Dec 12 '15 at 16:20
• @AlexM. This is wrong. $\mathbb N^{\mathbb N}$ has a cardinal equal to the one of $2^{\mathbb N}$ which has the cardinality of the continuum. – mathcounterexamples.net Dec 12 '15 at 17:10
• @mathcounterexamples.net: Thank you, I've removed that. I wrote "product" while thinking of "union". – Alex M. Dec 12 '15 at 17:14

$f_2$ defined from $\mathbb N \times \mathbb N$ to $\mathbb N$ by $$f_2(p,q)= 2^{p-1}(2q-1)$$ is a bijection.
The case of $n$ countable sets can then be considered by induction. For example for $n=3$ you can define $$f_3(p,q,r)=f_2(f_2(p,q),r)$$ which is a bijection from $\mathbb N^3$ to $\mathbb N$.
More generally $$f_{n+1}(p_1, \dots ,p_{n+1})= f_2(f_{n}(p_1, \dots ,p_{n}),p_{n+1})$$