Exercise 1.5.3

Question

\label{ex:countable_union}
  \begin{enumerate}[label=(\alph*)] 
  \item Prove if $A_1, \dots, A_m$ are countable sets then $A_1 \cup \dots \cup A_m$ is countable.
  \item Explain why induction \emph{cannot} be used to prove that if each $A_n$ is countable, then $\bigcup_{n=1}^\infty A_n$ is countable.
  \item Show how arranging $\mathbf{N}$ into the two-dimensional array
  $$\begin{array}{llllll}1 & 3 & 6 & 10 & 15 & \cdots \ 2 & 5 & 9 & 14 & \cdots & \ 4 & 8 & 13 & \cdots & & \ 7 & 12 & \cdots & & & \ 11 & \cdots & & & & \ \vdots & & & & & \end{array}$$
  leads to a proof for the infinite case.
 \end{enumerate}

Ulisse Mini · Accepted Answer

\begin{enumerate}[label=(\alph*)] 
  \item Let $B, C$ be disjoint countable sets. We use the same trick as with the integers and list them as
    $$B \cup C = \{b_1, c_1, b_2, c_2, \dots\}$$
    Meaning $B \cup C$ is countable, and $A_1 \cup A_2$ is also countable since we can let $B = A_1$ and $C = A_2 \setminus A_1$.

Now induction: suppose $A_1 \cup \dots \cup A_n$ is countable, $\left(A_1 \cup \dots \cup A_night) \cup A_{n+1}$ is the union of two countable sets which by above is countable.
  \item Induction shows something for each $n \in \mathbf{N}$, it does not apply in the infinite case.
  \item Rearranging $\mathbf{N}$ as in (c) gives us disjoint sets $C_n$ such that $\bigcup_{n=1}^\infty C_n = \mathbf{N}$.
    Let $B_n$ be disjoint, constructed as $B_1 = A_1, B_2 = A_1 \setminus B_1, \dots$ we want to do something like

$$f(\mathbf{N}) = f\left(\bigcup_{n=1}^\infty C_night) = \bigcup_{n=1}^\infty f_n(C_n) = \bigcup_{n=1}^\infty B_n = \bigcup_{n=1}^\infty A_n$$
    Let $f_n : C_n 	o B_n$ be bijective since $B_n$ is countable, define $f : \mathbf{N} 	o \bigcup_{n=1}^\infty B_n$ as
    $$
    f(n) = \begin{cases}
      f_1(n) &	ext{if } n \in C_1 \
      f_2(n) &	ext{if } n \in C_2 \
      \vdots
    \end{cases}
    $$
    \begin{enumerate}[label=(oman*)] 
      \item Since each $C_n$ is disjoint and each $f_n$ is 1-1, $f(n_1) = f(n_2)$ implies $n_1 = n_2$ meaning $f$ is 1-1.
      \item Since any $b \in \bigcup_{n=1}^\infty B_n$ has $b \in B_n$ for some $n$, we know $b = f_n(x)$ has a solution since $f_n$ is onto. Letting $x = f_{n}^{-1}(b)$ we have $f(x) = f_n(x) = b$ since $f_n^{-1}(b) \in C_n$ meaning $f$ is onto.
       \end{enumerate}
      By (i) and (ii) $f$ is bijective and so $\bigcup_{n=1}^\infty B_n$ is countable. And since
      $$\bigcup_{n=1}^\infty B_n = \bigcup_{n=1}^\infty A_n$$
      We have that $\bigcup_{n=1}^\infty A_n$ is countable, completing the proof.
   \end{enumerate}

Exercise 1.5.3

Answers

Comments

Exercise 1.5.3

Answers

Comments

Add answer