Problem 49 - Discrete Mathematics with Applications

Question

Prove each. A countable union of countable sets is countable.

Step-by-Step Solution

Answer

A countable union of countable sets is countable because we can define a bijection from the union to the set of natural numbers. To show this, we construct a list using the diagonal method that includes elements from each countable set in the union. By following this pattern, we can enumerate the elements of the union in a way that maintains a one-to-one correspondence with the natural numbers, proving that the union is also countable.

Step 1: Define countable sets and their union

A set A is countable if there exists a function f: A ⟶ ℕ, ℕ being the set of natural numbers, such that for every element a in A, there is a unique natural number n, where f(a) = n. The function f should be bijective, meaning it is both injective (one-to-one) and surjective (onto). A union of two sets A and B, denoted by A ∪ B, is the set of all elements that are either in A, in B, or in both sets. That is, an element x belongs to the set A ∪ B if and only if x ∈ A or x ∈ B.

Step 2: Prove that the union of two countable sets is countable

Let A and B be two countable sets and f: A ⟶ ℕ and g: B ⟶ ℕ be their corresponding bijections. We will now show that there exists a bijection h: A ∪ B ⟶ ℕ. We will define h by the interleaving method: we will list the elements of A first, and then the elements of B. This list is constructed in the following manner: 1. The first element of A ∪ B is the first element of A. 2. The second element of A ∪ B is the second element of A. 3. The third element of A ∪ B is the first element of B. 4. The fourth element of A ∪ B is the third element of A. 5. The fifth element of A ∪ B is the second element of B. 6. The sixth element of A ∪ B is the fourth element of A. We can write h as follows: h(a) = \(2f(a) - 1\) if a ∈ A h(b) = \(2g(b)\) if b ∈ B It is clear that h is a bijection from A ∪ B to ℕ as it preserves the one-to-one correspondence with natural numbers. Therefore, the union of two countable sets is countable.

Step 3: Prove that the union of an infinite number of countable sets is countable

Let S = {S₁, S₂, S₃, ...} be a countably infinite collection of countable sets, and let fᵢ: Sᵢ ⟶ ℕ be their corresponding bijections. We will now show that there exists a bijection F: ⋃Sᵢ ⟶ ℕ. We will define F using the diagonal method: 1. The first element of ⋃Sᵢ is the first element of S₁. 2. The second element of ⋃Sᵢ is the first element of S₂, followed by the second element of S₁. 3. The third element of ⋃Sᵢ is the first element of S₃, followed by the second element of S₂, and then the third element of S₁. 4. This pattern continues such that in each row i, we include elements from every set Sₙ for 1 ≤ n ≤ i in reverse order. Therefore, we can list the elements of ⋃Sᵢ in the following order: S₁₁, S₃₁, S₂₂, S₁₃, S₄₁, S₃₂, S₂₃, S₁₄, ... This ordering provides a bijection F: ⋃Sᵢ ⟶ ℕ, proving that a countable union of countable sets is countable.

Key Concepts

Bijective Function

A bijective function is one that has a perfect pairing between two sets. It is both injective and surjective, meaning every element has a unique and clear counterpart in the second set.
In simpler terms, imagine a school dance where everyone has a dance partner. Nobody is left out, and nobody has two partners. That's how a bijective function operates between two sets.

• Injective (One-to-One): Ensures that different elements in the set A map to different elements in set B. No two elements from set A share the same partner in set B.
• Surjective (Onto): Guarantees all elements in set B are matched. There are no lonely elements in set B waiting for a partner.

For counting purposes, bijective functions help establish a one-to-one correspondence with natural numbers (ℕ), proving sets like A ∪ B can be considered countable.

Union of Sets

The union of sets collects all unique elements from both sets. This is expressed as A ∪ B, meaning every element in set A, set B, or both, find a place.
If set A has 1, 2, 3 and set B has 3, 4, 5, then the union A ∪ B becomes a collection of the single elements: 1, 2, 3, 4, 5.
This collection reflects how we combine resources from two sources without repeating anything.

• Combining Elements: All members from both sets contribute to the union.
• Creating Uniqueness: Even if the same element is in both sets, it only appears once in the union.

The concept is simple but very powerful when considering countability, especially when dealing with infinity. If both sets contribute finite or countably infinite elements, as the original solution shows, their union remains countable.

Diagonal Method

The diagonal method is a clever way to list elements from multiple sets, ensuring we cover all elements.
Think of arranging people in a theater so nobody is overlooked. You start from the front row, picking the first person, then move diagonally backward, picking people row by row.
This systematic picking keeps everything organized and ensures no one is left behind.

• Pattern: Choose the first of each, then the second round in a diagonal fashion.
• Order: Go from top to bottom, always covering new ground.

With this method, when applied to sets, it's possible to pair elements with natural numbers, proving a union of countable sets stays countable.

Injective and Surjective Functions

Injective and surjective functions are the key characteristics of bijective functions.
Injective: (One-to-One) An injective function ensures unique mapping. Each element in the initial set points to a different element in the second set, just like unique email addresses.
Surjective: (Onto) A surjective function ensures coverage of the second set. Every element in the second set is paired with some element from the first set like ensuring every chair has a person sitting.

• Injective guarantees no overlap in pairings.
• Surjective ensures completeness in mapping.

Understanding these aspects can help visualize how countable sets work toward creating bijections with natural numbers, demonstrating countability.