# Countable Cartesian Product

#### 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 A1, A2, . ..$$ has at least two elements.

Last edited:

#### GJA

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
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

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

Thanks for the help.
~Kalyan.

#### Plato

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

#### kalyanram

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: