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.