Union of countable sets is countable

  • Thread starter Bipolarity
  • Start date
  • #1
775
1

Homework Statement


Prove that a finite union of countable sets is also countable. Is an infinite union of countable sets also countable?


Homework Equations


A set S is countable if and only if there exists an injection from S to N.


The Attempt at a Solution


I will attempt prove it for the case of 2 sets. Proving it for a finite collection of sets follows analogously. Suppose the countable sets are A and B. Then there are injections [itex] f_{A} [/itex] and [itex] f_{B} [/itex] from A to N and B to N respectively. We need to show the existence of an injection from {A+B} to N where + denotes union.

Since {A+B} is the union of A and B, certainly it contains an element that is in at least A or in B (or in both A and B). Then each element of {A+B} has an injective mapping to N, since each element of {A+B} is in A or in B.

Does this complete the proof? Is this rigorous?

And what about the case for an infinite union?

BiP
 
Last edited:

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,832
251
Hi BiP! :smile:
Then each element of {A+B} has an injective mapping to N, since each element of {A+B} is in A or in B.
Sorry, but that doesn't make any sense :redface:

Why don't you try to construct a mapping? :wink:
 
  • #3
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,239
5,822
You need a mapping that avoids mapping an element of A-B and an element of B-A to the same element in N.
 

Related Threads on Union of countable sets is countable

Replies
6
Views
5K
Replies
3
Views
2K
Replies
8
Views
11K
Replies
1
Views
3K
Replies
1
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
1K
Top