Results 1 to 5 of 5

Math Help - Cartesian product, countable?

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Cartesian product, countable?

    Hi,
    if I let A and B be countable sets, how can I prove that the Cartesian product A x B is countable?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    Hi,
    if I let A and B be countable sets, how can I prove that the Cartesian product A x B is countable?
    Suppose that A=\{a_1,a_2,a_3,\cdots\}~\&~B=\{b_1,b_2,b_3,\cdots  \}.

    Then if (a_n,b_m)\in A\times B define \Theta[(a_n,b_m)]=2^n\cdot 3^m.

    Prove that \Theta is an injection.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by Plato View Post
    Suppose that A=\{a_1,a_2,a_3,\cdots\}~\&~B=\{b_1,b_2,b_3,\cdots  \}.

    Then if (a_n,b_m)\in A\times B define \Theta[(a_n,b_m)]=2^n\cdot 3^m.

    Prove that \Theta is an injection.
    Thanks! But how did you deduce that \Theta should be \Theta[(a_n,b_m)]=2^n\cdot 3^m?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by posix_memalign View Post
    Hi,
    if I let A and B be countable sets, how can I prove that the Cartesian product A x B is countable?
    Basically the idea in Plaot's post is that you can prove that \mathbb{N}^m is countable, because clearly the mapping f:\mathbb{N}\mapsto\mathbb{N}^m given by n\mapsto(n\underbrace{1,\cdots,1}_{m-1\text{ times}}) is an injection and so is g:\mathbb{N}^m\mapsto \mathbb{N} given by \left(n_1,\cdots,n_m\right)\mapsto p_1^{n_1}\cdots p_m^{n_m} where p_k is the kth prime. It follows by the Schroder- Bernstein theorem that the two sets are equipotent. But, if E_1,\cdots,E_m is countable we know that for each there is a mapping f_k:E_k\mapsto\mathbb{N} which is bijective. So, define a mapping \prod_{j=1}^{m}f_j:\prod_{j=1}^{m}E_j\mapsto\mathb  b{N}^m by (e_1,\cdots,e_m)\mapsto\left(f_1(e_1),\cdots,f_m(e  _m)\right).This is readily verified to be a bijection, and since \mathbb{N} is countable it follows that \prod_{j=1}^{m}E_j is countable.


    Note: this is only true for finite cases. For example consider \{0,1\}^{\aleph_0}. This is uncountable, for if we could list it's elements in the fashion \bold{x}_1,\bold{x}_2,\cdots then we can construct a tuple \bold{x} where \pi_j(\bold{x})=\begin{cases} 1 & \mbox{if} \quad \pi_j(\bold{x}_j)=0 \\ 0 & \mbox{if} \quad \pi_j(\bold{x}_j)=1\end{cases} and so it follows that \bold{x}\in\{0,1\}^{\aleph_0} but \bold{x}\notin\left\{\bold{x}_n\right\}_{n\in\math  bb{N}}. This clearly shows that we have not, and thus cannot, list all the elements of \{0,1\}^{\aleph_0}. It follows that \{0,1\}^{\aleph_0} is uncountable.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    Thanks! But how did you deduce that \Theta should be \Theta[(a_n,b_m)]=2^n\cdot 3^m?
    Practice, Practice, Practice.
    All we must do is show that there is an injection from A to \mathbb{Z}^+ in order to show that A is countable.
    That mapping just happens to work.
    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 of A*A*A*A
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 14th 2011, 06:29 AM
  3. Cartesian product.
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 4th 2010, 01:59 PM
  4. Cartesian product
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 26th 2010, 11:30 AM
  5. Replies: 11
    Last Post: October 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum