Countable Cartesian Product

**kalyanram** · September 2nd 2012, 07:31 AM

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.

**GJA** · September 2nd 2012, 08:11 AM

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** · September 2nd 2012, 08:16 AM

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

**kalyanram** · September 2nd 2012, 08:35 AM

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.

**Plato** · September 2nd 2012, 09:04 AM

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.

The idea is correct. But I don't follow your reasons.
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~?$

**kalyanram** · September 2nd 2012, 09:49 AM

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.

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.

Thread: Countable Cartesian Product

LinkBack

Thread Tools

Display

Countable Cartesian Product

Re: Countable Cartesian Product

Re: Countable Cartesian Product

Re: Countable Cartesian Product

Re: Countable Cartesian Product

Re: Countable Cartesian Product

Similar Math Help Forum Discussions

Prove a countable Cartesian product of countable sets is uncountable

Cartesian product

Cartesian product, countable?

Cartesian Product

[SOLVED] I need help proving that the cross product of 2 countable sets is countable.

Search Tags