Not a duplicate of
This is exercise $3.7.5$ from the book How to Prove it by Velleman $($$2^{nd}$ edition$)$:
Suppose $\mathcal F$ is a nonempty family of sets. Let $I=\bigcup\mathcal F$ and $J=\bigcap\mathcal F$. Suppose also that $J\neq\emptyset$, and notice that it follows that for every $X\in\mathcal F$, $X\neq\emptyset$, and also that $I\neq\emptyset$. Finally, suppose that $\{A_i|i\in I\}$ is an indexed family of sets.
$(a)$ Prove that $\bigcup_{i\in I}A_i=\bigcup_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$.
$(b)$ Prove that $\bigcap_{i\in I}A_i=\bigcap_{X\in\mathcal F}(\bigcap_{i\in X}A_i)$.
$(c)$ Prove that $\bigcup_{i\in J}A_i\subseteq\bigcap_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$. Is it always true that $\bigcup_{i\in J}A_i=\bigcap_{X\in\mathcal F}(\bigcup_{i\in X}A_i)?$ Give either a proof or a counterexample to justify your answer.
$(d)$ Discover and prove a theorem relating $\bigcap_{i\in J}A_i$ and $\bigcup_{X\in\mathcal F}(\bigcap_{i\in X}A_i)$.
Here are my proofs:
Part $a$:
$(\rightarrow)$ Let $x$ be an arbitrary element of $\bigcup_{i\in I}A_i$. So we can choose some $i_0$ such that $i_0\in I$ and $x\in A_{i_0}$. Since $I=\bigcup\mathcal F$, $i_0\in\bigcup\mathcal F$. So we can choose some $X_0$ such that $X_0\in\mathcal F$ and $i_0\in X_0$. From $i_0\in X_0$ and $x\in A_{i_0}$, $x\in\bigcup_{i\in X}A_i$. From $X_0\in\mathcal F$ and $x\in\bigcup_{i\in X}A_i$, $x\in\bigcup_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$. Since $x$ is arbitrary, $\bigcup_{i\in I}A_i\subseteq\bigcup_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$.
$(\leftarrow)$ Let $x$ be an arbitrary element of $\bigcup_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$. So we can choose some $X_0$ such that $X_0\in\mathcal F$ and $x\in\bigcup_{i\in X_0}A_i$. So we can choose some $i_0$ such that $i_0\in X_0$ and $x\in A_{i_0}$. From $X_0\in\mathcal F$ and $i_0\in X_0$, $i_0\in\bigcup\mathcal F$. Since $I=\bigcup\mathcal F$, $i_0\in I$. From $i_0\in I$ and $x\in A_{i_0}$, $x\in\bigcup_{i\in I}A_i$. Since $x$ is arbitrary, $\bigcup_{X\in\mathcal F}(\bigcup_{i\in X}A_i)\subseteq\bigcup_{i\in I}A_i$.
Ergo $\bigcup_{i\in I}A_i=\bigcup_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$. $Q.E.D.$
Part $b$:
$(\rightarrow)$ Let $x$ be an arbitrary element of $\bigcap_{i\in I}A_i$. Let $X$ be an arbitrary element of $\mathcal F$. Let $i$ be an arbitrary element of $X$. Since $X\in\mathcal F$ and $i\in X$, $i\in\bigcup\mathcal F$. Since $I=\bigcup\mathcal F$, $i\in I$. From $x\in\bigcap_{i\in I}A_i$ and $i\in I$, $x\in A_i$. Since $i$ is arbitrary, $x\in\bigcap_{i\in X}A_i$. Since $X$ is arbitrary, $x\in\bigcap_{X\in\mathcal F}(\bigcap_{i\in X}A_i)$. Since $x$ is arbitrary, $\bigcap_{i\in I}A_i\subseteq\bigcap_{X\in\mathcal F}(\bigcap_{i\in X}A_i)$.
$(\leftarrow)$ Let $x$ be an arbitrary element of $\bigcap_{X\in\mathcal F}(\bigcap_{i\in X}A_i)$. Let $i$ be an arbitrary element of $I$. Since $I=\bigcup\mathcal F$, $i\in\bigcup\mathcal F$. So we can choose some $X_0$ such that $X_0\in\mathcal F$ and $i\in X_0$. From $x\in\bigcap_{X\in\mathcal F}(\bigcap_{i\in X}A_i)$ and $X_0\in\mathcal F$, $x\in\bigcap_{i\in X_0}A_i$. From $x\in\bigcap_{i\in X_0}A_i$ and $i\in X_0$, $x\in A_i$. Since $i$ is arbitrary, $x\in\bigcap_{i\in I}A_i$. Since $x$ is arbitrary, $\bigcap_{X\in\mathcal F}(\bigcap_{i\in X}A_i)\subseteq\bigcap_{i\in I}A_i$.
Ergo $\bigcap_{i\in I}A_i=\bigcap_{X\in\mathcal F}(\bigcap_{i\in X}A_i)$. $Q.E.D.$
Part $c$ – proof:
Let $x$ be an arbitrary element of $\bigcup_{i\in J}A_i$. So we can choose some $j_0$ such that $j_0\in J$ and $x\in A_{j_0}$. Let $X$ be an arbitrary element of $\mathcal F$. Since $J=\bigcap \mathcal F$, $j_0\in\bigcap\mathcal F$. From $j_0\in\bigcap\mathcal F$ and $X\in\mathcal F$, $j_0\in X$. From $j_0\in X$ and $x\in A_{j_0}$, $x\in\bigcup_{i\in X}A_i$. Since $X$ is arbitrary, $x\in\bigcap_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$. Since $x$ is arbitrary, $\bigcup_{i\in J}A_i\subseteq\bigcap_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$. $Q.E.D.$
Part $c$ – counterexample:
Suppose $\mathcal F=\Bigr\{\{1,2\},\{2,3\},\{1,2,3\}\Bigr\}$. Suppose $A_1=\{1\}$, $A_2=\{2\}$, and $A_3=\{1\}$. Then $1\in\bigcap_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$ but $1\notin \bigcup_{i\in J}A_i$ and so $\bigcap_{X\in\mathcal F}(\bigcup_{i\in X}A_i)\nsubseteq\bigcup_{i\in J}A_i$. Ergo $\bigcup_{i\in J}A_i\neq\bigcap_{X\in\mathcal F}(\bigcup_{i\in X}A_i)$.
Part $d$:
Let $x$ be an arbitrary element of $\bigcup_{X\in\mathcal F}(\bigcap_{i\in X}A_i)$. So we can choose some $X_0$ such that $X_0\in\mathcal F$ and $x\in\bigcap_{i\in X_0}A_i$. Let $i$ be an arbitrary element of $J$. Since $J=\bigcap\mathcal F$, $i\in\bigcap\mathcal F$. From $i\in\bigcap\mathcal F$ and $X_0\in\mathcal F$, $i\in X_0$. From $x\in\bigcap_{i\in X_0}A_i$ and $i\in X_0$, $x\in A_i$. Since $i$ is arbitrary, $x\in\bigcap_{i\in J}A_i$. Since $x$ is arbitrary, $\bigcup_{X\in\mathcal F}(\bigcap_{i\in X}A_i)\subseteq \bigcap_{i\in J}A_i$. $Q.E.D.$
Alternative ways to prove parts $a$ and $b$:
Part $a$:
Let $x$ be an arbitrary element of $\bigcup_{i\in I}A_i$.
$%
\require{begingroup}
\begingroup
\newcommand{\calc}{\begin{align} \quad &}
\newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}}
\newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} }
\newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & }
\newcommand{\endcalc}{\end{align}}
\newcommand{\Ref}[1]{\text{(#1)}}
\newcommand{\then}{\rightarrow}
\newcommand{\when}{\leftarrow}
\newcommand{\fa}[2]{\forall #1 \left( #2 \right) }
\newcommand{\ex}[2]{\exists #1 \left( #2 \right) }
\newcommand{\exun}[2]{\exists ! #1 \left( #2 \right) }
\newcommand{\F}{\mathcal F}
\newcommand{\equiv}{\leftrightarrow}
%$
\begin{align}
x\in\bigcup_{i\in I}A_i & \equiv \exists i(i\in I\land x\in A_i) \\
& \equiv \exists i\Bigr(i\in \bigcup\mathcal F\land x\in A_i\Bigr) \\
& \equiv \exists i\Bigr(\exists X(X\in\mathcal F\land i\in X)\land x\in A_i\Bigr)\\
& \color{red}{\equiv} \exists X\exists i\Bigr(X\in\mathcal F\land(i\in X\land x\in A_i)\Bigr)\\
& \color{red}{\equiv} \exists X\Bigr(X\in\mathcal F\land\exists i(i\in X\land x\in A_i)\Bigr)\\
& \equiv \exists X\Bigr(X\in\mathcal F\land x\in\bigcup_{i\in X}A_i\Bigr)\\
& \equiv x\in\bigcup_{X\in\mathcal F}\Bigr(\bigcup_{i\in X}A_i\Bigr)
\end{align}
Since $x$ is arbitrary, $\bigcup_{i\in I}A_i=\bigcup_{X\in\mathcal F}(\bigcup_{i\in X}A_i).$ $Q.E.D.$
Part $b$:
Let $x$ be an arbitrary element of $\bigcap_{i\in I}A_i$.
\begin{align}
x\in\bigcap_{i\in I}A_i & \equiv \forall i(i\in I\rightarrow x\in A_i)\\
& \equiv \forall i\Bigr(i\in \bigcup\mathcal F\rightarrow x\in A_i\Bigr)\\
& \equiv \forall i\Bigr(\exists X(X\in\mathcal F\land i\in X)\rightarrow x\in A_i\Bigr)\\
& \equiv \forall i\Bigr(\lnot\exists X(X\in\mathcal F\land i\in X)\lor x\in A_i\Bigr)\\
& \equiv \forall i\Bigr(\forall X(X\notin\mathcal F\lor i\notin X)\lor x\in A_i\Bigr)\\
& \color{red}{\equiv} \forall X\forall i\Bigr(X\notin\mathcal F\lor(i\notin X\lor x\in A_i)\Bigr)\\
& \color{red}{\equiv} \forall X\Bigr(X\notin\mathcal F\lor\forall i(i\notin X\lor x\in A_i)\Bigr)\\
& \equiv \forall X\Bigr(X\notin\mathcal F\lor\forall i(i\in X\rightarrow x\in A_i)\Bigr)\\
& \equiv \forall X\Bigr(X\notin\mathcal F\lor x\in\bigcap_{i\in X}A_i\Bigr)\\
& \equiv \forall X\Bigr(X\in\mathcal F\rightarrow x\in\bigcap_{i\in X}A_i\Bigr)\\
& \equiv x\in\bigcap_{X\in\mathcal F}\Bigr(\bigcap_{i\in X}A_i\Bigr)\\
\end{align}
Since $x$ is arbitrary, $\bigcap_{i\in I}A_i=\bigcap_{X\in\mathcal F}(\bigcap_{i\in X}A_i).$ $Q.E.D.$
I tried to be less superfluous and verbose this time. Are my proofs and counterexample valid$?$ What about the $\color{red}{\text{red iff arrows}}$ in the alternate proofs$?$ Are they valid$?$ Could you please provide alternate proofs for parts $c$ and $d$ as well$?$
Thanks for your attention.
Best Answer
As I said in my comment, the arguments are correct, but I’d like to make a few suggestions to improve readability (which actually isn’t bad). Let’s take part $(a)$ as an example.
It’s rarely necessary to say explicitly that you’re choosing an arbitrary element of a set: you could just as well begin simply ‘Let $x\in\bigcup_{i\in I}A_i$.’ However, there’s also no harm in emphasizing that you’re actually making an argument about every member of the set, and at this stage you’re probably better off (or at least more comfortable!) doing so. You can still tighten up the wording a bit, perhaps something like this:
(You did have one typo: at the end of your fifth sentence you want $x\in\bigcup_{i\in\color{red}{X_0}}A_i$.) I really didn’t change much: I just combined statements when I could and removed excess verbiage. For instance, of ‘some $i_0$ such that $i_0\in I$ and so-and-so’ one can say simply ‘an $i_0\in I$ such that so-and-so’, naming the source of $i_0$ immediately. Some may disagree, but I find that this makes it just a bit easier to read. I also took out a few justifications that I’d classify as obvious (e.g., ‘From $i_0\in X_0$ and $x\in A_{i_0}$’.
If I were writing it up, I’d make similar changes in the rest of $(a)$ and in $(b)$ and the first part of $(c)$. In the second part of $(c)$ I would actually spell out more details:
The alternative arguments for $(a)$ and $(b)$ are correct, but they obscure the actual flow of reasoning: it gets lost in the technical manipulations. Such arguments are necessary when one wants to show that something is derivable within a specific formal system, but in everyday mathematical writing I would definitely avoid them.