Results 1 to 6 of 6

Math Help - Countable Cartesian Product

  1. #1
    Member kalyanram's Avatar
    Joined
    Jun 2008
    From
    Bangalore, India
    Posts
    142
    Thanks
    14

    Countable Cartesian Product

    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.
    Last edited by kalyanram; September 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
    18,605
    Thanks
    1574
    Awards
    1

    Re: Countable Cartesian Product

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

  4. #4
    Member kalyanram's Avatar
    Joined
    Jun 2008
    From
    Bangalore, India
    Posts
    142
    Thanks
    14

    Re: Countable Cartesian Product

    Ok here goes my argument.

    Consider that every A_k has at least two elements and consider that the S = A_1x A_2x A_3x....... 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Countable Cartesian Product

    Quote Originally Posted by kalyanram View Post
    Ok here goes my argument.
    Consider that every A_k has at least two elements and consider that the S = A_1x A_2x A_3x....... 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~?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member kalyanram's Avatar
    Joined
    Jun 2008
    From
    Bangalore, India
    Posts
    142
    Thanks
    14

    Re: Countable Cartesian Product

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

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

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum