1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ see math.stackexchange.com/questions/127695/… search for more on MSE $\endgroup$ – Mirko Dec 12 '15 at 16:10
  • 1
    $\begingroup$ 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) $\endgroup$ – Henry Dec 12 '15 at 16:19
  • 3
    $\begingroup$ 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}$ $\endgroup$ – user160738 Dec 12 '15 at 16:20
  • $\begingroup$ @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. $\endgroup$ – mathcounterexamples.net Dec 12 '15 at 17:10
  • $\begingroup$ @mathcounterexamples.net: Thank you, I've removed that. I wrote "product" while thinking of "union". $\endgroup$ – Alex M. Dec 12 '15 at 17:14
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.