Countable union of countable sets vs countable product of countable sets

[snakesonawii]

I know that a countable union of countable sets is countable, and that a finite product of countable sets is countable, but even a countably infinite product of countable sets may not be countable.

Let $$X$$ be a countable set. Then $$X^{n}$$ is countable for each $$n \in N$$.

Now it should also be true that $$\bigcup^{\infty}_{n=1} X^{n}$$ is countable. How is this different from $$X^{\omega}$$, which is uncountable?

 

[micromass]

Ah, very good question. Let's take a look at this question with $$X=\mathbb{N}$$. You first mentioned

$$\bigcup{X^n}$$

The elements of these set are all the finite tuples. So examples include (1,2), (3,4,2000),... Of course, if you add zero's to the end, then you obtain an element of $$X^\omega$$. So (1,2) corresponds to (1,2,0,0,0,...) and (3,4,2000) corresponds to (3,4,2000,0,0,0,...).

So it is easily seen that every element of $$\bigcup{X^n}$$ can be represented by an element of $$X^\omega$$. And it is also easy to see that such elements are exactly the elements ending with a trail of 0's. For example: (1,1,1,0,0,0,...) corresponds to (1,1,1)...

But, and here comes the clue: there are much more elements in $$X^\omega$$. For example: (1,1,1,...) does not come from an element of $$\bigcup{X^n}$$. Other examples are (1,2,3,4,...) or (2,7,1,8,2,...). This shows that there are a huge number of elements in $$X^\omega$$! And so $$X^\omega$$ really is different than $$\bigcup{X^n}$$.

Of course, this is not a proof. But it merely gives an indication why the two sets are different...

 

[snakesonawii]

Ah, very good question. Let's take a look at this question with $$X=\mathbb{N}$$. You first mentioned

$$\bigcup{X^n}$$

The elements of these set are all the finite tuples. So examples include (1,2), (3,4,2000),... Of course, if you add zero's to the end, then you obtain an element of $$X^\omega$$. So (1,2) corresponds to (1,2,0,0,0,...) and (3,4,2000) corresponds to (3,4,2000,0,0,0,...).

So it is easily seen that every element of $$\bigcup{X^n}$$ can be represented by an element of $$X^\omega$$. And it is also easy to see that such elements are exactly the elements ending with a trail of 0's. For example: (1,1,1,0,0,0,...) corresponds to (1,1,1)...

But, and here comes the clue: there are much more elements in $$X^\omega$$. For example: (1,1,1,...) does not come from an element of $$\bigcup{X^n}$$. Other examples are (1,2,3,4,...) or (2,7,1,8,2,...). This shows that there are a huge number of elements in $$X^\omega$$! And so $$X^\omega$$ really is different than $$\bigcup{X^n}$$.

Of course, this is not a proof. But it merely gives an indication why the two sets are different...

Yes, after thinking about it I came to the same conclusion. You can't put them in bijective correspondence because if you wanted to map the union onto $$X^\omega$$ you could do so injectively by adding 0s but there's no way to make this mapping surjective.

 

[mathwonk]

i believe the standard cantor argument shows even a countable product of the set {0,1} is uncountable, i.e. the set of all sequences of 0's and 1's.

 

[snakesonawii]

i believe the standard cantor argument shows even a countable product of the set {0,1} is uncountable, i.e. the set of all sequences of 0's and 1's.

Exactly, hence why this was a seeming contradiction.

 

[discrete*]

Exactly, hence why this was a seeming contradiction.

What's the contradiction that you're referring to?

It's already been stated that the needed bijection doesn't exist. I'm not following you're argument...