Countable union of countable sets vs countable product of countable sets

  • #1
snakesonawii
5
0
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 [tex]X[/tex] be a countable set. Then [tex]X^{n}[/tex] is countable for each [tex]n \in N[/tex].

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

Answers and Replies

  • #2
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,302
Ah, very good question. Let's take a look at this question with [tex]X=\mathbb{N}[/tex]. You first mentioned

[tex]\bigcup{X^n}[/tex]

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 [tex]X^\omega[/tex]. 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 [tex]\bigcup{X^n}[/tex] can be represented by an element of [tex]X^\omega[/tex]. 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 [tex]X^\omega[/tex]. For example: (1,1,1,...) does not come from an element of [tex]\bigcup{X^n}[/tex]. Other examples are (1,2,3,4,...) or (2,7,1,8,2,...). This shows that there are a huge number of elements in [tex]X^\omega[/tex]!! And so [tex]X^\omega[/tex] really is different than [tex]\bigcup{X^n}[/tex].

Of course, this is not a proof. But it merely gives an indication why the two sets are different...
 
  • #3
snakesonawii
5
0
Ah, very good question. Let's take a look at this question with [tex]X=\mathbb{N}[/tex]. You first mentioned

[tex]\bigcup{X^n}[/tex]

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 [tex]X^\omega[/tex]. 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 [tex]\bigcup{X^n}[/tex] can be represented by an element of [tex]X^\omega[/tex]. 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 [tex]X^\omega[/tex]. For example: (1,1,1,...) does not come from an element of [tex]\bigcup{X^n}[/tex]. Other examples are (1,2,3,4,...) or (2,7,1,8,2,...). This shows that there are a huge number of elements in [tex]X^\omega[/tex]!! And so [tex]X^\omega[/tex] really is different than [tex]\bigcup{X^n}[/tex].

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 [tex]X^\omega[/tex] you could do so injectively by adding 0s but there's no way to make this mapping surjective.
 
  • #4
mathwonk
Science Advisor
Homework Helper
11,348
1,581
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.
 
  • #5
snakesonawii
5
0
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.
 
  • #6
discrete*
79
0
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...
 

Suggested for: Countable union of countable sets vs countable product of countable sets

Replies
1
Views
2K
Replies
10
Views
996
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
12
Views
4K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
7
Views
9K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
22
Views
1K
Replies
1
Views
2K
Top