Countably infinite sets

Hi,

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

Thanks!
 
56
1
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.
 
Another way to think about the problem...

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

[tex]\alpha[/tex]: N [tex]\rightarrow[/tex] A and [tex]\varphi[/tex]: N [tex]\rightarrow[/tex] B.

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

[tex]\zeta[/tex] is a bijection since [tex]\alpha[/tex] and [tex]\varphi[/tex] are bijections and therefore A X B is countable.
 
73
1
CharmedQuark, what you said isn't exactly correct, since your constructed function from N to AxB won't be surjective.
 

HallsofIvy

Science Advisor
41,626
821
Good point, in fact, it is very badly non surjective!

For example, if [itex]\alpha(2)= p[/itex] and [itex]\beta(2)= q[/itex], then [itex]\zeta(2)= (p, q)[/itex] but there is NO other [itex]\zeta(n)[/itex] giving a pair having p as its first member nor is there any other n so that [itex]\zeta(n)[/itex] is pair having q as its second member.
 
Good point, in fact, it is very badly non surjective!

For example, if [itex]\alpha(2)= p[/itex] and [itex]\beta(2)= q[/itex], then [itex]\zeta(2)= (p, q)[/itex] but there is NO other [itex]\zeta(n)[/itex] giving a pair having p as its first member nor is there any other n so that [itex]\zeta(n)[/itex] 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 [tex]\rightarrow[/tex] A X B. Other than that little error the principle is the same. [tex]\zeta[/tex]( n[tex]_{1}[/tex] , n[tex]_{2}[/tex] ) = ( [tex]\alpha[/tex]( n[tex]_{1}[/tex] ) , [tex]\varphi[/tex]( n[tex]_{2}[/tex] ) ). This function is a bijection and N X N is countable so any cartesian product of two countably infinite sets is countable.
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top