Exercise 1.2.13

Question

For this exercise, assume Exercise ef{demorgan} has been successfully completed.
  \begin{enumerate}[label=(\alph*)] 
  \item Show how induction can be used to conclude that
    $$
    \left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}ight)^{c}=A_{1}^{c} \cap A_{2}^{c} \cap \cdots \cap A_{n}^{c}
    $$
    for any finite $n \in \mathbf{N}$
  \item It is tempting to appeal to induction to conclude
    $$
    \left(\bigcup_{i=1}^{\infty} A_{i}ight)^{c}=\bigcap_{i=1}^{\infty} A_{i}^{c}
    $$
    but induction does not apply here. Induction is used to prove that a particular statement holds for every value of $n \in \mathbf{N}$, but this does not imply the validity of the infinite case. To illustrate this point, find an example of a collection of sets $B_{1}, B_{2}, B_{3}, \ldots$ where $\bigcap_{i=1}^{n} B_{i} 
eq \emptyset$ is true for every $n \in \mathbf{N}$, but $\bigcap_{i=1}^{\infty} B_{i} 
eq \emptyset$ fails.
  \item Nevertheless, the infinite version of De Morgan's Law stated in (b) is a valid statement. Provide a proof that does not use induction.
   \end{enumerate}

Ulisse Mini · Accepted Answer

\begin{enumerate}[label=(\alph*)] 
  \item \hyperref[demorgan]{1.2.5} Is our base case, Assume $(A_1 \cup \cdots \cup A_n)^c = A_1^c \cap \cdots \cap A_n^c$. We want to show the $n+1$ case. Using associativity we have
    $$
    \begin{aligned}
      ((A_1 \cup \cdots \cup A_n) \cup A_{n+1})^c
      &= (A_1 \cup \dots \cup A_n)^c \cap A_{n+1}^c \
      &= (A_1^c \cap \cdots \cap A_n^c) \cap A_{n+1}^c \
      &= A_1^c \cap \cdots \cap A_n^c \cap A_{n+1}^c
    \end{aligned}
    $$
  \item $B_1 = \{1, 2, \dots\}, B_2 = \{2, 3, \dots\}, \dots$
  \item First suppose $x \in \left(\bigcap_{i=1}^\infty A_iight)^c$, then $x 
otin \bigcap_{i=1}^\infty A_i$ meaning $x 
otin A_i$ for some $i$, which is the same as $x \in A_i^c$ for some $i$, meaning $x \in \bigcup_{i=1}^\infty A_i^c$. This shows
    $$\left(\bigcap_{i=1}^\infty A_iight) \subseteq \bigcup_{i=1}^\infty A_i^c$$
    Now suppose $x \in \bigcup_{i=1}^\infty A_i^c$ meaning $x 
otin A_i$ for some $i$, which is the same as $x 
otin \bigcap_{i=1}^\infty A_i$ implying $x 
otin \left(\bigcap_{i=1}^\infty A_iight)^c$. This shows inclusion the other way and completes the proof.
   \end{enumerate}

Exercise 1.2.13

Answers

Comments

Exercise 1.2.13

Answers

Comments

Add answer