Results 1 to 6 of 6

Thread: Countable Cartesian Product

  1. #1
    Member kalyanram's Avatar
    Joined
    Jun 2008
    From
    Uppsala, Sweden
    Posts
    149
    Thanks
    14

    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.
    Last edited by kalyanram; Sep 2nd 2012 at 08:46 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    GJA
    GJA is offline
    Member
    Joined
    Jul 2012
    From
    USA
    Posts
    109
    Thanks
    29

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,742
    Thanks
    2814
    Awards
    1

    Re: Countable Cartesian Product

    Quote Originally Posted by kalyanram View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member kalyanram's Avatar
    Joined
    Jun 2008
    From
    Uppsala, Sweden
    Posts
    149
    Thanks
    14

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,742
    Thanks
    2814
    Awards
    1

    Re: Countable Cartesian Product

    Quote Originally Posted by kalyanram View Post
    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~?$
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member kalyanram's Avatar
    Joined
    Jun 2008
    From
    Uppsala, Sweden
    Posts
    149
    Thanks
    14

    Re: Countable Cartesian Product

    Quote Originally Posted by Plato View Post
    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 View Post
    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 by kalyanram; Sep 2nd 2012 at 09:57 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Jan 9th 2013, 06:14 AM
  2. Cartesian product
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Aug 19th 2011, 11:38 AM
  3. Cartesian product, countable?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Feb 28th 2010, 03:16 PM
  4. Cartesian Product
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 9th 2010, 11:31 AM
  5. Replies: 11
    Last Post: Oct 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum