Prove Disjoint Union of Countable Sets is Countable

In summary, the conversation discusses the proof of the countability of a disjoint union of countable sets. The approach is similar to proving the countability of the rational numbers, using bijections and an infinite square array.
  • #1
the_kid
116
0

Homework Statement


A[itex]_{1}[/itex], A[itex]_{2}[/itex], A[itex]_{3}[/itex],... are countable sets indexed by positive integers. I'm looking to prove that the disjoint union of these sets is countable.


Homework Equations





The Attempt at a Solution


I can't figure out how to enter the form of the disjoint union in this interface, but I'm using the one listed on Wikipedia (http://en.wikipedia.org/wiki/Disjoint_union). So, I understand that when looking to prove that a single set, S, is countable, one must show that there exists a bijection from the N-->S. However, I'm confused about how I'd show this for the disjoint union. It seems to me that this bijection is almost implicit in the definition of the disjoint union. I.e. the disjoint union indexes each element according to which set it came from. I'm looking for some help getting started with this.
 
Physics news on Phys.org
  • #2
Did you prove that the rational numbers are countable? It's essentially the same proof with some changes of notation.
 
  • #3
the_kid said:

Homework Statement


A[itex]_{1}[/itex], A[itex]_{2}[/itex], A[itex]_{3}[/itex],... are countable sets indexed by positive integers. I'm looking to prove that the disjoint union of these sets is countable.

The Attempt at a Solution


I can't figure out how to enter the form of the disjoint union in this interface, but I'm using the one listed on Wikipedia (http://en.wikipedia.org/wiki/Disjoint_union). So, I understand that when looking to prove that a single set, S, is countable, one must show that there exists a bijection from the N-->S. However, I'm confused about how I'd show this for the disjoint union. It seems to me that this bijection is almost implicit in the definition of the disjoint union. I.e. the disjoint union indexes each element according to which set it came from. I'm looking for some help getting started with this.

I would try thinking about listing the elements of the sets in an infinite square array and moving along diagonals.
 
  • #4
Thanks for the replies! So, from the definition, the disjoint union gives pairs (x, i) : x[itex]\in[/itex]S[itex]_{i}[/itex]. I'm looking at my proof of why Q is countable: It begins with showing that if S and T are countable sets, then so is S X T. What would be the analogous argument for the disjoint union?
 

FAQ: Prove Disjoint Union of Countable Sets is Countable

What is the definition of a disjoint union of sets?

A disjoint union of sets is a mathematical operation that combines two or more sets into a new set. The resulting set contains all the elements from the original sets, with no overlap or common elements between them.

How do you prove that a disjoint union of countable sets is countable?

To prove that a disjoint union of countable sets is countable, we must show that there exists a one-to-one correspondence between the elements of the disjoint union and the natural numbers. This means that we can enumerate all the elements of the disjoint union in a systematic way, without skipping any elements.

Why is it important to prove that the disjoint union of countable sets is countable?

Proving that the disjoint union of countable sets is countable is important because it helps us understand the properties of countable sets and their operations. It also allows for the creation of new countable sets by combining existing ones, which is useful in various areas of mathematics.

Can you give an example of a proof for the disjoint union of countable sets being countable?

One example of a proof for the disjoint union of countable sets being countable is by using the diagonalization argument. This involves creating a table with the elements of the disjoint union and systematically listing them in rows and columns. By following a specific pattern, we can show that all the elements can be enumerated without skipping any, proving that the disjoint union is countable.

Are there any other properties of countable sets that can be proven using the same method?

Yes, the same method of using a one-to-one correspondence between elements and natural numbers can also be used to prove other properties of countable sets, such as the countability of cartesian products and the countability of the set of all finite sequences of elements from a countable set.

Similar threads

Back
Top