# $\cap_{A \in \mathcal{F}}(B \cup A) \subseteq B \cup (\cap \mathcal{F})$

$A$ and $B$ are sets and $\mathcal{F}$ is a family of sets. I'm trying to prove that

$\bigcap_{A \in \mathcal{F}}(B \cup A) \subseteq B \cup (\cap \mathcal{F})$

I start with "Let $x$ be arbitrary and let $x \in \bigcap_{A \in \mathcal{F}}(B \cup A)$, which means that $\forall C \in \mathcal{F}(x \in B \cup C)$. So, I need some set to plug in for $C$.

Looking at the goal, I need to prove that $x \in B \cup (\cap \mathcal{F})$, which is $x \in B \lor \forall C \in \mathcal{F}(x \in C)$. But I'm stuck here too because I need to break up the givens into cases in order to break up the goals into cases. I think.

• I should have used $A$ instead of $C$, not that it matters, but there was no good reason to change letters. – Matt Gregory Dec 11 '14 at 12:54

Note that $x \in \bigcap_{A \in \mathcal{F}} (B \cup A)$ is the same as saying that $(\forall C \in \mathcal{F})(x \in B \cup C)$.

If $x \in B$, then certainly $x \in B \cup (\bigcap \mathcal{F})$.

If $x \not \in B$, then $(x \in B \cup C) \Rightarrow (x \in C)$, so it must be the case that $(\forall C \in \mathcal{F})(x \in C)$, i.e. $x \in \bigcap \mathcal{F}$, and hence $x \in B \cup (\bigcap \mathcal{F})$.

So $x \in \bigcap_{A \in \mathcal{F}} (B \cup A) \Rightarrow x \in B \cup (\bigcap \mathcal{F})$, hence the former is a subset of the latter.

In fact, they are equal.

You can check that $x\in \bigcap_{A\in\mathcal{F}}(B\cup A)$ iff $\forall A\in\mathcal{F}: (x\in B)\lor (x\in A)$. Since $B$ occurs free, it is equivalent to $x\in B \lor (\forall A\in \mathcal{F}:x\in A)$ and is equivalent to $x\in B\cup \bigcap_{A\in\mathcal{F}}A$.

• I think your argument uses what I'm trying to prove (that a free variable can be pulled out of the quantifier). – Matt Gregory Dec 11 '14 at 12:48
• @MattGregory No, it does not: it proves that $\;B \cup\;$ can be pulled out of $\;\bigcap_A\;$, by using the definitions and the analogous rule of logic that $\;Q \lor\;$ (where $\;Q\;$ does not contain $\;A\;$) can be pulled out of $\;\forall A\;$. – Marnix Klooster Dec 19 '14 at 22:37
• @MarnixKlooster: Yeah, you're right. – Matt Gregory Dec 26 '14 at 21:35