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.

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.

Re: Countable Cartesian Product

Quote:

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

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.

Re: Countable Cartesian Product

Quote:

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.

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~?$

Re: Countable Cartesian Product

Quote:

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.

Quote:

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.