1

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.

An old man in the sea.
  • 5,241
  • see http://math.stackexchange.com/questions/127695/proving-that-a-set-is-countable-by-finding-a-bijection/127792#127792 search for more on MSE – Mirko Dec 12 '15 at 16:10
  • 1
    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
  • 3
    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

1 Answers1

1

Hint.

The answer is positive.

$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})$$

mathcounterexamples.net
  • 70,018