Results 1 to 6 of 6

Math Help - Prove a countable Cartesian product of countable sets is uncountable

  1. #1
    Member Last_Singularity's Avatar
    Joined
    Dec 2008
    Posts
    157

    Prove a countable Cartesian product of countable sets is uncountable

    Hey guys, could you please check over my solution and let me know if I made a mistake somewhere?

    Problem: Let A_1, A_2, A_3, ... be countable sets. Then show that the Cartesian product A = A_1 \times A_2 \times A_3 \times ... is uncountable. In other words, show that the set of countably infinite sets whose elements are natural numbers is uncountably large.

    Approach: I know that this is solvable using a diagonalization argument. But I wanted to try something else. I attempted to surject this to real numbers.

    Consider a subset of A, say B where B holds all such elements \{a_1, a_2, a_3, ...\} of A where a_2,a_3,a_4,... \leq 9.

    So I defined a function f: B \rightarrow \mathbb{R} where:

    For any element of B, f sends that set to \sum_{n \in \mathbb{N}} \frac{1}{10}^{n-1} a_n = a_1 + \frac{a_2}{10} + \frac{a_3}{100} + ... a_1.a_2 a_3... \in \mathbb{R}

    This function is surjective because for all real numbers x \in \mathbb{R} whose digits are: a_1. a_2 a_3 ..., we can find an element \{a_1, a_2, a_3, ...\} \in B

    The existence of this surjection implies that card(B) \geq card(\mathbb{R}). And we also know that B \subseteq A, so that card(A) \geq card(B). By transitivity, card(A) \geq card(B) \geq card(\mathbb{R}) which means that A must be uncountable.
    Last edited by Last_Singularity; January 15th 2009 at 05:31 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member vincisonfire's Avatar
    Joined
    Oct 2008
    From
    Sainte-Flavie
    Posts
    469
    Thanks
    2
    Awards
    1
    This makes sense to me but I'm not better than you are I think so I would wait for someone else to tell you that this is correct.
    (I take part of this thread so I get an email when someone answers because it's an interesting question)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by Last_Singularity View Post
    \sum_{n \in \mathbb{N}} \frac{1}{10}^{n-1} a_n
    The above one looks rational numbers, which are countable.
    Plz correct me if I am wrong.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    For any element of B, f sends that set to \sum_{n \in \mathbb{N}} \frac{1}{10}^{n-1} a_n = a_1 + \frac{a_2}{10} + \frac{a_3}{100} + ... a_1.a_2 a_3... \in \mathbb{R}
    Write \frac{1}{10^{n-1}}, this will give the correct writing.

    The above one looks rational numbers, which are countable.
    Plz correct me if I am wrong.
    It is true that rational numbers make a countable set. However, not all number having an infinity of decimals are rational.
    Irrrationals also have a decimal expansion, though it never ends and never repeats.

    So I guess what Last_Singularity did is correct... like vincisonfire, don't take my word for granted ><
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Jason Bourne's Avatar
    Joined
    Nov 2007
    Posts
    132
    Looks all good to me although you know much better than I do. What would we do without infinite cardinality!
    Last edited by Jason Bourne; January 18th 2009 at 01:29 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2013
    From
    North Pole
    Posts
    1

    Re: Prove a countable Cartesian product of countable sets is uncountable

    Apologies for the necro, but I found this post in a Google search on the first page of results, so I figured I should address some issues of the OP.

    Quote Originally Posted by Last_Singularity View Post
    Consider a subset of A, say B where B holds all such elements \{a_1, a_2, a_3, ...\} of A where a_2,a_3,a_4,... \leq 9.
    Small nitpick: an element of A isn't a set, so don't use set notation - use parentheses to indicate that it is a tuple or sequence.
    Larger nitpick: it was never mentioned that the various countable sets A_n were subsets of the integers. Countable sets needn't necessarily be comprised of natural numbers. You need to do some legwork to get to a usable set of numbers: let us define S_n as the "substitute" set, and wherever A_n and a_n appears in the proof, substitute it instead by S_n and s_n. Given that each A_n is countable, there is a bijection from a subset of the natural numbers. If this subset is not infinite, then it has cardinality c_n - in this case, let S_n be the set of natural numbers strictly less than c_n. Otherwise, let S_n = \mathbb{N}.

    For any element of B, f sends that set
    Again, elements of A (and thus B) are not sets, they are sequences or tuples. If it were a set, it would have a cardinality of at most 11, given how you chose B.

    This function is surjective because for all real numbers x \in \mathbb{R} whose digits are: a_1. a_2 a_3 ..., we can find an element \{a_1, a_2, a_3, ...\} \in B
    No it isn't. To be surjective, you require further assumptions. As a counter example, let each A_n be the countable set \{0, 1\}. The infinite countable product \{0, 1\}^\mathbb{N} is uncountable, but your "proof" does not show this. Your proof actually gives a weaker result.

    To complete you proof, you need the following assumptions. From the collection of countable sets A_n, there must be at least infinitely many sets with at least 10 elements - this lets us have infinitely many digits from 0 to 9. We would then "discard" any of the sets which do not have at least 10 elements - we can get them back later by taking the cartesian product of the resultant uncountably infinite set with the discarded sets. Unless any of these discarded sets is the empty set (yet another assumption which isn't mentioned), the product would also be uncountably infinite. Additionally, there must be at least one set with infinitely many elements - this would correspond to your A_1 in the above proof. Finally, obviously, you must assume that \mathbb{R} is uncountably infinite. This final assumption is a pretty big sticking point - how would you go about showing that \mathbb{R} is uncountable? If you manage it without some variant of the diagonalization argument, then that would be quite interesting, but I haven't yet seen a proof that isn't just diagonalization with different words. So your proof boils down to a weaker result that inevitably stems from diagonalization anyway.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. countable & uncountable sets
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 7th 2010, 07:43 PM
  2. Countable and Uncountable sets
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: October 21st 2010, 11:58 AM
  3. countable and uncountable sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2009, 12:40 PM
  4. Replies: 11
    Last Post: October 11th 2008, 06:49 PM
  5. Replies: 4
    Last Post: October 11th 2008, 01:42 PM

Search Tags


/mathhelpforum @mathhelpforum