Exercise 2.3

Question

Show that (b), (c), (f), and (g) of \href{./exercise_2-2}{Exercise 2} hold for arbitrary unions and intersections.

Dan Whitman · Accepted Answer

ewcommand\parens[1]{\left( #1 ight)}

ewcommand\squares[1]{\left[ #1 ight]}

ewcommand\angles[1]{\left\langle #1 ightangle}

ewcommand\ceil[1]{\left\lceil #1 ightceil}

ewcommand\floor[1]{\left\lfloor #1 ightfloor}

ewcommand\abs[1]{\left| #1 ight|}

ewcommand
orm[1]{\left\lVert #1 ightVert}

ewcommand\dabs[1]{\left\| #1 ight\|}

ewcommand\vect[1]{\mathbf{#1}}

ewcommand\closure[1]{\overline{#1}}

ewcommand\clop[1]{[#1)}

ewcommand\opcl[1]{(#1]}

ewcommand\inv[1]{#1^{-1}}

ewcommand\col[1]{\mathcal{#1}}

In what follows suppose that $f: A 	o B$ and that $\col{A}$ and $\col{B}$ are nonempty collections of subsets of $A$ and $B$, respectively.
This is to say that $A' \subset A$ for all $A' \in \col{A}$ and $B' \subset B$ for all $B' \in \col{B}$.

First, we show that part in \href{./exercise_2-2}{Exercise 2} part~(b) holds for arbitrary unions, i.e. that
\begin{gather*}
  \inv{f}\parens{\bigcup_{B' \in \col{B}} B'} = \bigcup_{B' \in \col{B}} \inv{f}(B') \,.
\end{gather*}
\begin{proof}
  As before, we again show this with a string of biconditional assertions:
  \begin{align*}
    x \in \inv{f}\parens{\bigcup_{B' \in \col{B}} B'} &\Leftrightarrow f(x) \in \bigcup_{B' \in \col{B}} B' \
                                                      &\Leftrightarrow \exists B' \in \col{B} (f(x) \in B') \
                                                      &\Leftrightarrow \exists B' \in \col{B} (x \in \inv{f}(B')) \
                                                      &\Leftrightarrow x \in \bigcup_{B' \in \col{B}} \inv{f}(B')
  \end{align*}
  as desired.
\end{proof}

Next, we show \href{./exercise_2-2}{Exercise 2} part~(c) for arbitrary intersections, that is
\begin{gather*}
  \inv{f}\parens{\bigcap_{B' \in \col{B}} B'} = \bigcap_{B' \in \col{B}} \inv{f}(B') \,.
\end{gather*}
\begin{proof}
  We show this with a string of bijections again:
  \begin{align*}
    x \in \inv{f}\parens{\bigcap_{B' \in \col{B}} B'} &\Leftrightarrow f(x) \in \bigcap_{B' \in \col{B}} B' \
                                                      &\Leftrightarrow \forall B' \in \col{B} (f(x) \in B') \
                                                      &\Leftrightarrow \forall B' \in \col{B} (x \in \inv{f}(B')) \
                                                      &\Leftrightarrow x \in \bigcap_{B' \in \col{B}} \inv{f}(B') \,,
  \end{align*}
  which shows the desired result.
\end{proof}

Now we show \href{./exercise_2-2}{Exercise 2} part~(f) for arbitrary unions, that is that
\begin{gather*}
  f\parens{\bigcup_{A' \in \col{A}} A'} = \bigcup_{A' \in \col{A}} f(A') \,.
\end{gather*}
\begin{proof}
  Again we utilize a string of biconditionals:
  \begin{align*}
    y \in f\parens{\bigcup_{A' \in \col{A}} A'} &\Leftrightarrow \exists x \squares{x \in \bigcup_{A' \in \col{A}} A' \land y = f(x)} \
                                                &\Leftrightarrow \exists x \squares{\exists A' \in \col{A} (x \in A') \land y = f(x)} \
                                                &\Leftrightarrow \exists x \squares{\exists A' \in \col{A} (x \in A' \land y = f(x))} \
                                                &\Leftrightarrow \exists x \exists A' \in \col{A} (x \in A' \land y = f(x)) \
                                                &\Leftrightarrow \exists A' \in \col{A} \exists x (x \in A' \land y = f(x)) \
                                                &\Leftrightarrow \exists A' \in \col{A} \squares{\exists x (x \in A' \land y = f(x))} \
                                                &\Leftrightarrow \exists A' \in \col{A} \squares{y \in f(A')} \
                                                &\Leftrightarrow y \in \bigcup_{A' \in \col{A}} f(A') \,,
  \end{align*}
  from which the result follows immediately.
\end{proof}

Lastly, we show \href{./exercise_2-2}{Exercise 2} part~(g) for arbitrary intersections, which is that
\begin{gather*}
  f\parens{\bigcap_{A' \in \col{A}} A'} \subset \bigcap_{A' \in \col{A}} f(A') \,,
\end{gather*}
where equality holds if $f$ is injective.
\begin{proof}
  First suppose that $y \in f\parens{\bigcap_{A' \in \col{A}} A'}$ so that there is an $x \in \bigcap_{A' \in \col{A}} A'$ where $y = f(x)$.
  Then $x \in A'$ for every $A' \in \col{A}$.
  So, for any such $A' \in \col{A}$, we have that $x \in A'$ and $y = f(x)$ so that $y \in f(A')$.
  Since $A'$ was arbitrary, this shows that $y \in \bigcap_{A' \in \col{A}} f(A')$, which shows the desired result since $y$ was arbitrary.

Now suppose that $f$ is injective and let $y \in \bigcap_{A' \in \col{A}} f(A')$.
  Then $y \in f(A')$ for every $A' \in \col{A}$.
  So, for any such $A_0 \in \col{A}$ we have that $y \in f(A_0)$ so that there is a $x_0 \in A_0$ where $y = f(x_0)$.
  Suppose for the moment that $x_0 
otin \bigcap_{A' \in \col{A}} A'$ so that there is an $A_1 \in \col{A}$ where $x_0 
otin A_1$.
  However, since $A_1 \in \col{A}$ we have that $y \in f(A_1)$, and hence there is an $x_1 \in A_1$ where $y = f(x_1)$.
  But then we have $f(x_0) = y = f(x_1)$ so that $x_0 = x_1$ since $f$ is injective, and so we have that both $x_0 
otin A_1$ and $x_0 = x_1 \in A_1$.
  As this is a contradiction, it has to be that $x_0 \in \bigcap_{A' \in \col{A}} A'$.
  Since also $y = f(x_0)$, this shows that $y \in f\parens{\bigcap_{A' \in \col{A}} A'}$.
  This shows that $f\parens{\bigcap_{A' \in \col{A}} A'} \supset \bigcap_{A' \in \col{A}} f(A')$ since $y$ was arbitrary, which in turns proves the desired equivalence.
\end{proof}

Exercise 2.3

Answers

Comments

Exercise 2.3

Answers

Comments

Add answer