# Validity of this proof: Prove that $\cup \mathcal{F} \subseteq \cap \mathcal{G}$

Here's the question as well as my thought process:

Suppose $\mathcal{F}$ and $\mathcal{G}$ are nonempty families of sets, and every element of $\mathcal{F}$ is a subset of every element of $\mathcal{G}$. Prove that $\bigcup \mathcal{F} \subseteq \bigcap \mathcal{G}$.

$\underline{\textbf{Scratch work:}}$

Interpreting the statement "every element of $\mathcal{F}$ is a subset of every element of $\mathcal{G}$..."

$\Rightarrow \forall A \in \mathcal{F} \forall B \in \mathcal{G} (A \subseteq B)$

While the end goal $\bigcup \mathcal{F} \subseteq \bigcap \mathcal{G}$ can be read as

$\forall x (x \in \bigcup \mathcal{F} \to x \in \bigcap \mathcal{G})$

We now have as a list of givens,

• $\forall A \in \mathcal{F} \forall B \in \mathcal{G} (A \subseteq B)$

• $x \in \bigcup \mathcal{F}$

and the end goal of proving

• $x \in \bigcap \mathcal{G}$

Some of these expressions can be expanded

• $x \in \bigcap \mathcal{G} \Rightarrow \forall B (B \in \mathcal{G} \to x \in B)$

• $x \in \bigcup \mathcal{F} \Rightarrow \exists A (A \in \mathcal{F} \land x \in A)$

And we end up with a new list of givens,

• $\forall A \in \mathcal{F} \forall B \in \mathcal{G} (A \subseteq B)$

• $\exists A (A \in \mathcal{F} \land x \in A)$

• $B \in \mathcal{G}$

as well as a new goal to prove,

• $x \in B$

My final proof goes something like this:

"Suppose $B$ is an arbitrary set in $\mathcal{G}$. Suppose there is some set $A$ that is in $\mathcal{F}$ and that $x$ is an arbitrary element in that set $A$. Since every element in $\mathcal{F}$ is a subset of $\mathcal{G}$, it follows that $x$ is also an element in the arbitrary $B$ that is is $\mathcal{G}$. In other words, $x \in \bigcap \mathcal{G}$. Based on this, we can conclude that if $x \in \bigcup \mathcal{F}$ then $x \in \bigcap \mathcal{G}$. This proves $\bigcup\mathcal{F}\subseteq\bigcap\mathcal{G}$."

Does this line of thinking seem reasonable? In particular, I'm unsure about the idea that since $x$ is an element in some particular set $A$ in $\mathcal{F}$, it is then an element in every arbitrary set $B$ in $\mathcal{G}$.

I hope that this question makes sense - Working on proofs is new to me so I apologize in advance if this question seems somewhat elementary.

Thanks in advance for the help!

• sorry guys, I meant to say that "every element of $\mathcal{F}$ is a subset of $\textit{every}$ element of $\mathcal{G}$" – user268537 Jul 19 '17 at 7:01
• Yeah your argument is fine. – Ravi Jul 19 '17 at 7:05

The statement is false.

Say $\mathcal F=\{\{\{1\}\}\}$ (i.e., $\mathcal F$ has one element, and that element is $\{\{1\}\}$.

And say $\mathcal G=\{\{1\}\}$

Then, it is true that every element of $\mathcal F$ is an element of $\mathcal G$, however

$$\bigcup \mathcal F = \{\{1\}\}\neq \{1\}=\bigcap \mathcal G$$

You say

Interpreting the statement "every element of $\mathcal{F}$ is a subset of $\mathcal{G}$..." $$\Rightarrow \forall A \in \mathcal{F} \forall B \in \mathcal{G} (A \subseteq B)$$

But that logical statement would actually translate into

Every element of $\mathcal F$ is a subset of every element of $\mathcal G$.

which is a very different statement from the original "every element of $\mathcal{F}$ is a subset of $\mathcal{G}$"

After edit

Does this line of thinking seem reasonable? In particular, I'm unsure about the idea that since $x$ is an element in some particular set $A$ in $\mathcal{F}$, it is then an element in $\textit{every}$ arbitrary set $B$ in $\mathcal{G}$.

The line of thinking is reasonable, yes.

You start with an arbitrary $B\in\mathcal G$ and an arbitrary $x\in\bigcup\mathcal F$. All you know about $B$ is that it is an element of $\mathcal G$, and all you know about $x$ is that it is an element of $\bigcup \mathcal F$.

From here on, you then take a set $A\in\mathcal F$ such that $x\in A$ because you know such a set must exist. You now have a concrete $x, A$ and $B$, and you know that $A\subseteq B$ which means that $x\in B$.

Now you take a step back and remember that $x$ and $B$ were arbitrary. So, you can conclude, that whenever you have $x\in \bigcup F$ and whenever you have $B\in \mathcal G$, you also know that $x\in B$. In other words:

$$\forall x\in\bigcup \mathcal F: (\forall B\in \mathcal G: x\in B)$$

Now you just simplify that, since $(\forall B\in \mathcal G: x\in B)$ is equivalent to $(x\in\bigcap \mathcal G)$ and you get

$$\forall x\in\bigcup \mathcal F: (x\in\bigcap\mathcal G)$$

which is what you wanted to prove.

• yeah that is actually what I meant to say. sorry for the confusion – user268537 Jul 19 '17 at 7:03
• @AlexJ.Lim See my edited answer. – 5xum Jul 19 '17 at 7:11