Countable union of countable sets vs countable product of countable sets

  • #1

Main Question or Discussion Point

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
22,097
3,280
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
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
10,908
1,069
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
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
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...
 

Related Threads on Countable union of countable sets vs countable product of countable sets

Replies
1
Views
2K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
12
Views
4K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
7
Views
8K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
5
Views
3K
Replies
11
Views
9K
Top