Take the 2-minute tour ×

Well, I've been studying Rudin's Principles of Mathematical Analysis and then I've thought on the following exercise: Let $A, B$ be two countable sets, then $A\times B$ is countable. My idea to prove this was to arrange the elements of $A\times B$ in a sequence. Inded, I've used that argument of constructing the array:

$$\begin{matrix} (a_1,b_1) & (a_1,b_2) & (a_1,b_3) & (a_1,b_4) & \cdots \\ (a_2,b_1) & (a_2,b_2) & (a_2,b_3) & \cdots & \cdots \\ (a_3,b_1) & (a_3,b_2) & \cdots & \cdots & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots\\ \end{matrix}$$

And then arrange the sequence $(a_1,b_1), (a_1,b_2), (a_2,b_1), (a_3,b_1), (a_2,b_2), (a_1,b_3)\dots$ with this I would be defining a sequence of distinct elements, in other words a bijection $f: \Bbb N \to A\times B$ showing that $A\times B$ is countable. I've then shown this to someone I know that studies set theory and he said that this proof wasn't good, it was needed to show explicitly the function $f$. Is this really necessary? Because the argument show that this must be a bijection: since $A$ is countable it's elements can be put into a sequence $(a_i)$ and the same for the elements of $B$ which would give a sequence $(b_i)$. Both sequences are of distinct terms. Now, on this arrangement, we have elements $(a_i, b_j)$, so all the pairs are distinct because the sequences $(a_i)$ and $(b_j)$ are of distinct elements.

Is it necessary to find $f$? If that's the case, how could I find it? I didn't notice any obvious pattern into the sequence I've made.

share|improve this question
I believe it's necessary to state f explicitly to write something a bit close to a formal proof –  Amr Jun 22 '13 at 23:25

2 Answers 2

up vote 3 down vote accepted

It's a slightly delicate point.

You don't need to explicitly write a formula for $f$, but you need to define it from the fact that $A$ and $B$ are countable. That is to say, you need to fix two bijections $f_A, f_B$ and then use them to write the formula for $f$ itself.

Essentially this means writing a formula for a bijection $F\colon\Bbb{N\to N\times N}$, and use that with $f_A$ and $f_B$ to write a function $f$ as wanted.

share|improve this answer

You don't need a bijection. I don't have a copy of that book handy, but I bet you're already had the proposition "a subset of a countable set is countable". So all you need in an injection from $A\times B$ to $\mathbb N$; that will then be a bijection from $A\times B$ to some subset of $\mathbb N$, which is good enough to show that $A\times B$ is countable. For your injection, you can map $(a_i,b_j)$ to $2^i3^j$, or to $2^{i-1}(2j-1)$, etc. etc.

share|improve this answer

Your Answer


