Countable Cartesian Product

Jun 2008
149
28
Uppsala, Sweden
Let \(\displaystyle A_1, A_2, A_3, . . .\) be countable sets, and let their Cartesian product \(\displaystyle A_1\) x \(\displaystyle A_2\) x \(\displaystyle A_3\) x ..... be defined to be the set of all sequences \(\displaystyle (a_1, a_2, . . .)\) where \(\displaystyle a_k\), is an element of \(\displaystyle A1\). Prove that the Cartesian product is uncountable. Show that the same conclusion holds if each of the sets \(\displaystyle A1, A2, . ..\) has at least two elements.
 
Last edited:

GJA

Jul 2012
109
32
USA
Hi, kalyanram.

Have you ever seen the proof that (0,1) (the open interval in R) is uncountable? I think you could do something like that here and get the result you want.
 

Plato

MHF Helper
Aug 2006
22,507
8,664
Let \(\displaystyle A_1, A_2, A_3, . . .\) be countable sets, and let their Cartesian product \(\displaystyle A_1\) x \(\displaystyle A_2\) x \(\displaystyle A_3\) x ..... be defined to be the set of all sequences \(\displaystyle (a_1, a_2, . . .)\) where \(\displaystyle a_k\), is an element of \(\displaystyle A1\). Prove that the Cartesian product is uncountable. Show that the same conclusion holds if each of the sets \(\displaystyle A_1, A_2, . ..\) has at least two elements.
Consider modifying the diagonal argument.

This condition "each of the sets \(\displaystyle A_1, A_2, . ..\) has at least two elements" makes that possible
 
Jun 2008
149
28
Uppsala, Sweden
Ok here goes my argument.

Consider that every \(\displaystyle A_k\) has at least two elements and consider that the \(\displaystyle S\) = \(\displaystyle A_1\)x\(\displaystyle A_2\)x\(\displaystyle A_3\)x....... is countable and has elements say \(\displaystyle s_1, s_2, s_3,\).....
now consider the element \(\displaystyle t=(t_1, t_2, t_3,.....)\) \(\displaystyle \ni\) \(\displaystyle t_i \neq s_i\) in the i-th co-ordinate. By the construction of \(\displaystyle t \neq s_i\) from the very construction of \(\displaystyle t\). Hence \(\displaystyle t\) is an element of the Cartesian product that \(\displaystyle \notin S\) a contradiction.

Thanks for the help.
~Kalyan.
 

Plato

MHF Helper
Aug 2006
22,507
8,664
Ok here goes my argument.
Consider that every \(\displaystyle A_k\) has at least two elements and consider that the \(\displaystyle S\) = \(\displaystyle A_1\)x\(\displaystyle A_2\)x\(\displaystyle A_3\)x....... is countable and has elements say \(\displaystyle s_1, s_2, s_3,\).....
now consider the element \(\displaystyle t=(t_1, t_2, t_3,.....)\) \(\displaystyle \ni\) \(\displaystyle t_i \neq s_i\) in the i-th co-ordinate. By the construction of \(\displaystyle t \neq s_i\) from the very construction of \(\displaystyle t\). Hence \(\displaystyle t\) is an element of the Cartesian product that \(\displaystyle \notin S\) a contradiction.
The idea is correct. But I don't follow your reasons.
For each \(\displaystyle n\), \(\displaystyle s_n=(a_{n,1},a_{n,2},a_{n,3},\cdots)\) where \(\displaystyle a_{n,k}\in A_k\).
Define \(\displaystyle t_n\in A_n\setminus \{a_{n,n}\}\). How do we know that \(\displaystyle t_n\) exists?
Is it possible that for some \(\displaystyle N,~t=(t_1, t_2, t_3,.....)=s_N~?\)
 
Jun 2008
149
28
Uppsala, Sweden
How do we know that \(\displaystyle t_n\) exists?
\(\displaystyle t\) is a real sequence \(\displaystyle (t_1,t_2,t_3,....)\) where each \(\displaystyle t_n \in A_n \setminus \{a_{n,n}\}\) as \(\displaystyle |A_n| \ge 2, \forall n\) each \(\displaystyle t_n\) exists.

Is it possible that for some \(\displaystyle N,~t=(t_1, t_2, t_3,.....)=s_N~?\)
As \(\displaystyle t_n\) depends on the index of enumeration so it is not possible that \(\displaystyle t = s_N\) for some \(\displaystyle N\). However lets assume that \(\displaystyle t=(t_1, t_2, t_3,.....)=s_N\) then by definition of \(\displaystyle t\) we have \(\displaystyle t_N \neq a_{N,N} \implies s_N \neq s_N\) a contradiction.

I hope the construction is now more clear.

Kalyan.
 
Last edited: