Question: Is the cartesian product of a countably infinite collection of countably infinite sets countable infinite ? and how to prove this?

Hi Geetha,

The cartesian product of a countably infinite collection of countably infinite sets is uncountable. Let N to be the set of positive integers and consider the cartesian product of countably many copies of N. This is the set S of sequences of positive integers. I am going to show that S is uncountable using a proof by contradiction. I am going to assume that S is countable and hence can be put into a one-to-one correspondence with N and then use this fact to produce an member of S that is outside this correspondence. So here is my proof.

Suppose that S is countable then S can be written

S = {s₁, s₂, s₃,··· }

that is there is a one-to-one correspondence between S and N = {1, 2, 3, ··· }.

At this point the notation get a little cumbersome. Each s_n is a sequence of positive integers and hence I am going to write

s_n = {x_n,1, x_n,2, x_n,3, ··· }

Thus for each x the first subscript tells you which sequence it is in and the second subscript tells you which element of the sequence it is.

Now I am going to construct a sequence t of positive integers that is not any of the terms s_n in S and hence have my contradiction.

If x_1,1 = 5 then t₁ = 0 and if x_1,1 ≠ 5 then t₁ = x_1,1

If x_2,2 = 5 then t₂ = 0 and if x_2,2 ≠ 5 then t₂ = x_2,2 , etc.

In general

If x_k,k = 5 then t_k = 0 and if x_k,k ≠ 5 then t_k = x_k,k

t is a sequence of positive integers and for each positive integer n, t ≠ s_n since t_n ≠ s_n,n

Thus S is not countable.

Penny