Union of countable sets is countable

  • Thread starter Bipolarity
  • Start date
  • Tags
    Sets Union
In summary: This can be done by mapping each element in A-B to a different element in N and each element in B-A to a different element in N. This can be done because each set is countable, so there are enough elements in N to map to. This mapping is injective because each element in {A+B} is mapped to a unique element in N. Therefore, the union of two countable sets is countable.In summary, the proof for the finite union of countable sets being countable is done by constructing an injective mapping from the union of the two sets to N. This can be done by mapping each element in one set to a different element in N and each element in the other set to a different element in
  • #1
Bipolarity
776
2

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:
Physics news on Phys.org
  • #2
Hi BiP! :smile:
Bipolarity said:
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
You need a mapping that avoids mapping an element of A-B and an element of B-A to the same element in N.
 

What is the definition of a countable set?

A countable set is a set that can be put in a one-to-one correspondence with the set of natural numbers (1, 2, 3, ...), meaning that each element in the set can be assigned a unique natural number.

What does it mean for a set to be countably infinite?

A set is countably infinite if it is a countable set with an infinite number of elements. This means that the set can be put in a one-to-one correspondence with the set of natural numbers, but the set itself has an infinite number of elements.

How do you prove that the union of two countable sets is countable?

To prove that the union of two countable sets is countable, we must show that the union can be put in a one-to-one correspondence with the set of natural numbers. This can be done by creating a new list that includes all the elements from both sets in a specific order, such as alternating between elements from each set. This list can then be paired with the natural numbers, proving that the union is countable.

Is the union of countably infinite sets always countably infinite?

No, the union of countably infinite sets is not always countably infinite. It is possible for the union of two countably infinite sets to be finite, such as if the two sets have overlapping elements.

Can the union of uncountable sets be countable?

No, the union of uncountable sets cannot be countable. This is because an uncountable set has an infinite number of elements that cannot be put in a one-to-one correspondence with the set of natural numbers. Therefore, the union of uncountable sets will also have an infinite number of elements and cannot be countable.

Similar threads

Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
509
Munkres Topology ch1 ex #9 - Generalized DeMorgan's Laws
    • Calculus and Beyond Homework Help
Replies
2
Views
947
Proof that algebraic numbers are countable
    • Calculus and Beyond Homework Help
Replies
6
Views
2K
A proof that a union of compact spaces is compact
    • Calculus and Beyond Homework Help
Replies
12
Views
1K
Countable union of Jordan sets is not always Jordan measurable
    • Calculus and Beyond Homework Help
Replies
1
Views
3K
Proving that the natural numbers are countable, stuck.
    • Calculus and Beyond Homework Help
Replies
8
Views
2K
Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
    • Calculus and Beyond Homework Help
Replies
4
Views
504
I Collection of finite unions of half-open intervals form an algebra
    • Topology and Analysis
Replies
3
Views
206
Proving that the algebraic numbers are denumerable
    • Calculus and Beyond Homework Help
Replies
3
Views
1K
Is (-infinity, b) an event for any real number b?
    • Calculus and Beyond Homework Help
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top