0
$\begingroup$

$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.

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

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I think your argument uses what I'm trying to prove (that a free variable can be pulled out of the quantifier). $\endgroup$ – Matt Gregory Dec 11 '14 at 12:48
  • $\begingroup$ @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\;$. $\endgroup$ – Marnix Klooster Dec 19 '14 at 22:37
  • $\begingroup$ @MarnixKlooster: Yeah, you're right. $\endgroup$ – Matt Gregory Dec 26 '14 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.