1. ## Countable Cartesian Product

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.

2. ## 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.

3. ## Re: Countable Cartesian Product

Originally Posted by kalyanram
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

4. ## Re: Countable Cartesian Product

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.

5. ## Re: Countable Cartesian Product

Originally Posted by kalyanram
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.
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~?$

6. ## Re: Countable Cartesian Product

Originally Posted by Plato
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.

Originally Posted by Plato
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.