To prove that the union of two countable sets $X$ and $Y$ is countable, we will proceed as follows:

Step-by-Step Proof

Definitions:

1. Countable Set: A set $A$ is countable if there exists a bijection between $A$ and the set of natural numbers $\mathbb{N}$, meaning $A$ can either be finite or countably infinite.
2. Union of Two Sets: The union $X \cup Y$ consists of all elements in $X$, $Y$, or both.

Goal:

We need to prove that if $X$ and $Y$ are countable sets, then their union $X \cup Y$ is also countable.

Strategy:

We construct functions from $X$ and $Y$ to the set $\mathbb{N}$ and use these to define a function on the union $X \cup Y$.

Step 1: Countable Functions for $X$ and $Y$

Since $X$ and $Y$ are countable, there exist bijections:

• $f: X \to \mathbb{N}$
• $g: Y \to \mathbb{N}$

Thus, each element in $X$ and $Y$ can be uniquely assigned a natural number.

Step 2: Define a Function on the Union $X \cup Y$

To construct a bijection for $X \cup Y$, we must map the elements of $X \cup Y$ to $\mathbb{N}$.

There are two cases to consider:

• $X \cap Y \neq \emptyset$, meaning $X$ and $Y$ may have some common elements.
• $X \cap Y = \emptyset$, meaning $X$ and $Y$ are disjoint.

To handle both cases, we can proceed as follows:

• Consider the function $h: X \cup Y \to \mathbb{N} \times \{0, 1\}$ defined by: \begin{cases} (f(z), 0) & \text{if } z \in X \setminus Y \\ (g(z), 1) & \text{if } z \in Y \setminus X \\ (f(z), 0) & \text{if } z \in X \cap Y \end{cases}$$

This function creates a distinct pair for elements of $X$ and $Y$ by pairing the outputs of $f$ and $g$ with an indicator value (0 or 1), ensuring that even if an element is shared by both sets, it is assigned consistently.

Step 3: Map $\mathbb{N} \times \{0, 1\}$ to $\mathbb{N}$

Next, we need to show that $\mathbb{N} \times \{0, 1\}$ is countable. This can be done by interleaving the pairs to produce a single natural number using a known bijection between $\mathbb{N} \times \mathbb{N}$ and $\mathbb{N}$. A simple function that works is: $\varphi(n, 0) = 2n, \quad \varphi(n, 1) = 2n + 1$ This function maps all pairs in $\mathbb{N} \times \{0, 1\}$ to distinct natural numbers, preserving the countability of the union.

Step 4: Conclude that $X \cup Y$ is Countable

The composition of the function $h$ with the bijection $\varphi$ gives a bijection from $X \cup Y$ to $\mathbb{N}$, showing that $X \cup Y$ is countable.

Conclusion:

We have constructed a bijection from the union $X \cup Y$ to $\mathbb{N}$, proving that the union of two countable sets is countable.

Would you like more details or have any questions on this?

Here are 5 follow-up questions to deepen your understanding:

1. What would change in the proof if $X$ or $Y$ were finite instead of infinite?
2. How does the concept of countability relate to uncountable sets like $\mathbb{R}$?
3. Can you extend this proof to a finite or infinite union of countable sets?
4. How does the interleaving method for $\mathbb{N} \times \{0, 1\}$ relate to Cantor’s pairing function?
5. How would this proof be adjusted if $X$ and $Y$ were not disjoint?

Tip: The union of any finite number of countable sets is always countable, but the infinite case requires a more careful treatment involving the axiom of choice!