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 be countable sets. Then show that the Cartesian product 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 , say where holds all such elements of A where .
So I defined a function where:
For any element of B, sends that set to
This function is surjective because for all real numbers whose digits are: , we can find an element
The existence of this surjection implies that . And we also know that , so that . By transitivity, which means that must be uncountable.
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.
Small nitpick: an element of isn't a set, so don't use set notation - use parentheses to indicate that it is a tuple or sequence.
Originally Posted by Last_Singularity
Larger nitpick: it was never mentioned that the various countable sets 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 as the "substitute" set, and wherever and appears in the proof, substitute it instead by and . Given that each is countable, there is a bijection from a subset of the natural numbers. If this subset is not infinite, then it has cardinality - in this case, let be the set of natural numbers strictly less than . Otherwise, let .
Again, elements of (and thus ) 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 .
For any element of B,
sends that set
No it isn't. To be surjective, you require further assumptions. As a counter example, let each be the countable set . The infinite countable product is uncountable, but your "proof" does not show this. Your proof actually gives a weaker result.
This function is surjective because for all real numbers
whose digits are:
, we can find an element
To complete you proof, you need the following assumptions. From the collection of countable sets , 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 in the above proof. Finally, obviously, you must assume that is uncountably infinite. This final assumption is a pretty big sticking point - how would you go about showing that 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.