Subjects set theory

Countable Union 2Ca786

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Use the AI math solver

1. **Problem Statement:** Prove that if $A$ and $B$ are two countable subsets of $\mathbb{R}$, then their union $A \cup B$ is also countable. 2. **Recall the definition:** A set is countable if it is either finite or has the same cardinality as the natural numbers $\mathbb{N}$, meaning there exists a bijection between the set and $\mathbb{N}$. 3. **Key idea:** Since $A$ and $B$ are countable, there exist functions: $$f: \mathbb{N} \to A \quad \text{and} \quad g: \mathbb{N} \to B$$ that are surjective (onto). 4. **Construct a surjection for $A \cup B$:** Define a function $h: \mathbb{N} \to A \cup B$ by interleaving elements from $A$ and $B$: $$h(n) = \begin{cases} f\left(\frac{n+1}{2}\right) & \text{if } n \text{ is odd} \\ g\left(\frac{n}{2}\right) & \text{if } n \text{ is even} \end{cases}$$ 5. **Explanation:** This function $h$ lists elements from $A$ and $B$ alternately, ensuring every element of $A$ and $B$ appears in the image of $h$. 6. **Surjectivity:** Since $f$ and $g$ are surjective, every element of $A$ and $B$ appears in the image of $h$, so $h$ is surjective onto $A \cup B$. 7. **Conclusion:** Because there is a surjection from $\mathbb{N}$ to $A \cup B$, the union $A \cup B$ is countable. **Final answer:** The union of two countable sets is countable.