Why is the union of countable many countable sets countable, but not the cross product?

Because, can't the cross product be written in the union format, something like:

Let $$A={E_1, E_2, ...} $$ Where each $E$ is a countable set, then isn't $$\prod _{i\in N}E_i=\cup_{j_1\in E_1}...\cup_{j_n\in E_n}...(a_1, a_2, ..., a_n, ...)$$ Which would be countable?

  • 2
    $\begingroup$ Minor nitpick, I think the term you're looking for is the Cartesian product. The cross product is an operation on a pair of vectors. $\endgroup$ – Eevee Trainer Sep 24 '19 at 1:44
  • 3
    $\begingroup$ @EeveeTrainer Sometimes the Cartesian product called the cross product. (see e.g. Mathworld) $\endgroup$ – Jair Taylor Sep 24 '19 at 1:48
  • $\begingroup$ Huh, I wasn't aware. My bad, and thanks for the heads up. $\endgroup$ – Eevee Trainer Sep 24 '19 at 1:49

You might think of the example where each of the sets $E_i$ is the finite set $\{0,1,2,3,4,5,6,7,8,9\}$. Then $\prod E_i$ can be seen as the set of all possible sequences of decimal digits. If you put a decimal point in front, you have the set of all real numbers in $[0,1]$. And hopefully you know Cantor's diagonalization argument which shows that is an uncountable set.

As a very rough explanation of the difference between union and product, union is like adding and product is like multiplying. For instance, if $A,B$ are two disjoint finite sets with 100 elements each, then $A \cup B$ has 200 elements, but $A \times B$ has 10000. You can see how repeated multiplication gives you much bigger numbers much faster than repeated addition - exponential growth is much faster than linear growth. So it isn't surprising that taking products of sets could give you much bigger sets than unions would.

| cite | improve this answer | |
  • $\begingroup$ So is it not the case that the Cartesian product can be constructed out of Unions? $\endgroup$ – Jac Frall Sep 24 '19 at 2:16
  • $\begingroup$ The specific answer I came across that used this is math.stackexchange.com/a/2439186/626797 $\endgroup$ – Jac Frall Sep 24 '19 at 2:20
  • $\begingroup$ @JacFrall: I do not know what you mean when you say "constructed out of". You have to be more precise. $\endgroup$ – Nate Eldredge Sep 24 '19 at 2:24
  • 1
    $\begingroup$ @JacFrall: The argument in that post is only valid when you take the Cartesian product of finitely many countable sets. It breaks down completely when you take the product of infinitely many sets. $\endgroup$ – Nate Eldredge Sep 24 '19 at 2:25
  • $\begingroup$ That is what was not making sense to me. Thank you $\endgroup$ – Jac Frall Sep 24 '19 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.