Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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