The Union and Intersection of Two Countable Sets is Countable
The Union and Intersection of Two Countable Sets is Countable
The Union of Two Countable Sets is Countable
Theorem 1: Let $A$ and $B$ be countable sets. Then $A \cup B$ is countable. |
- Proof: The cases when at least one of $A$ or $B$ is finite are easy to prove. So instead suppose that $A$ and $B$ are both countably infinite.
- We can assume that both $A$ and $B$ are disjoint sets, that is, $A \cap B = \emptyset$. This is because if $A$ and $B$ are not disjoint, then write $A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B)$. The sets $A \setminus B$, $B \setminus A$, and $A \cap B$ are all countable and so we can apply the theorem to $(A \setminus B) \cup (B \setminus A)$ and then to $[(A \setminus B) \cup (B \setminus A)] \cup (A \cap B)$.
- So assume that $A \cap B = \emptyset$.
- Since $A$ and $B$ are countably infinite there exists bijections $f : A \to \mathbb{N}$ and $g : B \to \mathbb{N}$. Define a function $h : A \cup B \to \mathbb{N}$ by:
\begin{align} \quad h(c) = \left\{\begin{matrix} 2f(c) & \mathrm{if} \: c \in A \\ 2g(c) + 1 & \mathrm{if} \: c \in B \end{matrix}\right. \end{align}
- We need to show that $h$ is injective. Let $c, d \in A \cup B$ and suppose that $h(c) = h(d)$. There are three cases to consider.
- Case 1: If $c \in A$ and $d \in A$ then $h(c) = h(d)$ implies that $2f(c) = 2f(d)$ and so $f(c) = f(d)$ which implies that $c = d$.
- Case 2: If $c \in B$ and $d \in B$ then $h(c) = h(d)$ implies that $2g(c) + 1 = 2g(d) + 1$ and so $g(c) = g(d)$ which implies that $c = d$.
- Case 3: If $c \in A$ and $d \in B$ then $h(c) = h(d)$ implies that $2f(c) = 2g(d) + 1$ so $2[f(c) - g(d)] = 1$ which happens if and only if $f(c) - g(d) = \frac{1}{2}$. This cannot happen since $f(c), g(d) \in \mathbb{N}$.
- Case 4: If $c \in B$ and $d \in A$ then $h(c) = h(d)$ implies that $2g(c) + 1 = 2f(d)$ so $2[f(d) - g(c)] = 1$ which happens if and only if $f(d) - g(c) = \frac{1}{2}$. Again, this cannot happen since $f(d), g(c) \in \mathbb{N}$.
- Therefore in all cases we have that $m = n$, so $h$ is injective and $h(A \cup B) \subseteq \mathbb{N}$ is countably infinite. So there exists a bijection $s : h(A \cup B) \to \mathbb{N}$.
- Observe also that the function $t : (A \cup B) \to f(A \cup B)$ defined for all $c \in A \cup B$ by $t(c) = h(c)$ is a bijection.
- Therefore the composition $s \circ t : (A \cup B) \to \mathbb{N}$ is a bijection and $A \cup B$ is countably infinite. $\blacksquare$
Theorem 2: Let $\{ A_{\lambda} \}_{\lambda \in \Lambda}$ be a countable collection of countable sets. Then $\displaystyle{\bigcup_{\lambda \in \Lambda} A_{\lambda}}$ is countable. |
The Intersection of Two Countable Sets is Countable
Theorem 3: Let $A$ and $B$ be countable sets. Then $A \cap B$ is a countable set. |
- Proof: Observe that $A \cap B \subseteq A$. Since $A$ is countable, so is $A \cap B$. $\blacksquare$
More generally, if one of $A$ or $B$ is countable then the intersection $A \cap B$ will be countable.
Theorem 4: Let $\{ A_{\lambda} \}_{\lambda \in \Lambda}$ be a countable collection of countable sets. Then $\displaystyle{\bigcap_{\lambda \in \Lambda} A_{\lambda}}$ is countable. |