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...