# Countable Cartesian Product

• September 2nd 2012, 07:31 AM
kalyanram
Countable Cartesian Product
Let $A_1, A_2, A_3, . . .$ be countable sets, and let their Cartesian product $A_1$ x $A_2$ x $A_3$ x ..... be defined to be the set of all sequences $(a_1, a_2, . . .)$ where $a_k$, is an element of $A1$. Prove that the Cartesian product is uncountable. Show that the same conclusion holds if each of the sets $A1, A2, . ..$ has at least two elements.
• September 2nd 2012, 08:11 AM
GJA
Re: Countable Cartesian Product
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.
• September 2nd 2012, 08:16 AM
Plato
Re: Countable Cartesian Product
Quote:

Originally Posted by kalyanram
Let $A_1, A_2, A_3, . . .$ be countable sets, and let their Cartesian product $A_1$ x $A_2$ x $A_3$ x ..... be defined to be the set of all sequences $(a_1, a_2, . . .)$ where $a_k$, is an element of $A1$. Prove that the Cartesian product is uncountable. Show that the same conclusion holds if each of the sets $A_1, A_2, . ..$ has at least two elements.

Consider modifying the diagonal argument.

This condition "each of the sets $A_1, A_2, . ..$ has at least two elements" makes that possible
• September 2nd 2012, 08:35 AM
kalyanram
Re: Countable Cartesian Product
Ok here goes my argument.

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

Thanks for the help.
~Kalyan.
• September 2nd 2012, 09:04 AM
Plato
Re: Countable Cartesian Product
Quote:

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

For each $n$, $s_n=(a_{n,1},a_{n,2},a_{n,3},\cdots)$ where $a_{n,k}\in A_k$.
Define $t_n\in A_n\setminus \{a_{n,n}\}$. How do we know that $t_n$ exists?
Is it possible that for some $N,~t=(t_1, t_2, t_3,.....)=s_N~?$
• September 2nd 2012, 09:49 AM
kalyanram
Re: Countable Cartesian Product
Quote:

Originally Posted by Plato
How do we know that $t_n$ exists?

$t$ is a real sequence $(t_1,t_2,t_3,....)$ where each $t_n \in A_n \setminus \{a_{n,n}\}$ as $|A_n| \ge 2, \forall n$ each $t_n$ exists.

Quote:

Originally Posted by Plato
Is it possible that for some $N,~t=(t_1, t_2, t_3,.....)=s_N~?$

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

I hope the construction is now more clear.

Kalyan.