Exploring the Countable Infinity of Disjoint Sets and their Cartesian Product

[zeebo17]

Hi,

I was wondering if two sets are disjoint countably infinite sets why is their Cartesian product also countably infinite?

Thanks!

 

[farful]

You can order your two sets a_1,a_2,a_3,... and b_1,b_2,b_3 mapping them onto the set of natural numbers.

Then, you can form a triangular mapping recursively (like you do to prove that the set of rational numbers is countably infinite)... so:
(a_1,b_1) maps to 1,
(a_1,b_2) maps to 2,
(a_2,b_1) maps to 3,
(a_1,b_3) maps to 4,
(a_2,b_2) maps to 5, etc. etc.

 

[CharmedQuark]

Another way to think about the problem...

Since we have two countably infinite sets call them A , B we can define two bijections:

\alpha: N \rightarrow A and \varphi: N \rightarrow B.

We can then define another function \zeta: N \rightarrow A X B as \zeta(n) = ( \alpha(n) , \varphi(n) ).

\zeta is a bijection since \alpha and \varphi are bijections and therefore A X B is countable.

 

[grief]

CharmedQuark, what you said isn't exactly correct, since your constructed function from N to AxB won't be surjective.

 

[HallsofIvy]

Good point, in fact, it is very badly non surjective!

For example, if \alpha(2)= p and \beta(2)= q, then \zeta(2)= (p, q) but there is NO other \zeta(n) giving a pair having p as its first member nor is there any other n so that \zeta(n) is pair having q as its second member.

 

[CharmedQuark]

Good point, in fact, it is very badly non surjective!

For example, if \alpha(2)= p and \beta(2)= q, then \zeta(2)= (p, q) but there is NO other \zeta(n) giving a pair having p as its first member nor is there any other n so that \zeta(n) is pair having q as its second member.

Yeah I wrote it last night and wasn't paying attention to what I was writing. The function should instead be a function from N X N \rightarrow A X B. Other than that little error the principle is the same. \zeta( n_{1} , n_{2} ) = ( \alpha( n_{1} ) , \varphi( n_{2} ) ). This function is a bijection and N X N is countable so any cartesian product of two countably infinite sets is countable.