If I have two sets say A and B which are countable and infinite then how would I show that the Cartesian product is countable.


closed as off-topic by Xander Henderson, Leucippus, JMP, choco_addicted, Claude Leibovici Mar 23 '18 at 9:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Leucippus, JMP, choco_addicted, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Do you have any thoughts? $\endgroup$ – StubbornAtom Nov 11 '16 at 13:37
  • $\begingroup$ Have you seen proof that $\mathbb N\times\mathbb N$ is countable? $\endgroup$ – Henning Makholm Nov 11 '16 at 13:39
  • $\begingroup$ The easiest way to show something is countable is to create a bijection between the two sets. $\endgroup$ – Q the Platypus Nov 11 '16 at 13:41
  • $\begingroup$ How would I create this bijection. Would I need to show its both surjective and injective. $\endgroup$ – Thomas Nov 11 '16 at 13:44
  • $\begingroup$ You could have a look at the related questions on the right. Like this one: math.stackexchange.com/questions/71850/…. $\endgroup$ – StubbornAtom Nov 11 '16 at 13:50

The set of natural numbers is the prototype for countable sets; anything in bijective correspondence with this set, by definition, is a countable set.

Let us see the natural numbers in their physical/visual form. We write them out in base 10. Then we get all possible finite sequences formed by the symbols $0,1,2,\ldots,9$ (avoiding 0 at the starting position).

As numbers can be written uniquely in any basis (binary system, decimal system) it follows that given a finite set of symbols, the collection of strings of all possible finite length composed of these symbols is a countable set.

Now let us take a visual description of the cartesian product: a typical element looks like $(13374,26905)$. We can see that physically these are subset of all possible strings of finite length composed of the thirteen symbols: the decimal digits, opening and closing parentheses, the comma.

So this is a subset of the countable set of all strings of finite length formed with 13 symbols, hence countable.

Note that this actually proves that product of three (or any finite number of) countable sets is also countable.

BONUS: To prove countability of rationals look at their physical forms, other than the minus sign, the slash sign for division should be enlisted, and same argument will work.


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